六树与叉树遍历叉树.ppt

* * 数据结构 6.1 树的定义和基本术语 第六章 树和二叉树 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.5 赫夫曼树及其应用 6.4 树和森林 6.3 遍历二叉树和线索二叉树 一、遍历：按某种搜索路径访问二叉树的每个结 点，而且每个结点仅被访问一次。 树结构（非线性结构）→线性结构。 遍历的实质? A F G E D C B 6.3 遍历二叉树和线索二叉树 一、遍历：按某种搜索路径访问二叉树的每个结 点，而且每个结点仅被访问一次。 A F G E D C B 令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD 1.先序遍历 A B C D E F G I J 先序序列: A B D E J C F I 原则: 若被遍历的二叉树非空, 则 1. 访问根结点; 2. 以先序遍历原则遍历根结点的左子树; 3. 以先序遍历原则遍历根结点的右子树. G Flash 2.中序遍历 中序序列: D B J E A F I C 原则: 若被遍历的二叉树非空, 则 1. 以中序遍历原则遍历根结点的左子树; 2. 访问根结点; 3. 以中序遍历原则遍历根结点的右子树. G A B C D E F G I J Flash 3.后序遍历 后序序列: D J E B I F G C 原则: 若被遍历的二叉树非空, 则 1. 以后序遍历原则遍历根结点的左子树; 2. 以后序遍历原则遍历根结点的右子树； 3. 访问根结点。 A A B C D E F G I J Flash 二、遍历的算法描述 先序遍历 Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) { if (T) //非空树 {if(Visit(T-data)) if(PreOrderTraverse(T-lchild, Visit)) if(PreOrderTraverse(T-rchild, Visit)) return OK; }else return ERROR; }//PreOrderTraverse ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ T 指向函数的指针 P129 二、遍历的算法描述 先序遍历 Status PreOrderTraverse(BiTree T) { if (T) { Visit(T-data)； PreOrderTraverse(T-lchild, Visit) ； PreOrderTraverse(T-rchild, Visit)； return OK; }else return ERROR; }//PreOrderTraverse ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ T 改造算法 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A C B D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 二、遍历的算法描述 先序遍历 算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。 解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。 在前序遍历中，设要遍历二叉树的根指针为T，则有两种可能： ⑴ 若T!=NULL，则表明？如何处理？ ⑵ 若T=NULL，则表明？如何处理？ 非递归算法 二、遍历的算法描述 先序遍历 访问结点序列: A 栈S内容: B D A B 先序遍历的非递归实现 A D B C 二、遍历的算法描述 访问结点序列: A 栈S内容: B D A 先序遍历的非递归实现 A D B C