数据结构.第6章.树和二叉树.2.遍历二叉树和线索二叉树VIP专享VIP免费

武汉科技大学WuhanUniversityofScienceandTechnology数据结构DataStructures张凯计算机学院软件工程系2011年3月12日树和森林第6章树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用提出问题§6.3遍历二叉树和线索二叉树在二叉树的一些应用中，常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了遍历二叉树的问题。遍历是任何类型均有的操作§6.3遍历二叉树和线索二叉树对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)；而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。遍历二叉树§6.3遍历二叉树和线索二叉树对二叉树而言，是由三个基本单元组成：根结点、左子树和右子树。因此，若能遍历这三部分，便是遍历了整个二叉树。考虑：一共有多少种遍历二叉树的方案？遍历二叉树§6.3遍历二叉树和线索二叉树假如以L、D、R分别表示遍历二叉树的左子树、访问根结点、遍历右子树，则有DLR、LDR、LRDDRL、RDL、RLD先序中序后序六种遍历方案选择先左后右的遍历算法§6.3遍历二叉树和线索二叉树先（根）序遍历算法DLR中（根）序遍历算法LDR后（根）序遍历算法LRD先（根）序遍历算法§6.3遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。voidPreOrderTraverse(BiTreebt){if(bt){printf("%c",bt->data);/*输出根结点数据域的值*/PreOrderTraverse(bt->lchild);/*先序遍历左子树*/PreOrderTraverse(bt->rchild);/*先序遍历右子树*/}}中（根）序遍历算法§6.3遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。voidInOrderTraverse(BiTreebt){if(bt){InOrderTraverse(bt->lchild);/*中序遍历左子树*/printf("%c",bt->data);/*输出根结点数据域的值*/InOrderTraverse(bt->rchild);/*中序遍历右子树*/}}后（根）序遍历算法§6.3遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。voidPostOrderTraverse(BiTreebt){if(bt){PostOrderTraverse(bt->lchild);/*后序遍历左子树*/PostOrderTraverse(bt->rchild);/*后序遍历右子树*/printf("%c",bt->data);/*输出根结点数据域的值*/}}例1§6.3遍历二叉树和线索二叉树先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根例2：用二叉树表示算术表达式§6.3遍历二叉树和线索二叉树+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB例3§6.3遍历二叉树和线索二叉树假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。画出该二叉树。遍历算法的递归实现§6.3遍历二叉树和线索二叉树回忆1：二叉树结点的数据类型定义：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;回忆2：递归求解n!longintfact(n)//求n!{longs;if(n>1)s=n*fact(n-1);elsef=1;return(f);}先序遍历二叉树的递归算法§6.3遍历二叉树和线索二叉树StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//二叉链表存储结构，visit是对数据元素操作的应用函数//先序遍历二叉树T的递归算法，对每个数据元素调用visitif(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverser(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}PreOrderTraverseACBD主程序Pre(T)Pre(TR);Pre(TR);TAVisit(A);Pre(TL);TDVisit(D);Pre(TL);TCVisit(C);Pre(TL);TBVisit(B);Pre(TL);返回T>Pre(TR);返回T>返回T>返回T>返回T>Pre(TR);得到的遍历次序为：ABDCPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOr...