1. 基本概念 在链式存储中,发现二叉链表中存在大量的空指针,如果利用这些空指针指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法。二叉树的线索化,是为了加快查找结点前驱和后继的速度。 在有N个结点的二叉树中,存在N+ ...
1. 基本概念
在链式存储中,发现二叉链表中存在大量的空指针,如果利用这些空指针指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法。二叉树的线索化,是为了加快查找结点前驱和后继的速度。
在有N个结点的二叉树中,存在N+1个空指针。每个叶结点有2个空指针,度为1的结点有1个空指针,总的空指针为2N0+N1,又有N0=N2+1,所以总的空指针为N0+N1+N2+1=N+1。
二叉树线索化规则:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。如图,增加两个标志域,用来表明当前指针指向左右结点还是前驱后继结点。
其中标志位含义为:
线索二叉树的结点:
private class Node{ int data; Node lchild, rchild; int ltag = 0, rtag = 0;}
原标题:线索二叉树
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。