二叉树的三种遍历（非递归）

二叉树的三种遍历（非递归）

由于下大雨在宿舍偷懒，剩不到一个月考研了很焦虑怎么办！QAQ

顺便在这里很粗略的写写二叉树的三种遍历算法（非递归） ，不知道会不会考到呢、、o(´^｀)o

图1：示例二叉树

先序遍历：12354

中序遍历：32514

后序遍历：35241

--------------------------------------------------------------------------先序遍历-------------------------------------------------------------------------------

先直接上代码：

/* 思路： 1.根结点入栈 2.当栈不空时 循环{ 出栈并输出栈顶结点，然后将其左右孩子入栈 右孩子先入栈，左孩子后入栈 （保证左孩子先出栈访问） } */void preorderNonrecursion(BTNode *bt){ if(bt!=NULL) { BTNode *Stack[maxsize]; int top=-1; BTNode *p; Stack[++top]=bt; //根结点入栈 while(top!=-1) { p=Stack[top--]; //出栈并输出栈顶结点 Visit(p); if(p->rchild!=NULL) Stack[++top]=p->rchild; if(p->lchild!=NULL) Stack[++top]=p->lchild; } } }

算法步骤详解：

初始栈均为空。

①：根结点1入栈。

②：栈顶元素（1）出栈，并访问。将其左右孩子入栈，右孩子（4）先入栈，左孩子（2）后入栈.

③：栈顶元素（2）出栈，并访问。将其左右孩子入栈，右孩子（5）先入栈，左孩子（3）后入栈.

④：栈顶元素（3）出栈，并访问。无孩子结点。

⑤：栈顶元素（5）出栈，并访问。无孩子结点。

⑥：栈顶元素（4）出栈，并访问。无孩子结点。

此时依次访问结点序列为12354，即先序遍历序列。

图2：先序遍历结点进出栈过程

--------------------------------------------------------------------------中序遍历-------------------------------------------------------------------------------

/*思路：1.根结点入栈。 2.循环操作：若栈顶结点左孩子存在，则左孩子入栈。左孩子不存在，则出栈并输出栈顶结点。 然后检查其右孩子是否存在，若存在，则入栈。 3.栈为空时算法结束。 */void inorderNoncursion(BTNode *bt){if(bt!=NULL) { BTNode *Stack[maxsize]; int top=-1; BTNode *p; p=bt; while(top!=-1||p!=NULL)//特殊情况 { while(p!=NULL) //左孩子存在，左孩子入栈 { Stack[++top]=p; p=p->lchild; } if(top!=-1) //在栈不空的情况下出栈并输出出栈结点

算法步骤详解：

初始栈均为空。

①：根结点1入栈。1左孩子存在。

②：结点2入栈。2左孩子存在。

③：结点3入栈。3左孩子不存在。

④：栈顶元素（3）出栈，输出栈顶元素，3右孩子不存在。

⑤：栈顶元素（2）出栈，输出栈顶元素，2右孩子存在（5），入栈。5左孩子不存在。

⑥：栈顶元素（5）出栈，输出栈顶元素，5右孩子不存在。

⑦：栈顶元素（1）出栈，1右孩子存在（4），入栈。4左孩子不存在。

栈顶元素（4）出栈，输出栈顶元素，此时栈空，进入终态。

此时依次输出结点序列为32514，即中序遍历序列。

图3：中序遍历结点进出栈过程

--------------------------------------------------------------------------后序遍历-------------------------------------------------------------------------------

/*思路：1.定义两个栈，从根结点开始 2.循环{ 当前结点入栈ST1,ST1栈顶元素出栈，并将出栈结果入栈ST2 若当前结点的左右孩子存在，依次入栈ST1 } */void postorderNoncursion(BTNode *bt){ if(bt!=NULL) { BTNode *Stack1[maxsize]; int top1=-1; BTNode *Stack2[maxsize]; int top2=-1; BTNode *p=NULL; Stack1[++top1]=bt; while(top1!=-1) { p=Stack1[top1--]; //从Stack1中出栈进入Stack2中 Stack2[++top2]=p; if(p->lchild!=NULL) Stack1[++top1]=p->lchild; if(p->rchild!=NULL) Stack1[++top1]=p->rchild; } while(top2!=-1) { p=Stack2[top2--]; Visit(p); } } }

算法步骤详解：

设立两个栈，记为ST1和ST2。初始两个栈均为空。

①：根结点1入栈ST1。

②：ST1栈顶元素（1）出栈，并将其入栈ST2。若该元素左右孩子存在，依次入栈ST1。（左孩子为2，右孩子为4，依次入栈）

③：ST1栈顶元素（4）出栈，并将其入栈ST2。该元素不存在孩子结点。

④：ST1栈顶元素（2）出栈，并将其入栈ST2。若该元素左右孩子存在，依次入栈ST1。（左孩子为3，右孩子为5，依次入栈）

⑤：ST1栈顶元素（5）出栈，并将其入栈ST2。该元素不存在孩子结点。

⑥：ST1栈顶元素（3）出栈，并将其入栈ST2。该元素不存在孩子结点。

此时ST1栈为空，ST2栈自顶向下依次为：35241，即后序遍历序列。

图4：后序遍历结点进出栈ST1过程

图5：后序遍历结点进出栈ST2过程

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。