资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
一个具有n个结点的二叉树若采用二叉链表存储结构,在 2n个指针域中只有n1个指针域是用来存储结点孩子的地址 ,而另外n1个指针域存放的都是NULL。因此,可以利用 某结点空的左指针域(lchild)指出该结点在某种遍历序列 中的直接前驱结点的存储地址,利用结点空的右指针域( rchild)指出该结点在某种遍历序列中的直接后继结点的存 储地址;对于那些非空的指针域,则仍然存放指向该结点左 、右孩子的指针。这样,就得到了一棵线索二叉树。由于序列可由不同的遍历方法得到,因此,线索树有先序 线索二叉树、中序线索二叉树和后序线索二叉树三种。把二 叉树改造成线索二叉树的过程称为线索化。线索二叉树EACBDFGEFABDCGACBEDFG先序线索二叉树 中序线索二叉树 后序线索二叉树 线索二叉树那么,下面的问题是在存储中,如何区别某结点 的指针域内存放的是指针还是线索?通常可以采 用下面两种方法来实现。方法一:不改变结点结构,仅在作为线索的地址 前加一个负号,即负的地址表示线索,正的地址 表示指针。实现方法二结点中增加两个标记域两标记域取值范围是0,1。 指向前驱和指向后继的指针叫做线索(Thread)。 以这种结构组成的二叉链表作为二叉树的存储结构 ,叫做线索链表。 具有线索的二叉树叫做线索二叉树。rchildlchildltagDatartag指向左孩子0指向前驱1指向右孩子0指向后继1练习:画出下列二叉树的线索二 叉树ABDGCEHF线索二叉树先序线索二叉树:ABDGCEHFNULL先序序列:ABDGCEHFABDGCEHFNULL0A01B00C00D11G10E11A11H1先序序列:ABDGCEHF线索二叉树中序线索二叉树:ABDGCEHF NULLNULL中序序列:DGBAEHCF线索二叉树后序线索二叉树:ABDGCEHFNULL后序序列:GDBHEFCA线索二叉树的操作 建立线索二叉树 在线索二叉树中查找前驱和后继结点 线索二叉树的插入和删除运算结点定义:typedef struct node int data;int ltag, rtag;struct node *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头结点: ltag=0, lchild指向根结点 rtag=1, rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后 一个结点的rchild域都指向头结点AB DC ET中序序列:BCAED 中序线索二叉树0000111111 对于中序线索二叉树上的任一结点,寻找其中 序的前驱结点,有以下两种情况: (1)如果该结点的左标志为1,那么其左指针 域所指向的结点便是它的前驱结点; (2)如果该结点的左标志为0,表明该结点 有左孩子,根据中序遍历的定义,它的前驱结 点是以该结点的左孩子为根结点的子树的最右 结点,即沿着其左子树的右指针链向下查找, 当某结点的右标志为1时,它就是所要找的前 驱结点。在线索二叉树中查找前驱和后继结点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,那么其右指针 域所指向的结点便是它的后继结点; (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); 0A01B00C00D11G10E11A11H1插入操作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);
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号