二叉树遍历的非递归实现.ppt

《二叉树遍历的非递归实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.2.5二叉树遍历的非递归实现p.106中序遍历的非递归算法：在中序遍历时，遇到一个结点，就把它入栈，并去遍历它的左子树；遍历完左子树后，从栈顶弹出这个结点并访问之，然后再去遍历该结点的右子树。算法4.7中序遍历的非递归算法。voidInOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&p=root){BinaryTreeNode*t=p;Stackstack;while(t

2、

3、!stack.Empty()){if(t){stack.Push(t);t=t->leftChild;}e

4、lse{t=stack.Pop();Visit(t);t=t->rightChild;}}//while}//InOrderp=roott=pt=stack.Pop()Visit(t)t=t->rightChildstack.Push(t)t=t->leftChildt

5、

6、!stack.Empty()tYYNN算法流程图：举例说明：A^B^C^D^^E^root举例说明：A^B^C^D^^E^proottstack举例说明：A^B^C^D^^E^proott&Astack举例说明：A^B^C^D^^E^proott&Astack举例说明

7、：A^B^C^D^^E^proott&B&Astack举例说明：A^B^C^D^^E^proott&B&Astack举例说明：A^B^C^D^^E^proott&C&B&Astack举例说明：A^B^C^D^^E^proott=^&C&B&Astack举例说明：A^B^C^D^^E^proot&B&Astackt举例说明：A^B^C^D^^E^proot&B&AstacktC举例说明：A^B^C^D^^E^proot&B&Astackt=^C举例说明：A^B^C^D^^E^proot&AstackCt举例说明：A^B^C^D^^E^pr

8、oot&AstackCBt举例说明：A^B^C^D^^E^proot&AstackCBt举例说明：A^B^C^D^^E^proot&D&AstackCBt举例说明：A^B^C^D^^E^proot&D&AstackCBt举例说明：A^B^C^D^^E^proot&E&D&AstackCBt举例说明：A^B^C^D^^E^proot&E&D&AstackCBt=^举例说明：A^B^C^D^^E^proot&D&AstackCBt举例说明：A^B^C^D^^E^proot&D&AstackCBEt举例说明：A^B^C^D^^E^proot&

9、D&AstackCBEt=^举例说明：A^B^C^D^^E^proot&AstackCBEt举例说明：A^B^C^D^^E^proot&AstackCBEDt举例说明：A^B^C^D^^E^proot&AstackCBEDt=^举例说明：A^B^C^D^^E^prootstackCBEDt举例说明：A^B^C^D^^E^prootstackCBEDAt举例说明：A^B^C^D^^E^prootstackCBEDAt=^