深度优先遍历二叉树(DFS)

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 
  5 using namespace std;
  6 
  7 #define STACK_INIT_SIZE 30
  8 #define STACKINCREASE 10
  9 typedef char ElemType;
 10 typedef struct BiNode
 11 {
 12     ElemType data;
 13     struct BiNode *lchild,*rchild;
 14 }BiNode,*BiPtr;
 15 typedef struct
 16 {
 17     BiPtr *base;
 18     BiPtr *top;
 19     int stacksize;
 20 }SqStack;
 21 
 22 int InitStack(SqStack &S)
 23 {
 24     S.base = (BiPtr *)malloc(STACK_INIT_SIZE*sizeof(BiPtr));
 25     if(!S.base)
 26     {
 27         cout << "分配空间失败!";
 28         exit(-1);
 29     }
 30     S.top = S.base;
 31     S.stacksize = STACK_INIT_SIZE;
 32     return 0;
 33 }
 34 
 35 int Push(SqStack &S,BiPtr e)
 36 {
 37     if((S.top-S.base)>=STACK_INIT_SIZE)
 38     {
 39         S.base = (BiPtr *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREASE)*sizeof(BiPtr));
 40         if(!S.base)
 41         {
 42             cout << "分配空间失败!";
 43             exit(-1);
 44         }
 45         S.top = S.base + STACK_INIT_SIZE;
 46         S.stacksize = STACK_INIT_SIZE + STACKINCREASE;
 47     }
 48     *(S.top) = e;//结构体
 49     S.top++;
 50     return 0;
 51 }
 52 
 53 int Pop(SqStack &S,BiPtr &e)
 54 {
 55     if(S.base==S.top)
 56     {
 57         cout << "栈为空!";
 58         exit(0);
 59     }
 60     S.top--;
 61     e = *(S.top);
 62     return 0;
 63 }
 64 
 65 BiPtr GetTop(SqStack &S)
 66 {
 67     if(S.base==S.top)
 68     {
 69         cout << "栈为空!";
 70         return 0;
 71     }
 72     else return *(S.top-1);//返回一个指针
 73 }
 74 
 75 
 76 int EmptyStack(SqStack &S)
 77 {
 78     if(S.base==S.top) return 1;//stack is empty!
 79     else return 0;//stack is not empty!
 80 }
 81 
 82 //默认按前序遍历的顺序输入，尾结点用#表示
 83 int Create_BiTree(BiPtr& T)
 84 {
 85     ElemType c;
 86     //cout << "请输入当前节点元素值：" << endl;
 87     cin >> c;
 88     if(c == '#') T = NULL;
 89     else
 90     {
 91         T = new BiNode;
 92         T->data = c;
 93         Create_BiTree(T->lchild);
 94         Create_BiTree(T->rchild);
 95     }
 96     return 0;
 97 }
 98 
 99 //递归中序遍历二叉树
100 int InOrderTraverse(BiPtr T)
101 {
102     if(T)
103     {
104         InOrderTraverse(T->lchild);
105         cout << T->data << " ";
106         InOrderTraverse(T->rchild);
107     }
108     return 0;
109 }
110 //非递归中序遍历二叉树 方法1
111 int InOrderTraverse1(BiPtr T)
112 {
113     BiPtr p = T;
114     SqStack S;
115     InitStack(S);
116     Push(S,T);
117     while(!EmptyStack(S))
118     {
119         while(GetTop(S))
120         {
121             Push(S, p->lchild);
122             p = p->lchild;//不停的“向左下走”
123         }
124         Pop(S, p);//前面会“走过头”，所以弹出多入栈的空指针
125         if(!EmptyStack(S))
126         {
127             Pop(S, p);
128             cout << p->data <<" ";
129             Push(S, p->rchild);
130             p = p->rchild;
131         }
132     }
133    return 0;
134 }
135 
136 //非递归中序遍历二叉树 方法2
137 int InOrderTraverse2(BiPtr T)
138 {
139     BiPtr p = T;//从树根开始
140     SqStack S;
141     InitStack(S);
142     while(p || !EmptyStack(S))//还有未访问的结点
143         {
144             if(p)//p向左下走到底并记录下沿途的节点
145             {
146                 Push(S, p);
147                 p = p->lchild;
148             }
149             else//p走到了底，再依次弹出刚才路过却没有访问的节点，访问之，然后p向右走
150             {
151                 Pop(S, p);
152                 cout << p->data <<" ";
153                 p = p->rchild;
154             }
155         }
156     return 0;
157 }
158 
159 int main()
160 {
161     freopen( "input.txt", "r", stdin );//从input.txt中读取输入数据
162     BiPtr T;
163     Create_BiTree(T);
164     InOrderTraverse(T);
165     cout << endl;
166     InOrderTraverse1(T);
167     cout << endl;
168     InOrderTraverse2(T);
169     fclose(stdin);
170     return 0;
171 }
input.txt的两组测试数据如下（分开测试，不是放同一个txt中的）：
ABC##D##E#F## 对应的遍历输出：C B D A E F
ABC##DEG#H###F#I##JK### 对应的遍历输出：C B G H E D F I A K J
上面例子中的两棵树如下：
只有0和1的世界是简单的