二叉树：层次遍历算法（自下而上，从右到左） |
您所在的位置：网站首页 › 二叉树按层遍历ACM › 二叉树：层次遍历算法（自下而上，从右到左） |
二叉树：层次遍历算法（自下而上，从右到左）
|
和上一个算法：二叉树：层次遍历算法（自上而下，从左到右）类似，是在上一个的基础上完成的，上一个是自上而下，从左到右，是默认的层次遍历算法。 而与之相反的，本题是自下而上，从右到左的层次遍历，需要借助队列和栈来完成。 分析： 如图，先将根结点A入队，此时栈为空。 算法思想：一般的二叉树层次遍历是自上而下，从左到右，这里的遍历顺序则恰好相反。利用原有的层次遍历算法，出队的同时将各个结点指针入栈，在所有结点入栈之后再从栈顶开始依次访问所有结点直到栈为空，就结束。 大致步骤总结： 1、把根结点入队； 2、把一个元素出队列，遍历这个元素； 3、依次把这个元素的左孩子、右孩子入队； 4、如果队列不为空，就执行第二步，如果队列为空，就结束。 代码： void Invert_Level(BiTree T){ InitStack(s); // 初始化栈s InitQueue(Q); // 初始化队列Q BiTree *p; // 初始化工作指针p，用来循环过程中指向结点 if(T!=NULL){ EnQueue(Q,T); // 将根节点入队 while(!IsEmpty(Q)){ // !xx和xx==false含义一样 // 此处循环条件写成IsEmpty(Q)==false也可以 // 从while开始是正常的自上而下的层次遍历，队列不空则循环，多了个入栈 DeQueue(Q,p); // 队头结点出队 push(s,p); // 队头结点入栈 if(p->lchild!=NULL) // 如果左孩子不为空 EnQueue(Q,p->lchild); // 就将左孩子入队 if(p->rchild!=NULL) // 如果右孩子不为空 EnQueue(Q,p->rchild); // 就将右孩子入队 } // 上面循环结束，队列中序列为ABCDEFG，即自上而下，从左到右的层次遍历 while(!IsEmpty(s)){ // 栈不空则循环 // 因为上面的while全部判断完后栈中序列为GFEDCBA， // 所以依次出栈即为最终所求，即自下而上，从右到左的层次遍历序列 pop(s,p); // 将p出栈 visit(p->data); // 访问p所指结点的值 } } } |
然后队头结点A出队，并访问A，然后把A入栈。此时发现A有左右孩子，然后把左右孩子BC入队。此时栈中只有A。 
然后队头结点B出队，并访问B，然后把B入栈。此时发现B有左右孩子，然后把左右孩子DE入队。此时栈中有AB。
然后队头结点C出队，并访问C，然后把C入栈。此时发现C有左右孩子，然后把左右孩子FG入队。此时栈中有ABC。 
然后队头结点D出队，并访问D，然后把D入栈。此时发现D没有左右孩子，就继续将队头结点E出队，并访问E，然后把E入栈。此时发现E没有左右孩子，FG同理。 队列为空，结束。此时栈中有ABCDEFG，然后将栈的元素依次出栈即为最终结果。 
【本文地址】
今日新闻 |
推荐新闻 |