基本数据结构

本章讲述了栈、队列、树、指针、对象的基本实现。boring AND difficult！！！

（1）栈

概念定义：栈属于动态集合，采用先进后出策略（LIFO）。基本操作是压入（PUSH）和弹出（POP）。如果s.top=0，表示栈空，如果试图对空栈进行POP操作会发生下溢（underflow）。如果s.top>n,表示栈满，如果进行PUSH操作会发生上溢（overflow）。

基本代码

 1 //基本的栈操作
 2 #include <iostream>
 3 #include <time.h>
 4 using namespace std;
 5 const n=10;
 6 struct stack
 7 {
 8     int top;
 9     int Array[n];
10 }s;
11 //初始化一个空栈
12 int Init_Stack()
13 {
14     s.top = 0;//top为0表示空栈
15     return 1;
16 }
17 //判断栈是否为空
18 bool stack_empty(int Array[])
19 {
20     if (s.top==0)
21     {
22         return true;
23     }
24     else
25     {
26         return false;
27     }
28 }
29 //入栈
30 void stack_push(int Array[],int x)
31 {
32     if (s.top==n)
33     {
34         cerr<<"overflow!"<<endl;
35     } 
36     else
37     {
38         s.top++;
39         s.Array[s.top]=x;
40         
41     }
42 }
43 //出栈
44 int stack_pop(int Array[])
45 {
46     if (stack_empty(s.Array))
47     {
48         cerr<<"underflow"<<endl;
49         return -1;
50     }
51     else
52     {
53         s.top--;
54         return s.Array[s.top+1];
55     }    
56 }
57 void main()
58 {
59     struct stack s;
60     Init_Stack();
61     int x=0;
62     srand( (unsigned)time( NULL ) );
63     for ( int i=0;i<n;i++)
64     {
65         x=rand()%100;
66         stack_push(s.Array,x);
67     }
68     for (i=0;i<n;i++)
69     {
70         cout<<stack_pop(s.Array)<<endl;
71     }
72 
73 }

（2）队列

概念定义：队列属于动态集合，采用先进先出策略（FIFO）。基本操作是出队（enqueue）和出队（dequeue）。如果head=tail，表示队列为空，如果试图对空队列进行enqueue操作会发生下溢（underflow）。如果head=tail+1,表示队列满，如果进行dequeue操作会发生上溢（overflow）。

基本代码：

 1 //基本的队列操作
 2 #include <iostream>
 3 #include <time.h>
 4 using namespace std;
 5 const n=5;
 6 struct Queue
 7 {
 8     int head;
 9     int tail;
10     int Array[n];
11 }Q;
12 void Init_Queue()
13 {
14     Q.head=Q.tail=1;//表示队列为空栈
15 }
16 //判断栈是否为空
17 bool Queue_empty(int Array[])
18 {
19     if (Q.head==Q.tail)
20     {
21         return true;
22     }
23     else
24     {
25         return false;
26     }
27 }
28 void ENQueue(int Array[],int x)
29 {
30     if (Q.head==Q.tail+1)
31     {
32         cerr<<"overflow!"<<endl;
33     } 
34     else
35     {
36         Q.Array[Q.tail]=x;
37         if (Q.tail==n)
38         {
39             Q.tail=0;
40         }
41         else
42         {
43             Q.tail++;
44         }
45     }
46 }
47 int DEQueue(int Array[])
48 {
49     int x=0;
50     if (Queue_empty(Q.Array))
51     {
52        cerr<<"underflow"<<endl;
53     } 
54     else
55     {
56         x=Q.Array[Q.head];
57         if (Q.head==n)
58         {
59             Q.head=0;
60         } 
61         else
62         {
63             Q.head++;
64         }
65     }
66    return x;
67 }
68 void main()
69 {
70     struct Queue Q;
71     Init_Queue();
72     int x=0;
73     srand( (unsigned)time( NULL ) );
74     for ( int i=0;i<n;i++)
75     {
76         x=rand()%100;
77         ENQueue(Q.Array,x);
78     }
79     for (i=0;i<n;i++)
80     {
81         cout<<DEQueue(Q.Array)<<endl;
82     } 
83 }

（3）链表

基本概念：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序存储结构，操作复杂。

基本代码：

  1 //书中双向链表无哨兵实现
  2 
  3 #include <iostream>
  4 #include <time.h>
  5 using namespace std;
  6 #define LEN sizeof(struct List)
  7 struct List
  8 {
  9     struct List*prev;
 10     struct List*next;
 11     struct List*head;
 12     int key;
 13 };
 14 //查找数据
 15 struct List*search(struct List L,int k)
 16 {
 17     struct List*x;
 18     x=L.head;
 19     while (x!=NULL&&x->key!=k)
 20     {
 21         x=x->next;
 22     }
 23     return x;
 24 }
 25 //插入数据
 26 struct List*insert(struct List L,struct List*x)
 27 {
 28    x->next=L.head;
 29    if (L.head!=NULL)
 30    {
 31        L.head->prev=x;
 32    }
 33    L.head=x;
 34    x->prev=NULL;
 35    return L.head;
 36 }
 37 //删除数据
 38 struct List*Delete(struct List L,struct List*x)
 39 {
 40    if (x->prev!=NULL)
 41    {
 42        x->prev->next=x->next;
 43    } 
 44    else
 45    {
 46        L.head=x->next;
 47    }
 48    if (x->next!=NULL)
 49    {
 50        x->next->prev=x->prev;
 51    }
 52    return L.head;
 53 }
 54 //打印数据
 55 void Print(List L)  
 56 {  
 57     struct List*p = L.head;  
 58     while(p)  
 59     {  
 60         cout<<p->key<<' ';  
 61         p = p->next;  
 62     }  
 63     cout<<endl;  
 64 }  
 65 void main()
 66 {
 67    struct List L,*x,*t;
 68    srand( (unsigned)time( NULL ) );
 69    L.head=NULL;x=NULL;
 70    for (int i=0;i<10;i++)
 71    {
 72        x= (struct List*)malloc(LEN);
 73        x->key=rand()%100;
 74        if (i==6)
 75        {
 76            t=x;
 77        }
 78        L.head=insert(L,x);
 79    }
 80    Print(L);
 81    x=search(L,60);
 82    if (x==NULL)
 83    {
 84        cout<<"未找到数据！"<<endl;
 85    } 
 86    else
 87    {
 88        cout<<"已经找到数据"<<x->key<<endl;
 89    }
 90    L.head=Delete(L,t);
 91    Print(L);
 92 }

书中双向链表有哨兵实现:

#include <iostream>
#include <time.h>
using namespace std;
#define LEN sizeof(struct List)
struct List
{
    struct List*prev;
    struct List*next;
    struct List*nil;
    int key;
};
struct List*Initialization(struct List &L)
{
   L.nil;
   L.nil=(struct List*)malloc(LEN);
   L.nil->next=L.nil;
   L.nil->prev=L.nil;
   return L.nil;
}
struct List*search(struct List &L,int k)
{
   struct List*x;
   x=L.nil->next;
   while (x!=L.nil&&x->key!=k)
   {
       x=x->next;
   }
   return x;
}
struct List*insert(struct List &L,struct List*x)
{
    x->next=L.nil->next;
    L.nil->next->prev=x;
    L.nil->next=x;
    x->prev=L.nil;
    return L.nil;
}
struct List*Delete(struct List &L,struct List*x)
{
    x->prev->next=x->next;
    x->next->prev=x->prev;
    return L.nil;
}
//打印数据
void Print(List L)  
{  
    struct List*p = L.nil->next; 
    if(p!=L.nil)
    {
        while(p!=L.nil)  
        {  
            cout<<p->key<<' ';  
            p = p->next;  
        }  
        cout<<endl; 
    }
    else
    {
        cout<<"此链表为空！"<<endl;
    }
} 
void main()
{
    struct List L,*x,*t;
    Initialization(L);
    Print(L);
    srand( (unsigned)time( NULL ) );
    x=NULL;
    for (int i=0;i<10;i++)
    {
        x= (struct List*)malloc(LEN);
        x->key=rand()%100;
        if (i==6)
        {
            t=x;
        }
        insert(L,x);
    }
    Print(L);
    x=search(L,60);
    if (x==L.nil)
    {
        cout<<"未找到数据！"<<endl;
    } 
    else
    {
        cout<<"已经找到数据"<<x->key<<endl;
    }
   Delete(L,t);
   Print(L);
}

View Code

（4）指针和对象的实现

基本概念：当有些语言不支持指针和对象数据类型时，我们可以用数组和数组下标构造对象和指针。这种链表称为静态链表。

对象的多数组和单数组表示基本的字典操作+申请分配内存

基本代码：

对象的多数组表示

用三个数组next key prev 分别表示链表的后继数据前驱。

  1 //由于有些语言不支持指针，所以我们可以用多数组表示的静态双链表。
  2 #include <iostream>
  3 #include <time.h>
  4 #include <windows.h>
  5 using namespace std;
  6 #define MAX 10//于表头的前驱和表尾的后继都不存放元素，所以实际能存放的有效元素个数比MAX少2个
  7 #define Null -1
  8 int head=Null,Free=0;
  9 int j=0;
 10 struct List
 11 {
 12     int next[MAX];
 13     int key[MAX];
 14     int prev[MAX];
 15 };
 16 int isIn(int *num,int index,int pat)//生成的随机数pat是否已经存在
 17 {
 18     int i=0;
 19     for(i=0;i<index;++i)
 20         if(pat==num[i])
 21             return 1;
 22         return 0;   
 23 }
 24 int RAND(int *num)//随机抽取元素互异的key 这样key不会出现重复数值，易于以后的删除工作。
 25 {
 26     int result=0;
 27     if (j>=MAX)
 28     {
 29         return Null;
 30     }
 31     while(1)
 32     {
 33         result=rand()%MAX;
 34         if(!isIn(num,j,result))
 35         {
 36             num[j]=result;
 37             j++;
 38             break;
 39         }
 40     }
 41     return result;
 42 }
 43 //链表初始化
 44 void Initialization(struct List &T,int*num)
 45 {
 46    Free=RAND(num);//[1,MAX-1]之间的数随机选择一个作为表头元素下标
 47    for (int i=0;i<MAX;i++)
 48    {
 49        T.key[i]=0;
 50        T.prev[i]=0;
 51    }
 52    int p=Free;
 53    for ( i=0;i<MAX-1;i++)
 54    {
 55        p=T.next[p]=RAND(num);
 56    }
 57    T.next[p]=Null;//链表最后的next指针为空。-1代表空
 58    j=0;//结构体T初始化后，临时数组num下标设置为0.
 59 }  
 60 //分配空间
 61 int Allocate_object(struct List &T,int*num)
 62 {
 63     if (Free==Null)
 64     {
 65         cerr<<"out of space!"<<endl;
 66         return Null;
 67     }
 68     else
 69     {    
 70       int x=Free; 
 71    Free=T.next[x];
 72       return x;
 73     }
 74 }
 75 //释放空间
 76 void Free_object(struct List &T,int x)
 77 {
 78    T.next[x]=Free;
 79    Free=x;
 80 }
 81 //插入数据
 82 void insert(struct List &T,int k,int *num)
 83 {
 84      int x=Allocate_object(T,num);//类似指针开辟一段内存空间
 85   if (x==Null)
 86   {
 87    return;
 88   }
 89   T.next[x]=head;
 90   T.key[x]=k;
 91   if (head!=Null)
 92   {
 93    T.prev[head]=x;
 94   }
 95   head=x;
 96   T.prev[x]=Null;
 97 }
 98 //查找数据
 99 int search(struct List &T,int k)
100 {
101    int t=head;
102    if (head==Null)
103    {
104        cout<<"链表为空！无法查找！"<<endl;
105        return Null;
106    }
107    while (t!=-1&&T.key[t]!=k)
108    {
109        t=T.next[t];
110    }
111    if (t==Null)
112    {
113        cout<<"不存在这个数据！"<<endl;
114        return Null;
115    } 
116    else
117    {
118       cout<<"待查找数据已经找到！"<<endl;
119       return t;//将待删除的数据下标返回，易于删除工作。
120    }
121 }
122 //删除数据
123 void Delete(struct List &T,int k)//删除特定值的删除函数
124 { 
125     int p=0;
126         p=search(T,k);
127         if (p!=Null)
128         {
129        
130             if (T.prev[p]!=Null)
131             {
132                 T.next[T.prev[p]]=T.next[p];
133             } 
134             else
135             {
136                 head=T.next[p];
137             }
138             if (T.next[p]!=Null)
139             {
140                 T.prev[T.next[p]]=T.prev[p];
141             }
142             cout<<"删除成功！"<<endl;
143             Free_object(T,p);
144         } 
145         else
146         {
147             cout<<"待删除的数据不存在！无法删除！"<<endl;
148         }
149 }
150 void Print(struct List &T)
151 {
152     int i=head;
153     if (head==Null)
154     {
155         cout<<"此链表为空！"<<endl;
156         return;
157     }
158     while (i!=Null)
159     {
160         cout<<T.key[i]<<"->";
161         i=T.next[i];
162     }
163     cout<<endl;
164 }
165 void main()
166 {
167     struct List T;
168     srand((unsigned)time(NULL));
169     int num[MAX]={0};//临时存放next[MAX]和key[MAX]数组的值，目的是用于生成互异的随机数
170     cout<<"初始化链表中。";
171     for( int j=0; j <= 100; j++ )      // 打印百分比   
172      {  
173       cout.width(3);  
174       cout << j << "%";  
175          Sleep(40);  
176       cout << "";//退格符号  
177   }  
178     cout << "
";  
179     Initialization(T,num);
180     Print(T);
181     cout<<"给链表添加数据中。";
182  for(  j=0; j <= 100; j++ )      // 打印百分比   
183  {  
184   cout.width(3);  
185   cout << j << "%";  
186   Sleep(40);  
187   cout << "";//退格符号  
188  }  
189     cout << "
"; 
190     for (int i=0;i<MAX+1;i++)
191     {
192   int k=RAND(num);
193         insert(T,k,num);
194     }
195     insert(T,35,num);
196     Print(T);
197     cout<<"查找数据中。";
198  for(  j=0; j <= 100; j++ )      // 打印百分比   
199  {  
200   cout.width(3);  
201   cout << j << "%";  
202   Sleep(40);  
203   cout << "";//退格符号  
204  }  
205  cout << "
"; 
206     search(T,6);
207     cout<<"删除数据中。";
208  for( j=0; j <= 100; j++ )      // 打印百分比   
209  {  
210   cout.width(3);  
211   cout << j << "%";  
212   Sleep(40);  
213   cout << "";//退格符号  
214  }  
215     cout << "
"; 
216     Delete(T,0);
217     Delete(T,2);
218  Delete(T,5);
219  Delete(T,500);
220  insert(T,25,num);
221  Print(T);
222 }

View Code

对象的单数组表示

用一个数组即可表示双链表，这种表示法比较灵活，因为它允许不同长度的对象存储于同一数组中。一般地我们考虑的数据结构多是由同构的元素构成，因此采用对象的多数组表示法足够满足我们的需求。

以下的代码分别展示了基本的字典操作和如何申请分配内存。

  1 //我们用key next prev表示双链表，如果array[i-1]为key,那么array[i]为next,array[i+1]为prev。
  2 #include <iostream>
  3 #include <time.h>
  4 #include <windows.h>
  5 using namespace std;
  6 #define MAX 120
  7 #define Null -1
  8 int head=0,Free=0;
  9 int isIn(int *num,int index,int pat)//生成的随机数pat是否已经存在
 10 {
 11     int i=0;
 12     for(i=0;i<index;++i)
 13         if(pat==num[i])
 14             return 1;
 15         return 0;   
 16 }
 17 int RAND(int *num,int &j)//随机抽取元素互异的key 这样key不会出现重复数值，易于以后的删除工作。
 18 {
 19     
 20     int result=0;
 21     if (j==0)
 22     {
 23         num[j]=head;j++;
 24     }
 25     while(1)
 26     {
 27         if (MAX/3==0)//防止被除数为0
 28         {
 29             return Null;
 30         }
 31         else
 32         {
 33             result=(rand()%(MAX/3)) * 3 + 1;
 34         }
 35         if(!isIn(num,j,result))
 36         {
 37             num[j]=result;
 38             j++;
 39             break;
 40         } 
 41     }
 42     return result;
 43 }
 44 //分配空间
 45 int Allocate_object(int *Array,int*num)
 46 {
 47     static x;
 48     if (Free==Null)
 49     {
 50         cout<<endl;
 51         cerr<<"out of space!"<<endl;
 52         return Null;
 53     }
 54     else
 55     {   
 56         x=Free;
 57         Free=Array[x];
 58         return x;
 59     }
 60 }
 61 //释放空间
 62 void Free_object(int *Array,int x)
 63 {
 64     Array[x]=Free;
 65     Free=x;
 66 }
 67 //链表初始化
 68 void Initialization(int *Array,int*num,int &j)
 69 {
 70     for (int i=0;i<MAX;i++)
 71     {
 72          Array[i]=0;
 73     }
 74     int p=RAND(num,j);
 75     Free=head=p;
 76     for (i=0;i<MAX/3-1;i++)
 77     {
 78          p=Array[p]=RAND(num,j);
 79     }
 80    Array[p]=Null;//链表最后的next指针为空。-1代表空
 81 }
 82 int insert(int *Array,int *num,int &j)
 83 {
 84     static p=head,q=Null;
 85     int x=Allocate_object(Array,num);
 86     if (p!=Null)
 87     {
 88         Array[p-1]=rand()%MAX+1;
 89         Array[p+1]=q;
 90         q=p;
 91         p=Array[x];
 92     }
 93     else cout<<"链表开辟的内存空间不足！ 无法插入！"<<endl;
 94     return p;
 95 }
 96 //查找数据
 97 int search(int *Array,int k)
 98 {
 99     int t=head;
100     if (Array[t-1]==0)
101     {
102         cout<<"链表为空！无法查找！"<<endl;
103         return Null;
104     }
105     while (t!=-1&&Array[t-1]!=k)
106     {
107         t=Array[t];
108     }
109     if (t==Null)
110     {
111         cout<<"不存在这个数据！"<<endl;
112         return Null;
113     } 
114     else
115     {
116         cout<<"待查找数据已经找到！"<<endl;
117         return t;//将待删除的数据下标返回，易于删除工作。
118     }
119 }
120 //删除数据
121 void Delete(int Array[],int k)//删除特定值的删除函数
122 {
123     int p=0;
124     p=search(Array,k);
125     if (p!=Null)
126     {
127         if (Array[p+1]!=Null)
128         {
129             Array[Array[p+1]]=Array[p];
130         } 
131         else
132         {
133             head=Array[p];
134         }
135         if (Array[p]!=Null)
136         {
137             Array[Array[p]+1]=Array[p+1];
138         }
139         Free_object(Array,p);
140         cout<<"删除成功！"<<endl;
141     }
142     else
143     {
144        cout<<"待删除的数据不存在！无法删除！"<<endl;
145     }
146 }
147 void Print(int *Array)
148 {
149     int i=head;int flag=1;
150     if (Array[head-1]==0)
151     {
152         cout<<"链表为空！"<<endl;
153         return;
154     }
155     while (flag)
156     {
157         if (Array[i]==Null)
158         {
159             flag=0;
160         }
161         cout<<Array[i-1]<<"	";
162         i=Array[i];        
163     }
164 }
165 void main()
166 {
167     int Array[MAX];
168     int num[MAX]={0};//临时存放数据的next指针的值，目的是用于生成互异的随机数
169     int j=0;
170     srand((unsigned)time(NULL));
171     cout<<"初始化链表中。";
172     for( int i=0; i <= 100; i++ )      // 打印百分比 
173     {
174         cout.width(3);
175         cout << i << "%";
176         Sleep(40);
177         cout << "";//退格符号
178     }
179     cout << "
";
180     Initialization(Array,num,j);
181     Print(Array);
182     cout<<"给链表添加数据中。";
183     for(  i=0; i<= 100; i++ )      // 打印百分比 
184     {
185         cout.width(3);
186         cout << i << "%";
187         Sleep(40);
188         cout << "";//退格符号
189     }
190     insert(Array,num,j);
191     insert(Array,num,j);
192     insert(Array,num,j);
193     insert(Array,num,j);
194     insert(Array,num,j);
195     for ( i=0;i<MAX/3;i++)
196     {
197         insert(Array,num,j);
198     }
199     Print(Array);
200     cout<<"查找数据中。";
201     for(  i=0; i <= 100; i++ )      // 打印百分比 
202     {
203         cout.width(3);
204         cout << i << "%";
205         Sleep(40);
206         cout << "";//退格符号
207     }
208     cout << "
";
209     search(Array,5);
210     cout<<"删除数据中。";
211     for(  i=0; i <= 100; i++ )      // 打印百分比 
212     {
213         cout.width(3);
214         cout << i << "%";
215         Sleep(40);
216         cout << "";//退格符号
217     }
218     cout << "
";
219     Delete(Array,5);
220     Delete(Array,6);
221     Delete(Array,7);
222     Delete(Array,7);
223     Delete(Array,6);
224     Print(Array);
225 }

View Code

（5）树

基本代码：

递归实现：

#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
struct Tree
{
    int key;
    struct Tree*lchild;
    struct Tree*rchild;
};
//二叉树的创建
void create(struct Tree **p)
{
  *p=new struct Tree [LEN];
  cout<<"请输入二叉树key值:(按0结束当前分支输入)"<<endl;
  cin>>(*p)->key;
  static i=0;
  if ((*p)->key!=0)
  {
      create((&(*p)->lchild));
      create((&(*p)->rchild));
  }
}
//先序遍历递归过程。。。。（位置1）
void PreOderTraverse(struct Tree *p)
{//递归实现先序遍历
    if (p->key)
    {
        cout<<p->key<<" ";
        PreOderTraverse(p->lchild);
        PreOderTraverse(p->rchild);
    }
}
//中序遍历
void InOderTraverse(struct Tree *p)
{
    if (p->key)
    {        
        InOderTraverse(p->lchild);
        cout<<p->key<<" ";
        InOderTraverse(p->rchild);
    }
}
//后序遍历
void BackOderTraverse(struct Tree *p)
{
    if (p->key)
    {        
        BackOderTraverse(p->lchild);
        BackOderTraverse(p->rchild);
        cout<<p->key<<" ";
    }
}
void main()
{
    struct Tree *p=NULL;
    create(&p);
    cout<<"先序遍历："<<endl;
    PreOderTraverse(p);
    cout<<endl;
    cout<<"中序遍历："<<endl;
    InOderTraverse(p);
    cout<<endl;
    cout<<"后序遍历："<<endl;
    BackOderTraverse(p);
    cout<<endl;
}

View Code

循环实现：

栈实现：

.也可以用栈的数组实现，栈的实现，包括PUSH POP等栈操作全部自己实现。这个应该是符合《算法导论》10.4-3题目条件。

#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
#define m 10//栈的最大容纳空间可以调整
struct Tree
{
    int key;
    struct Tree*lchild;
    struct Tree*rchild;
};
struct Stack
{
    int top;
    int Array[m];
    bool empty();
    void push(struct Tree*);
    int pop();
}s;
//判断栈是否为空
bool Stack::empty()
{
    if (s.top==-1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//入栈
void Stack::push(struct Tree*p)
{
    if (s.top==m)
    {
        cerr<<"overflow!"<<endl;
    } 
    else
    {
        s.top++;
        s.Array[s.top]=reinterpret_cast<int>(p);//将树形结构体的地址转化为整数储存到栈里面。
    }
}
//出栈
int Stack::pop()
{
    if (empty())
    {
        cerr<<"underflow"<<endl;
        return NULL;
    }
    else
    {
        s.top--;
        return s.Array[s.top+1];
    }    
}
void create(struct Tree **p)
{
  *p=new struct Tree [LEN];
  cin>>(*p)->key;
  static i=0;
  if ((*p)->key!=0)
  {
      create((&(*p)->lchild));
      create((&(*p)->rchild));
  }
} 
void PreOderTraverse(struct Tree *root)  
{  //用栈的数组实现，POP PUSH等函数全部自己来写
    if (root == NULL) return; 
    s.top=-1;
    s.push(root);
    struct Tree *p=root;
    while (!s.empty()) {   
        p=reinterpret_cast<struct Tree *>(s.Array[s.top]);//将数组中的数据恢复为编译器所能识别的指针
        cout<<p->key<<" ";
        s.pop();
        if (p->rchild->key != 0) 
        {
            s.push(p->rchild); 
        }
        if (p->lchild->key != 0) 
        {
            s.push(p->lchild);  
        }
    }  
    cout << endl;  
}
void main()
{
    struct Tree *p=NULL;
    create(&p);
    PreOderTraverse(p);
}

View Code

还有一种不用辅助栈，但需要父结点：

//(1). 访问左孩子
//(2). 访问右孩子
//(3). 如果是从右孩子返回，表明整棵子树已访问完，需要沿树而上寻找父节点。直到是从左孩子返回，或者访问到根节点的父节点
#include <iostream>
#include <stack>
using namespace std;
#define LEN sizeof(struct Tree)
struct Tree
{
    int key;
    struct Tree*lchild;
    struct Tree*rchild;
    struct Tree*parent;
};
void create(struct Tree **p)
{
    static struct Tree *p1=NULL;//p1保存当前结点的父亲结点
    *p=new struct Tree [LEN];
    cin>>(*p)->key;
    (*p)->parent=p1;
    p1=*p;
    if ((*p)->key!=0)
    {
        create((&(*p)->lchild));
        p1=*p;    
        create((&(*p)->rchild));
    }
}
void InOderTraverse(struct Tree *p)
{
   if(!p->key) return;
    struct Tree *x=NULL;
    while(1)
    {
        //访问左孩子
        if(x != p->lchild)
        {
            while(p->lchild->key) 
            {
                p=p->lchild;
            }
        }
        cout<<p->key<<" ";
        //访问右孩子
        if(p->rchild->key)
        {
            p=p->rchild;
            continue;
        }
        //回溯
        do
        {
            x=p;
            p=p->parent;
            //访问到根节点的父节点（NULL)
            if(!p) return;
        }while(x==p->rchild);
    }
}
void main()
{
    struct Tree *p=NULL;
    create(&p);
    InOderTraverse(p);
}

View Code

左孩子右兄弟表示多叉树:

//左孩子右兄弟表示多叉树
#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
struct Tree*root=NULL;
struct Tree
{
    int key;
    struct Tree*left_child;
    struct Tree*right_sibling;
};
struct Tree*create(struct Tree**p)
{//注意创建多叉树的过程中，根结点没有右兄弟，所以最后回溯到根结点时，要把根节点的右兄弟设置为0.
  *p=new struct Tree[LEN];
  cin>>(*p)->key; 
  if ((*p)->key!=0)
  {
      create(&(*p)->left_child);
      create(&(*p)->right_sibling);
  }      
   return root;
}
//先序遍历递归过程
void PreOderTraverse(struct Tree *p)
{
    if (p->key)
    {
        cout<<p->key<<" ";
        PreOderTraverse(p->left_child);
        PreOderTraverse(p->right_sibling);
    }
}          
void main()
{
    struct Tree *p=NULL;
    create(&p);
    PreOderTraverse(p);
}

View Code

参考资料：

1、栈和队列的简单应用:

http://www.cnblogs.com/robinli/archive/2011/02/26/1965630.html

2、简单数据结构的理论升级：

http://blog.csdn.net/z84616995z/article/details/19202773