Chapter8-2二叉树的遍历课件.ppt

1、LOGO1LOGO2LOGO3LOGO4LOGO5LOGO6LOGO7深度优先遍历深度优先遍历LOGO8前序序列的第一个元素前序序列的第一个元素必为二叉树的根节点必为二叉树的根节点LOGO9LOGO10中序序列的中序序列的根节点根节点恰为恰为左右子树的中序序列的左右子树的中序序列的分界分界点点LOGO11LOGO12后序序列的后序序列的最后最后一个元素一个元素必为二叉树的必为二叉树的根节点根节点LOGO13LOGO14LOGO15LOGO16LOGO17LOGO18LOGO19LOGO20toptopT1BAtopT2AtopT3topET3topT4LOGO21LOGO22LOGO23LOG

2、O24LOGO25LOGO26LOGO27LOGO28结论结论LOGO29LOGO30LOGO31LOGO32n n LOGO33LOGO34LOGO35LOGO36LOGO37LOGO38LOGO39LOGO40时间复杂度时间复杂度(n)(n)LOGO41时间复杂度时间复杂度(n)(n)LOGO42时间复杂度时间复杂度(n)(n)LOGO43时间复杂度时间复杂度(n)(n)LOGO44调用示例调用示例1234LOGO45LOGO46LOGO47时间复杂度时间复杂度(n)(n)LOGO48时间复杂度时间复杂度(n)(n)LOGO49时间复杂度时间复杂度(n)(n)LOGO50时间复杂度时间复杂

3、度(n)(n)LOGO51LOGO52LOGO53LOGO54Preorder sequence is 4 3 1 2Inorder sequence is 1 3 2 4Postorder sequence is 1 2 3 4Level order sequence is 4 3 1 2Number of nodes=4Height=3Count of nodes is 41234LOGO55二叉树遍历的非递归算法v 递归算法转换为等价的非递归算法，使用递归算法转换为等价的非递归算法，使用“栈栈”v 以前序为例：根以前序为例：根-左左-右，左下降右，左下降 abcdev 思考：如果能在左下

4、降的过程中，记录留待以后思考：如果能在左下降的过程中，记录留待以后访问的右子树的根结点，以便在遍历完一个结点的左访问的右子树的根结点，以便在遍历完一个结点的左子树后能转移到这个结点的右子树，即可实现！子树后能转移到这个结点的右子树，即可实现！LOGO56非递归前序遍历二叉树v主要思想：每遇到一个结点，先访问该结点，并主要思想：每遇到一个结点，先访问该结点，并把把该结点的该结点的非空非空右子结点压入栈中右子结点压入栈中，然后遍历其左子，然后遍历其左子树；当左子树为空时，从栈顶弹出待访问的结点，树；当左子树为空时，从栈顶弹出待访问的结点，继续遍历。继续遍历。abcde访问访问a进栈进栈c左进左进b

5、访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 c dc c 结束结束LOGO57算法描述void PreOrder(BinTree T)stack S;InitStack(&S);/递归工作栈递归工作栈 BinTreeNode*p=T;Push(&S,NULL);while(p!=NULL)cout data rightChild!=NULL)Push(&S,p-rightChild);if (p-leftChild!=NULL)p=p-leftChild;/进左子树进左子树 else Pop(&S,p);LOGO

6、58非递归中序遍历二叉树v主要思想：主要思想：每遇到一个每遇到一个非空非空结点就把它压入栈结点就把它压入栈，然，然后去遍历其左子树；遍历完左子树后，从栈中弹出后去遍历其左子树；遍历完左子树后，从栈中弹出并访问这个结点，然后再去访问该结点的右子树。并访问这个结点，然后再去访问该结点的右子树。abcdebaa b入栈入栈ab退栈退栈访问访问dad入栈入栈ad退栈退栈访问访问a退栈退栈访问访问ecc e 入栈入栈ce e 退栈访问退栈访问c c 退栈访问退栈访问栈空栈空LOGO59非递归后序遍历二叉树v主要思想：每遇到一个非空结点，先把它压入栈，主要思想：每遇到一个非空结点，先把它压入栈，然后去遍历

7、其左子树；遍历完其左子树后，应继续然后去遍历其左子树；遍历完其左子树后，应继续遍历该结点的右子树；遍历完右子树之后，才从栈遍历该结点的右子树；遍历完右子树之后，才从栈中弹出并访问这个结点。中弹出并访问这个结点。v后序遍历二叉树：左子树后序遍历二叉树：左子树-右子树右子树-当前节点当前节点v需要注意：访问某个结点之前，需要知道是否已经需要注意：访问某个结点之前，需要知道是否已经访问该结点的右子树，因此需要给结点加一个标志访问该结点的右子树，因此需要给结点加一个标志位位tag，Left：表示已经进入该结点的左子树：表示已经进入该结点的左子树 Right：表示已经进入该结点的右子树：表示已经进入该结

8、点的右子树LOGO60后序遍历时使用的栈的结点定义后序遍历时使用的栈的结点定义typedef struct BinTreeNode*ptr;/结点指针结点指针 enum tag L,R;/该结点退栈标记该结点退栈标记 StackNode;根结点的根结点的 tag=L，表示从左子树退出，表示从左子树退出,访问右子树。访问右子树。tag=R,表示表示从右子树退出从右子树退出,访问根。访问根。LOGO61void PostOrder(BinTree T)stack S;InitStack(&S);StackNode w;BinTreeNode*p=T;do while(p!=NULL)/向左子树走向左子树走 w.ptr=p;w.tag=L;Push(&S,w);p=p-leftChild;int continue=1;/继续循环标记继续循环标记LOGO62while(continue&!StackEmpty(&S)Pop(&S,w);p=w.ptr;switch(w.tag)/判断栈顶判断栈顶tag标记标记 case L:w.tag=R;Push(&S,w);continue=0;p=p-rightChild;break;case R:cout data endl;while(p!=NULL|!StackEmpty(&S);cout endl;