第六章数据.ppt

6.4 二叉树的遍历 一、问题的提出 二、先左后右的遍历算法 三、算法的递归描述 四、中序遍历算法的非递归描述 五、遍历算法的应用举例 顺着某一条有哪些信誉好的足球投注网站路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。 一、问题的提出 “访问”的含义可以很广，如：输出结 点的信息等。 “遍历”是任何类型均有的操作， 对线性结构而言，只有一条有哪些信誉好的足球投注网站路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的有哪些信誉好的足球投注网站 路径遍历的问题。 对“二叉树”而言，可以有三条有哪些信誉好的足球投注网站路径： 1．先上后下的按层次遍历； 2．先左（子树）后右（子树）的遍历； 3．先右（子树）后左（子树）的遍历。 二、先左后右的遍历算法 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 先（根）序的遍历算法： 1 2 4 5 3 6 124536 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 中（根）序的遍历算法： 1 2 4 5 3 6 425136 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 后（根）序的遍历算法： 1 2 4 5 3 6 452631 三、算法的递归描述 Status Preorder (BiTree T, Status( *visit)(TElemType e)) { // 先序遍历二叉树 if (T) { if((*visit)(T-data)) // 访问根结点 if(Preorder(T-lchild, visit)) // 遍历左子树 if(Preorder(T-rchild, visit))// 遍历右子树 return OK; return ERROR; }else return OK; } //PreorderTraverse 1 2 4 5 3 6 void Preorder (BiTree T, void ( *visit)(TElemType e)) { // 先序遍历二叉树 if (T) { (*visit)(T-data); // 访问根结点 Preorder(T-lchild, visit); // 遍历左子树 Preorder(T-rchild, visit); // 遍历右子树 } } //PreorderTraverse 同理，中序遍历如下： void InOrderTraverse(BiTreeT, void(* visit)(TElemType)){ if(T){ InOrderTraverse(T-lchild,visit); (*visit)(T-data); InOrderTraverse(T-rchild,visit); } } 后序遍历呢 ？ 四、中序遍历算法的非递归描述 BiTNode *GoFarLeft(BiTree T, Stack S){ if(!T) return NULL; while(T-lchild){ Push(S, T); T=T-lchild; } return T; }//找到T树中最左孩子的指针，用指针T返回 //非递归中序遍历的算法 void InOrderTraverse(BiTree T, void(*visit)(TElemType e)){ Stack S; t=GoFarLeft(T,S); //找到最左下的结点 while(t) { visit(t-data); if(t-rchild) t=GoFarLeft(t-rchild, S); else if(!StackEmpty(S)) //栈不空时退栈