第四章树与树的表示(二).ppt

二叉树的遍历 遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。 二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。 若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是： DLR——先(根)序遍历。 LDR——中(根)序遍历。 LRD——后(根)序遍历。 对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用堆栈来实现的。 （1）先序遍历 遍历过程为： ① 访问根结点； A（B D F E ）（C G H I） ② 先序遍历其左子树； ③ 先序遍历其右子树。 先序遍历= A B D F E C G H I void PreOrderTraversal( BinTree BT ) { if( BT ) { printf(“%d”, BT-Data); 2 B 1 A 6 C } } PreOrderTraversal( BT-Left ); PreOrderTraversal( BT-Right ); 3 D 5 E 4 F 7 9 G 8 H I 5 6 （2）中序遍历 遍历过程为： （D B E F） A （G H C I） ① 中序遍历其左子树； ② 访问根结点； 中序遍历= D B E F A G H C I ③ 中序遍历其右子树。 A void InOrderTraversal( BinTree BT ) { } if( BT ) { InOrderTraversal( BT-Left ); printf(“%d”, BT-Data); InOrderTraversal( BT-Right ); } 1 D 3 B 2 E F 4 C 8 G 7 H 9 I A 9 2 I （3）后序遍历 遍历过程为： ① 后序遍历其左子树； ② 后序遍历其右子树； （D E F B ）（ H G I C） A ③ 访问根结点。 后序遍历= D E F B H G I C A void PostOrderTraversal( BinTree BT ) { } if( BT ) { PostOrderTraversal( BT-Left ); PostOrderTraversal( BT-Right); printf(“%d”, BT-Data); } 1 D B 4 F 3 E C 8 6 7 G 5 H 先序、中序和后序遍历过程：遍历过程中经过结点的路线一 样，只是访问各结点的时机不同。 图中在从入口到出口的曲线上用三种符号分别标记出了先序、 中序和后序访问各结点的时刻入口. B A 出口 C D E F G H I 二叉树的非递归遍历 中序遍历非递归遍历算法 非递归算法实现的基本思路：使用堆栈 B 入口 A 出口 C D E F G H I ?中序遍历非递归遍历算法 ? 遇到一个结点，就把它压栈，并去遍历它的左子树； ? 当左子树遍历结束后，从栈顶弹出这个结点并访问它； ? 然后按其右指针再去中序遍历该结点的右子树。 void InOrderTraversal( BinTree BT ) { BinTree T=BT; Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) ){ while(T){ /*一直向左并将沿途结点压入堆栈*/ Push(S,T); T = T-Left; } if(!IsEmpty(S)){ T = Pop(S); /*结点弹出堆栈*/ printf(“%5d”, T-Data); /*（访问）打印结点*/ T = T-Right; /*转向右子树*/ } } } 层序遍历 存储结构：队列 层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右” 访问树中的