试给出二叉树的自下而上 自右而左的层次遍历算法。
-
正确答案：题目要求的次序与层次遍历次序刚好相反因此我们可以得到这样一个思路：首先用层次遍历的方法遍历二叉树同时将被访问到的结点压入栈中最后将栈中所有元素出栈根据栈的后进先出特性我们就可以得到题目所要的遍历顺序。 void InvertLevel(BinTree bt){ //对二叉树按自下而上、自右向左进行层次遍历 if(bt!=NULL){ Stacklnit(s)； Queuelnit(Q)； Enqueue(Qbt)； while(!QueueEmpty(Q)){ p=Dequeue(Q)； push(Sp)； if(p->lchild) Enqueue(Qp->lchild)； if(p->rchild) Enqueue(Qp->rchild)； }//endwhile while(!StackEmpty(s)){ p=pop(s)； printf(p->data)： } }//endif }
题目要求的次序与层次遍历次序刚好相反,因此我们可以得到这样一个思路：首先用层次遍历的方法遍历二叉树,同时将被访问到的结点压入栈中,最后将栈中所有元素出栈,根据栈的后进先出特性,我们就可以得到题目所要的遍历顺序。voidInvertLevel(BinTreebt){//对二叉树按自下而上、自右向左进行层次遍历if(bt!=NULL){Stacklnit(s)；Queuelnit(Q)；Enqueue(Q,bt)；while(!QueueEmpty(Q)){p=Dequeue(Q)；push(S,p)；if(p->lchild)Enqueue(Q,p->lchild)；if(p->rchild)Enqueue(Q,p->rchild)；}//endwhilewhile(!StackEmpty(s)){p=pop(s)；printf(p->data)：}}//endif}