一步两步学算法之树的遍历非递归实现

浏览数：17 / 时间：2015年06月08日

递归的程序其实我觉得可读性较高但是执行效率低下

为了做一道PAT的题去理解了下非递归实现树的遍历

用一个栈来实现

先序遍历

先访问节点再把节点push进栈再访问再push 直到next=NULL

然后pop出一个节点也就是弹出一个节点访问它的右边再弹出在访问

中序遍历

把左边节点全部push进栈然后弹出访问中间再访问右边再弹出一直循环

后序遍历

比较难理解要入两次栈才能访问先左边全部入栈栈顶是左边的元素此书不能访问因为右边还没入栈

下面给出先序和后序的代码后序的代码记得调试下看看不然很难理解

给出一张图片便于理解来自c语言中文网

技术分享

void  NRpreOrder(BiTree bt)
{
    BiTree stack[MXSNODE],p;
    int top;
    if(bt==NULL)
        return;
    top=0;
    p=bt;
    while(!(p==NULL &&top==0))
    {
        while(p!=NULL)
        {
            visit(p->data); //访问节点数据
            if(top<MAXNODE-1)
            {
                stack[top]=p;    //访问后的节点进栈 
                top++;            
            } 
            else
            {
                printf("栈溢出");
                return; 
            }
            p=p->left;            //指向下一个 
        }
        if(top<=0)
            return;
        else{
            top--;
            p=stack[top];        //弹出节点 
            p=p->right;            //指向右边 
        }
    }
}

 1 #include "stdio.h"
 2 #define MXSNODE 10
 3 typedef struct Bitree
 4 {
 5     int data;
 6     struct Bitree *left;
 7     struct Bitree *right;
 8 }BiTree;
 9 
10 typedef struct
11 {
12     BiTree *link;
13     int flag;
14 }stacktype;
15 
16 void  NRpreOrder(BiTree *bt)
17 {
18     stacktype stack[MXSNODE];
19     BiTree *p;
20     int top,sign;
21     if(bt==NULL)
22         return;
23     top=-1;
24     p=bt;
25     while(!(p==NULL &&top==-1))
26     {
27         if(p!=NULL)
28         {
29             top++;
30             stack[top].link=p;
31             stack[top].flag=1;
32             p=p->left;
33         }
34         else
35         {
36             p=stack[top].link;
37             sign=stack[top].flag;
38             top--;
39         
40             if(sign==1)
41             {
42                 top++;
43                 stack[top].link=p;
44                 stack[top].flag=2;
45                 p=p->right;
46             }
47             else{
48                 printf("%d",p->data);
49             }
50         }
51     }
52 }