24、先序遍历序列为ABC，后序遍历序列为CBA的二叉树共有 棵。A．1B．2C．3D．4
24、先序遍历序列为ABC，后序遍历序列为CBA的二叉树共有 棵。
A．1
B．2
C．3
D．4
参考答案和解析
(1)先序遍历。 void PreOrderTraverse(BiTree bt){ ／*二叉树bt采用二叉链表存储对其进行先序遍历*／if(bt) ／*二叉树非空*／{InitStack(S)；Push(Sbt)； while(!EmptyStack(S)) {while(GetTop(Sp)&&p) ／*当栈顶元素非空*／ {visit(p一>data)； push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)) ／*若栈非空使栈顶元素的右孩子人栈*／ {Pop(Sp)；Push(SP一>rchild)；) } }}(2)中序遍历。void InOrderTraverse(BiTree bt){ ／*二叉树bt采用二叉链表存储对其进行中序遍历*／ if(bt) {InitStack(s)；Push(sbt)； while(!EmptyStack(S)) {while(GetTop(Sp)&&p) push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)) {Pop(SP)； visit(p一>data)； Push(SP一>rchild)； } } }}(3)后序遍历。voidFeorder(BiTreebt){ ／*后序遍历bt所指的二又树s为存储二叉树结点指针的栈*／ InitStack(S)；Push(Sbt)； while(!EmptyStack(S)) {while(GetTop(SP)) Push(SP一>ichild)； Pop(SP)； if(!EmptyStack(S)){Push(SGetTop(Sp)一>rchild)； if(GetTop(sP)==NULL) {Pop(sP);Pop(sP); visit(P一>data); while(GetTop(sq)一>rchild==p&&!EmptyStack(s)) {Pop(sP); visit(P一>data); } if(!EmptyStack(s)) Push(sGetTop(sP)一>rchild); } } }} 将一个递归算法转换成一个非递归算法，利用栈就可消除递归，根据对二叉树进行先序、中序和后序遍历的思想，其非递归算法描述如下。
相关考题：
●若一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 (38) 。(38) A．ABDEGHJFICB．ABDEGHJCFIC．ABCDEFGHIJD．ABDEGJHCFI
● 已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 （57） 。对于任意一棵二叉树，叙述错误的是 （58） 。（57）A. ②、③、①、⑤、④B. ①、②、③、④、⑤C. ②、④、⑤、③、①D. ④、⑤、③、②、①（58）A. 由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B. 由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C. 由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列D. 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列
已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为( )。对于任意一棵二叉树，叙述错误的是( )。A．②、③、①、⑤、④B．①、②、③、④、⑤C．②、④、⑤、③、①D．④、⑤、③、②、①
若一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为(38)。A．ABDEGHJFICB．ABDEGHJCFIC．ABCDEFGHIJD．ABDEGJHCFI
一棵二叉树的中序遍历序列为DBGEUJOCIF，后序遍历序列为DCJHEBIPCO，则其前序遍历序列为(87)。A．OBCDEFGHIJB．OBDEGHJCFIC．OBDEGHJPICD．OBDECJHCFI
单选题若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为（）ADEBAFCBDEFBCACDEBCFADDEBFCA