《数据结构树和二叉树遍历二叉树和线索二叉树》由会员分享，可在线阅读，更多相关《数据结构树和二叉树遍历二叉树和线索二叉树（52页珍藏版）》请在金锄头文库上搜索。
1、武汉科技大学Wuhan University of Science and Technology数据结构数据结构 Data StructuresData Structures张 凯 计算机学院 软件工程系2011年3月12日树和森林第6章 树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用v提出问题6.3 遍历二叉树和线索二叉树在二叉树的一些应用中，常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了遍历二叉树的问题。v遍历是任何类型均有的操作6.3 遍历二叉树和线索二叉树对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)；而二叉树是非
2、线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。v遍历二叉树6.3 遍历二叉树和线索二叉树对二叉树而言，是由三个基本单元组成：根结点、左子树和右子树。因此，若能遍历这三部分，便是遍历了整个二叉树。考虑：一共有多少种遍历二叉树的方案？v遍历二叉树6.3 遍历二叉树和线索二叉树假如以 L、D、R 分别表示遍历二叉树的左子树、访问根结点、遍历右子树，则有 D L R 、L D R 、L R DD R L 、R D L 、R L D 先序 中序 后序六种遍历方案选择v先左后右的遍历算法6.3 遍历二叉树和线索二叉树 先（根）序遍历算法 DLR 中（根）序遍历算法 LDR
3、后（根）序遍历算法 LRDv先（根）序遍历算法6.3 遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。void PreOrderTraverse(BiTree bt) if(bt)printf(“%c “, bt-data); /*输出根结点数据域的值*/PreOrderTraverse(bt-lchild); /*先序遍历左子树*/PreOrderTraverse(bt-rchild); /*先序遍历右子树*/ v中（根）序遍历算法6.3 遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1) 中序遍历左子树；(2)
4、 访问根结点；(3) 中序遍历右子树。void InOrderTraverse(BiTree bt) if(bt)InOrderTraverse(bt-lchild); /*中序遍历左子树*/printf(“%c “, bt-data); /*输出根结点数据域的值*/InOrderTraverse(bt-rchild); /*中序遍历右子树*/ v后（根）序遍历算法6.3 遍历二叉树和线索二叉树若二叉树为空树，则空操作；否则(1) 后序遍历左子树；(2) 后序遍历右子树；(3) 访问根结点。void PostOrderTraverse(BiTree bt) if(bt)PostOrderTra
5、verse(bt-lchild);/*后序遍历左子树*/PostOrderTraverse(bt-rchild); /*后序遍历右子树*/printf(“%c “, bt-data); /*输出根结点数据域的值*/ v例16.3 遍历二叉树和线索二叉树先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：A B CD EA B D E CD B E A CD E B C A口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根v例2：用二叉树表示算术表达式6.3 遍历二叉树和线索二叉树+*A*/EDCB先序遍历 + * * / A B C D E 前缀
6、表示中序遍历 A / B * C * D + E 中缀表示后序遍历 A B / C * D * E + 后缀表示层序遍历 + * E * D / C A Bv例36.3 遍历二叉树和线索二叉树假设一棵二叉树的先序序列为 E B A D C F H G I K J，中序序列为 A B C D E F G H I J K。画出该二叉树。v遍历算法的递归实现6.3 遍历二叉树和线索二叉树回忆1：二叉树结点的数据类型定义： typedef struct node *tree_pointer; typedef struct node int data;tree_pointer left_child, r
7、ight_child; node;回忆2：递归求解 n! long int fact(n) /求n! long s;if (n1) s=n*fact(n-1);else f=1;return(f); v先序遍历二叉树的递归算法6.3 遍历二叉树和线索二叉树Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e) /二叉链表存储结构，visit是对数据元素操作的应用函数 /先序遍历二叉树T的递归算法，对每个数据元素调用visitif(T)if (Visit(T-data)if ( PreOrderTraverse(T-lchild
8、,Visit )if (PreOrderTraverser(T-rchild,Visit) return OK;return ERROR; else return OK; PreOrderTraverseACBD主程序Pre( T )Pre(T R);Pre(T R);TAVisit(A); Pre(T L);TDVisit(D); Pre(T L);TCVisit(C); Pre(T L);TBVisit(B); Pre(T L);返回TPre(T R);返回T返回T返回T返回TPre(T R);得到的遍历次序为：A B D CPreOrderTraverse(BiTree T,Status
9、(* Visit)(TElemType e) if(T)if (Visit(T-data)if ( PreOrderTraverse(T-lchild,Visit )if (PreOrderTraverser(T-rchild,Visit) return OK;return ERROR; else return OK; v中序遍历二叉树的递归算法6.3 遍历二叉树和线索二叉树Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if(T) if ( InOrderTraverse(T-lchild,Visit) )if (V
10、isit(T-data)if ( InOrderTraverse(T-rchild,Visit) ) return OK;return ERROR; else return OK;/ InOrderTraversev后序遍历二叉树的递归算法6.3 遍历二叉树和线索二叉树Status PostOrderTraverse(BiTree T ,Status(* Visit)(TElemType e) if(T) if ( PostOrderTraverse(T-lchild ,Visit) )if ( PostOrderTraverse(T-rchild ,Visit) )if (Visit(T-d
11、ata) return OK;return ERROR; else return OK;/PostOrderTraversev遍历历的分析6.3 遍历二叉树和线索二叉树1. 从前面的三种遍历算法可以知道：如果将 print语句抹去，从递归的角度看，这三种算法 是完全相同的，或者说这三种遍历算法的访问 路径是相同的，只是访问结点的时机不同。从虚线的起点到终点，每个结点经过3次AFEDCBG第1次经过时访问先序遍历 第2次经过时访问中序遍历 第3次经过时访问后序遍历2. 二叉树遍历的时间效率和空间效率 时间效率:O O( (n n) ) /每个结点只访问一次 空间效率:O O( (n n) ) /
12、栈占用的最大辅助空间v中序遍历历二叉树树的非递归递归 算法一6.3 遍历二叉树和线索二叉树Staus InOrderTrav(BiTree T,Status(* Visit)(TElemType e) /中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit. InitStack(S); Push(S,T); /根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)/向左走到尽头Pop(S,p); /空指针退栈if(!StackEmpty(S) /访问结点，向右一步Pop(S,p); if(!Visit(p-data) return error;Push
13、(S,p-rchild); /if /while Return ok; /InOrderTraverseACBEDv中序遍历历二叉树树的非递归递归 算法二6.3 遍历二叉树和线索二叉树Status InOrderTrv( BiTree T,Status (*Visit)(TElemType e) /采用二叉链表存储结构，Visit是对数据元素操作的应用函数 /中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S); p=T;while(p | !StackEmpty(S)if (p) Push( p=p-lchild; else Pop(if (!Visit
14、(p-data) return ERROR；p=p-rchild; /else /whilereturn OK; /InOrderTrv/根指针进栈，遍历左子树 /根指针退栈，访问根结点，遍历右子树 ACBEDv遍历历算法的应应用举举例6.3 遍历二叉树和线索二叉树“遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树求结点的双亲，求结点的孩子结点，判定结点所在的层次等。v例1：统计统计 二叉树树中叶子结结点的个数6.3 遍历二叉树和线索二叉树Status CountLeaf (BiTree T, int return OK; CountLeaf( T - lc
15、hild, count); / 统计左子树中叶子结点个数CountLeaf( T - rchild, count); / 统计右子树中叶子结点个数 else return ERROR; v例2：求二叉树树的深度6.3 遍历二叉树和线索二叉树int Depth (BiTree T ) if ( !T ) depthval = 0;else depthLeft = Depth( T-lchild );depthRight= Depth( T-rchild );depthval = 1 + max(depthLeft,depthRight);return depthval;v例3：按先序序列建立二叉树树的二叉链链表6.3 遍历二叉树和线索二叉树已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0 （其中0表示空格字符, 空指针）建立相应的二叉链表ABCDEFGv例3：按先序序列建立二叉树树的二叉链链表6.3 遍历二叉树和线索二叉树Status CreateBiTree (BiTree else if( !( T=(BiTNode*)malloc(sizeof(
