(12)--第4章 树和二叉树-线索化二叉树.ppt

《(12)--第4章 树和二叉树-线索化二叉树.ppt》由会员分享，可在线阅读，更多相关《(12)--第4章 树和二叉树-线索化二叉树.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 树和二叉树线索化二叉树线索化二叉树思考思考二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。线索化二叉索化二叉树在n个结点的二叉链表中，有n+1个空指针域 AB C D E F G线索化二叉索化二叉树普通二叉普通二叉树只能找到只能找到结点的左右孩子信息，而点的左右孩子信息，而该结点的点的直接前直接前驱和直接后和直接后继只能在遍只能在遍历过程中程中获得得若将遍若将遍历后后对应的有关前的有关前驱和后和后继预存起来，存起来，则从从第一第一个个结点点开始就能很快开始就能很快“顺藤摸瓜藤摸瓜”而遍而遍历整个整个树例如中序

2、遍例如中序遍历结果：果：B D C E A F H G，实际上上已将二已将二叉叉树转为线性排列，性排列，显然具有唯一前然具有唯一前驱和唯一后和唯一后继！可能是根、或最左（右）叶子两种解决方法增加两个域：fwd和bwd；利用空链域（n+1个空链域）如何保存如何保存这类信息？信息？线索化二叉索化二叉树1）若）若结点有左子点有左子树，则lchild指向其左孩子；指向其左孩子；否否则，lchild指向其直接前指向其直接前驱(即即线索索)；2）若）若结点有右子点有右子树，则rchild指向其右孩子；指向其右孩子；否否则，rchild指向其直接后指向其直接后继(即即线索索)。为了避免混淆，增加两个了避免混

3、淆，增加两个标志域志域lchildLTagdataRTag rchild线索化二叉索化二叉树LTag :若若 LTag=0,lchild域指向左孩子；域指向左孩子；若若 LTag=1,lchild域指向其前域指向其前驱。RTag :若若 RTag=0,rchild域指向右孩子；域指向右孩子；若若 RTag=1,rchild域指向其后域指向其后继。lchildLTagdataRTag rchild线索化二叉索化二叉树ABCDE A B D C ET先序序列：先序序列：ABCDE0000111111 lchild LTag data RTag rchild先序线索二叉树先序线索二叉树LTag=0,

4、lchildLTag=0,lchild域指向左孩子域指向左孩子LTag=1,lchildLTag=1,lchild域指向其前驱域指向其前驱RTag=0,rchildRTag=0,rchild域指向右孩子域指向右孩子RTag=1,rchildRTag=1,rchild域指向其后继域指向其后继 中序中序线索二叉索二叉树ABCDE A B D C ET中序序列：中序序列：BCAED0000111111 lchild LTag data RTag rchild后序后序线索二叉索二叉树 lchild LTag data RTag rchildABCDE A B D C ET后序序列：后序序列：CBEDA

5、0000111111线索索：指向：指向结点前点前驱和后和后继的指的指针线索索链表表：加上：加上线索二叉索二叉链表表线索二叉索二叉树：加上：加上线索的二叉索的二叉树（图形式形式样）线索化索化：对二叉二叉树以某种次序遍以某种次序遍历使其使其变为线索索二叉二叉树的的过程程线索化二叉索化二叉树的几个的几个术语ABCGEIDHFroot悬悬空？空？悬悬空？空？该二叉二叉树中序遍中序遍历结果果为:H,D,I,B,E,A,F,C,G画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点练习对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此注：此图中序遍中序遍历结果果为:H,D,I,B,E,A,F,C,G0-root0画出与二叉树对应的中序线索二叉树2825405560330854因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL练习下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）ABCDABCD提交单选题2分2/8/2024此处添加题目描述ABCDABCD提交单选题2分