早就想办了这个线索二叉树,但是一直又没什么动力。这次就办了吧、
在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。
上面那张图我也没看太明白,但是这块儿我看的明白: 线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索指针和孩子指针,在每个结点中设置两个标志ltag和rtag。 当tag和rtag为0时,leftChild和rightChild分别是指向左孩子和右孩子的指针;否则,leftChild是指向结点前驱的线索(pre),rightChild是指向结点的后继线索(suc)。由于标志只占用一个二进位,每个结点所需要的存储空间节省很多。
现将二叉树的结点结构重新定义如下:
lchild | ltag | data | rtag | rchild |
---|
其中:ltag=0 时lchild指向左儿子;ltag=1 时lchild指向前驱;rtag=0 时rchild指向右儿子;rtag=1 时rchild指向后继。
建立线索二叉树,或者说对二叉树线索化,实质上就是遍历一棵二叉树。在遍历过程中,访问结点的操作是检查当前的左,右指针域是否为空,将它们改为指向前驱结点或后续结点的线索。为实现这一过程,设指针pre始终指向刚刚访问的结点,即若指针p指向当前结点,则pre指向它的前驱,以便设线索。 另外,在对一颗二叉树加线索时,必须首先申请一个头结点,建立头结点与二叉树的根结点的指向关系,对二叉树线索化后,还需建立最后一个结点与头结点之间的线索。 加上线索的二叉树结构是一个双向链表结构,为了便于遍历线索二叉树,我们为其添加一个头结点,头结点左孩子指向原二叉树的根结点,右孩子指针指向中序遍历的最后一个结点。同时,将第一个结点左孩子指针指向头结点,最后一个结点的右孩子指针指向头结点。
//中序遍历进行中序线索化
void inThreading(ThrBiTree T, ThrBiTree &pre){
if(T){
inThreading(T->lchild, pre);//左子树线索化
if(!T->lchild){//当前结点的左孩子为空
T->lTag = Thread;
T->lchild = pre;
}else{
T->lTag = Link;
}
if(!pre->rchild){//前驱结点的右孩子为空
pre->rTag = Thread;
pre->rchild = T;
}else{
pre->rTag = Link;
}
pre = T;
inThreading(T->rchild, pre);//右子树线索化
}
}
加上头结点,遍历线索二叉树:
//T指向头结点,头结点的lchild链域指针指向二叉树的根结点
//中序遍历打印二叉线索树T(非递归算法)
void inOrderTraversePrint(ThrBiTree T){
ThrBiNode *p = T->lchild;//p指向根结点
while(p != T){//空树或遍历结束时,p == T
while(p->lTag == Link){
p = p->lchild;
}
//此时p指向中序遍历序列的第一个结点(最左下的结点)
printf("%c ", p->data);//打印(访问)其左子树为空的结点
while(p->rTag == Thread && p->rchild != T){
p = p->rchild;
printf("%c ", p->data);//访问后继结点
}
//当p所指结点的rchild指向的是孩子结点而不是线索时,p的后继应该是其右子树的最左下的结点,即遍历其右子树时访问的第一个节点
p = p->rchild;
}
printf("\n");
}
优势 (1)利用线索二叉树进行中序遍历时,不必采用堆栈处理,速度较一般二叉树的遍历速度快,且节约存储空间。 (2)任意一个结点都能直接找到它的前驱和后继结点。
不足 (1)结点的插入和删除麻烦,且速度也较慢。 (2)线索子树不能共用。