3.a)出队列取得一个结点指针,访问该结点; (3.b)若该结点的左子树非空,则将该结点的左子树指针入 队列; (3.c)若该结点的右子树非空,则将该结点的右子树指针入 队列; (4)结束。 注意:一个二又树的遍历序列不能决定一棵二叉树,但先 序(或后序)和中序遍历序列的组合可以惟一确定一棵二叉 树。而先序和后序遍历则不能
6 (3.a)出队列取得一个结点指针，访问该结点； (3.b)若该结点的左子树非空，则将该结点的左子树指针入 队列； (3.c)若该结点的右子树非空，则将该结点的右子树指针入 队列； （4）结束。 注意：一个二叉树的遍历序列不能决定一棵二叉树，但先 序（或后序）和中序遍历序列的组合可以惟一确定一棵二叉 树。而先序和后序遍历则不能
例1: 先序遍历的结果是: ABD E O 中序遍历的结果是: D BE AC B 后序遍历的结果是: DEBCA 口诀: DLR一先序遍历,即先根再左再右 LDR一中序遍历,即先左再根再右 LRD一后序遍历,即先左再右再根
7 例1： 先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是： A B C D E D B E A C D E B C A 口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根 A B D E C
例2:用二叉树表示算术表达式先序遍历结果 +**/abcde 前缀表示法 E 中序遍历结果 A/B *c*d+e D 一中缀表示法 后序遍历结果 AB/CAdre+ 后缀表示法 A B 层次遍历结果 +REd/CaB
8 + * A * / E D C B 先序遍历结果 + * * / A B C D E —前缀表示法 中序遍历结果 A / B * C * D + E —中缀表示法 后序遍历结果 A B / C * D * E + —后缀表示法 层次遍历结果 + * E * D / C A B 例2：用二叉树表示算术表达式