数据结构课件树概论.ppt

5．在中序线索二叉树上查找任意结点的中序后继结点 有以下两种情况： ⑴如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点； ⑵如果该结点的右标志为0，它的后继结点是以该结点的右孩子为根结点的子树的最左结点。 6.3.5 线索二叉树 6．线索二叉树应用 二叉树经常遍历或查找结点在遍历所得线性序列中的前驱和后继，应用线索二叉链表作存储结构较合适。 二叉树的线索二叉链表表示（P133） 为了计算方便可添加头结点（P133 图6.11） 6.3.5 线索二叉树 小 结 掌握二叉树的四种遍历方式 指定二叉树的遍历结点序列 恢复二叉树 掌握二叉树遍历的实现算法 递归、非递归实现算法 层次遍历实现算法 理解如何对二叉树线索化 练习题 编写二叉树创建递归算法 编写二叉树中序遍历的非递归算法 编写二叉树后序遍历的非递归算法 利用二叉树的遍历算法实现求二叉树中结点总数和在二叉树中查找某一个结点x的算法。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 先序遍历（DLR）定义： 若二叉树为空，遍历结束。否则， ⑴访问根结点； ⑵先序遍历根结点的左子树； ⑶先序遍历根结点的右子树。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 中序遍历（LDR）定义： 若二叉树为空，遍历结束。否则， ⑴中序遍历根结点的左子树； ⑵访问根结点； ⑶中序遍历根结点的右子树。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 后序遍历（LRD）定义： 若二叉树为空，遍历结束。否则， ⑴后序遍历根结点的左子树； ⑵后序遍历根结点的右子树。 ⑶访问根结点； 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种： 先序、中序、后序和层次遍历 层次遍历定义： 若二叉树为空，遍历结束。否则，从二叉树的第一层（根结点）开始，从上至下逐层遍历，同一层，则按从左到右的顺序逐个访问结点。 6.3.1 二叉树的遍历方式 练习1： 给出下面指定二叉树的四种遍历方式下的结点序列。 6.3.1 二叉树的遍历方式 练习2： 根据给定的遍历结点序列恢复二叉树。 LDR：DCBGEAHFIJK DLR：ABCDEGFHJIK 哪些遍历组合可以唯一确定一棵二叉树？ 6.3.1 二叉树的遍历方式 结论 DLR，LDR可以确定一棵二叉树； LDR，LRD可以确定一棵二叉树； LDR，层次遍历可以确定一棵二叉树 6.3.1 二叉树的遍历方式 练习3： 根据给定的遍历结点序列恢复二叉树。 LDR： B C A E D G H F I LRD： C B E H G I F D A 6.3 二叉树的遍历 6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树 6.3.2 二叉树遍历的递归算法 先序遍历递归算法： void PreOrder（BiTree bt） { if (bt==NULL) return; Visite（bt-data）; PreOrder（bt-lchild）; PreOrder（bt-rchild）; } 6.3.2 二叉树遍历的递归算法 中序遍历递归算法： void InOrder（BiTree bt） { if (bt==NULL) return; InOrder（bt-lchild）; Visite（bt-data）; InOrder（bt-rchild）; } 6.3.2 二叉树遍历的递归算法 后序遍历递归算法： void PostOrder（BiTree bt） { if (bt==NULL) return; PostOrder（bt-lchild）; PostOrder（bt-rchild）; Visite（bt-data）; } 6.3.2 二叉树遍历的递归算法 根据二叉树的递归定义，很容易写出二叉树先序、中序和后序遍历的递归算法。但并非所有程序设计语言都允许递归；另一方面，递归程序虽然简洁，但可读性不好，执行效率也不