6.3.5中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2.给定二叉树T的 后序序列: BGHECAJIFD 中序序列: BACGEHDIJF 如何求二叉树T? B AC G,E H 二叉树T
6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2. 给定二叉树T的 后序序列：B G H E C A J I F D 中序序列：B A C G E H D I J F 如何求二叉树T？ D B,A,C G,E,H I,J,F D A F B C I E G H J 二叉树T
6.3.6中序遍历非递归算法 ≯递归算法简明精炼,但效率较低,实际应用中常使用 非递归; 某些高级语言不支持递归; 非递归算法思想: (1)设置一个栈S存放所经过的根结点(指针)信息; 初始化S (2)第一次访问到根结点并不访问,而是入栈 (3)中序遍历它的左子树,左子树遍历结束后,第二 次遇到根结点,就将根结点(指针)退栈,并且访问 根结点;然后中序遍历它的右子树 (4)当需要退栈时,如果栈为空则结束
6.3.6 中序遍历非递归算法 ➢ 递归算法简明精炼，但效率较低，实际应用中常使用 非递归； ➢ 某些高级语言不支持递归； ➢ 非递归算法思想： （1）设置一个栈S存放所经过的根结点（指针）信息； 初始化S； （2）第一次访问到根结点并不访问，而是入栈； （3）中序遍历它的左子树，左子树遍历结束后，第二 次遇到根结点，就将根结点（指针）退栈，并且访问 根结点；然后中序遍历它的右子树。 （4） 当需要退栈时，如果栈为空则结束
C根进栈 A D)(E A 根进栈 根进栈 B t B C DBA t=NULL,表示D的左子 树遍历结束
A B C D E t A A B C D E t B A A B C D E t D B A A B C D E t=NULL,表示D的左子 树遍历结束 根进栈 根进栈 根进栈
D 退栈→t,访问D, B (B t-> rchild→t B ①E t=NULL,表示D的左子 t=NULL,表示B的左子 树遍历结束 树遍历结束 退栈→t,访问B A 根进栈 A t-> rchild→t E B A DB t=NULL,表示E的左子 树遍历结束
D B A A B C D E 退栈➔t，访问D， t->rchild➔t B A A B C D E t=NULL,表示B的左子 树遍历结束 退栈➔t，访问B， t->rchild➔t E A A B C D E A B C A D E t 根进栈 t=NULL,表示E的左子 树遍历结束 D D B t=NULL,表示D的左子 树遍历结束
退栈→t,访问E, E (B t-> rchild→t B t=NULL,表示E的左子 t=NULL,表示A的左子 树遍历结束 树遍历结束 退栈→t,访问A, A 根进栈 A t-> rchild→t B DBE t=NULL,表示C的左子 树遍历结束
E A A B C D E 退栈➔t，访问E， t->rchild➔t A A B C D E t=NULL,表示A的左子 树遍历结束 退栈➔t，访问A， t->rchild➔t C A B C D E A B C D E t 根进栈 t=NULL,表示C的左子 树遍历结束 D B E D B E A t=NULL,表示E的左子 树遍历结束