《线索二叉树(1)》由会员分享，可在线阅读，更多相关《线索二叉树(1)（26页珍藏版）》请在金锄头文库上搜索。
1、 一个具有n个结点的二叉树若采用二叉链表存储结构，在 2n个指针域中只有n1个指针域是用来存储结点孩子的地址 ，而另外n1个指针域存放的都是NULL。因此，可以利用 某结点空的左指针域（lchild）指出该结点在某种遍历序列 中的直接前驱结点的存储地址，利用结点空的右指针域（ rchild）指出该结点在某种遍历序列中的直接后继结点的存 储地址；对于那些非空的指针域，则仍然存放指向该结点左 、右孩子的指针。这样，就得到了一棵线索二叉树。由于序列可由不同的遍历方法得到，因此，线索树有先序 线索二叉树、中序线索二叉树和后序线索二叉树三种。把二 叉树改造成线索二叉树的过程称为线索化。线索二叉树EACB
2、DFGEFABDCGACBEDFG先序线索二叉树 中序线索二叉树 后序线索二叉树 线索二叉树那么，下面的问题是在存储中，如何区别某结点 的指针域内存放的是指针还是线索？通常可以采 用下面两种方法来实现。方法一：不改变结点结构，仅在作为线索的地址 前加一个负号，即负的地址表示线索，正的地址 表示指针。实现方法二结点中增加两个标记域两标记域取值范围是0，1。 指向前驱和指向后继的指针叫做线索（Thread）。 以这种结构组成的二叉链表作为二叉树的存储结构 ，叫做线索链表。 具有线索的二叉树叫做线索二叉树。rchildlchildltagDatartag指向左孩子0指向前驱1指向右孩子0指向后继1练
3、习：画出下列二叉树的线索二 叉树ABDGCEHF线索二叉树先序线索二叉树：ABDGCEHFNULL先序序列：ABDGCEHFABDGCEHFNULL0A01B00C00D11G10E11A11H1先序序列：ABDGCEHF线索二叉树中序线索二叉树：ABDGCEHF NULLNULL中序序列：DGBAEHCF线索二叉树后序线索二叉树：ABDGCEHFNULL后序序列：GDBHEFCA线索二叉树的操作 建立线索二叉树 在线索二叉树中查找前驱和后继结点 线索二叉树的插入和删除运算结点定义：typedef struct node int data;int ltag, rtag;struct node
4、*lchild, *rchild; tbinode,*tbitree;结点结构rchildlchildltagDatartag递归中序线索化二叉树INTHREAD(tbitree *root) if (p!=NULL) INTHREAD(root-lchild);if (root-lchild=NULL) root-ltag1; root-lchildpre;if (pre!=NULL pre-rtag=1preroot;INTHREAD(p-rchild); ABCDE0 A 01 B 0 0 D 11 C 1 1 E 1 T中序序列：BCAED 带头结点的中序线索二叉树0 1头结点： lt
5、ag=0, lchild指向根结点 rtag=1, rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后 一个结点的rchild域都指向头结点AB DC ET中序序列：BCAED 中序线索二叉树0000111111 对于中序线索二叉树上的任一结点，寻找其中 序的前驱结点，有以下两种情况： （1）如果该结点的左标志为1，那么其左指针 域所指向的结点便是它的前驱结点； （2）如果该结点的左标志为0，表明该结点 有左孩子，根据中序遍历的定义，它的前驱结 点是以该结点的左孩子为根结点的子树的最右 结点，即沿着其左子树的右指针链向下查找， 当某结点的右标志为1时，它就是所要找
6、的前 驱结点。在线索二叉树中查找前驱和后继结点0A01B00C00D11G10E11A11H1在线索二叉树中查找前驱和后继结点查找前驱的算法： tbitree InPreNode（tbitree p） /*在中序线索二叉树上寻找结点p的中序前驱结点*/tbitree pre;pre=p-lchild;if (p-ltag!=1) while (pre-rtag=0) pre=pre-rchild;return(pre); 0A01B00C00D11G10E11A11H1查找中序线索二叉树后继 对于中序线索二叉树上的任一结点，寻找其中 序的后继结点，有以下两种情况： （1）如果该结点的右标志为1
7、，那么其右指针 域所指向的结点便是它的后继结点； （2）如果该结点的右标志为0，表明该结点 有右孩子，根据中序遍历的定义，它的前驱结 点是以该结点的右孩子为根结点的子树的最左 结点，即沿着其右子树的左指针链向下查找， 当某结点的左标志为1时，它就是所要找的后 继结点。查找后继的算法： tbitree InPostNode（tbitree p） /*在中序线索二叉树上寻找结点p的中序后继结点*/ tbitree post;post=p-rchild;if (p-rtag!=1) while (post-rtag=0) post=post-lchild;return(post); 0A01B00C
8、00D11G10E11A11H1插入操作ABDGCEHF NULLNULLPP-rtag=0;P-rchild=Q;MQ Q-ltag=1;Q-lchild=P;Q-rtag=1;Q-rchild=P-rchild;插入操作 ABDGCEHNULLPFNULLIJMQ插入操作ABDGCEHNULLPMQFNULLIJ RQ-rtag=0;Q-rchild=P-rchild;Q-ltag=1;Q-lchild=P;P-rchild=Q; R-lchild=Q;删除操作ABDGCEHF NULLNULLMPQ-rtag=0;Q-rchild=P-rchild;Q删除操作ABDGCEHF NULLNULLfree(P);Q-rtag=0;Q-rchild=P-rchild;Q删除操作ABDGCEHNULLPMQFNULLIJ RR-lchild=Q-lchild;删除操作ABDGCEHNULLPFNULLIJ RR-lchild=Q-lchild; p-rchild=Q-rchild;free(Q);
