数据结构-二叉树

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<stack>
  5 #include<queue>
  6 using namespace std;
  7 
  8 typedef struct BiTNode
  9 {
 10     char data;
 11     struct BiTNode *lchild,*rchild;
 12 } BiTNode,*BiTree;
 13 
 14 int CreateBiTree(BiTree &T)
 15 {//按先序序列创建二叉树
 16     char ch;
 17     scanf("%c",&ch);
 18     if(ch ==‘&‘)//‘ ’表示空树
 19     {
 20         T = NULL;
 21     }
 22     else
 23     {
 24         T = (BiTree)malloc(sizeof(BiTNode));
 25         T->data = ch;
 26         CreateBiTree(T->lchild);
 27         CreateBiTree(T->rchild);
 28     }
 29     return 0;
 30 }
 31 
 32 void Visit(BiTree T)
 33 {
 34     if(T->data != ‘ ‘)
 35     {
 36         printf("%c ",T->data);
 37     }
 38 }
 39 
 40 void PreOrder(BiTree T)
 41 {//先序遍历
 42     if(T!= NULL)
 43     {
 44         Visit(T);
 45         PreOrder(T->lchild);
 46         PreOrder(T->rchild);
 47     }
 48 }
 49 
 50 void InOrder(BiTree T)
 51 {//中序遍历
 52     if(T!= NULL)
 53     {
 54         InOrder(T->lchild);
 55         Visit(T);
 56         InOrder(T->rchild);
 57     }
 58 }
 59 
 60 void PostOrder(BiTree T)
 61 {//后序遍历
 62     if(T!= NULL)
 63     {
 64         PostOrder(T->lchild);
 65         PostOrder(T->rchild);
 66         Visit(T);
 67     }
 68 }
 69 
 70 void PreOrder2(BiTree T)
 71 {//先序遍历(非递归).访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
 72     stack<BiTree> stack;
 73     BiTree p = T;
 74     while(p || !stack.empty())
 75     {//栈不空或p不空时循环
 76         if(p != NULL)
 77         {
 78             stack.push(p);
 79             printf("%c ",p->data);//访问根节点
 80             p = p->lchild;//遍历左子树
 81         }
 82         else
 83         {
 84             p = stack.top();
 85             stack.pop();//退栈
 86             p = p->rchild;//访问右子树
 87         }
 88     }//while
 89 }
 90 
 91 void InOrder2(BiTree T)
 92 {// 中序遍历(非递归).中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
 93   //先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
 94     stack<BiTree> stack;
 95     BiTree p = T;//p是遍历指针
 96     while(p || !stack.empty())
 97     {//栈不空或者p不空时循环
 98         if(p != NULL)
 99         {
100             stack.push(p);//入栈
101             p = p->lchild;//遍历左子树
102         }
103         else
104         {
105             p = stack.top();//退栈，访问根节点
106             printf("%c ",p->data);
107             stack.pop();
108             p = p->rchild;//访问右子树
109         }
110     }
111 }
112 
113 typedef struct BiTNodePost
114 {
115     BiTree biTree;
116     char tag;
117 } BiTNodePost,*BiTreePost;
118 
119 void PostOrder2(BiTree T)
120 {//后序遍历(非递归).
121     stack<BiTreePost> stack;
122     BiTree p = T;
123     BiTreePost BT;
124     while(p != NULL || !stack.empty())
125     {
126         while(p != NULL)
127         {//遍历左子树
128             BT = (BiTreePost)malloc(sizeof(BiTNodePost));
129             BT->biTree = p;
130             BT->tag = ‘L‘;//访问过左子树
131             stack.push(BT);
132             p = p->lchild;
133         }
134         while(!stack.empty() && (stack.top())->tag == ‘R‘)
135         { //左右子树访问完毕访问根节点
136             BT = stack.top();
137             stack.pop();//退栈
138             printf("%c ",BT->biTree->data);
139         }
140         if(!stack.empty())//遍历右子树
141         {
142             BT = stack.top();
143             BT->tag = ‘R‘; //访问过右子树
144             p = BT->biTree;
145             p = p->rchild;
146         }
147     }
148 }
149 
150 void LevelOrder(BiTree T)
151 {//层次遍历
152     BiTree p = T;
153     queue<BiTree> queue;//队列
154     queue.push(p);//根节点入队
155     while(!queue.empty())
156     {//队列不空循环
157         p = queue.front();//对头元素出队
158         printf("%c ",p->data);//访问p指向的结点
159 
160         queue.pop();//退出队列
161         if(p->lchild != NULL)
162         {//左子树不空，将左子树入队
163             queue.push(p->lchild);
164         }
165         if(p->rchild != NULL)
166         { //右子树不空，将右子树入队
167             queue.push(p->rchild);
168         }
169     }
170 }
171 int main()
172 {
173     BiTree T;
174     printf("请输入示例先序序列:ABDH&&&E&I&&CF&G&&&.或者自定义先序序列.\n");
175     CreateBiTree(T);
176 
177     printf("\n---------------------------\n");
178     printf("先序遍历：\n");
179     PreOrder(T);
180 
181     printf("\n---------------------------\n");
182     printf("先序遍历(非递归)：\n");
183     PreOrder2(T);
184 
185     printf("\n---------------------------\n");
186     printf("中序遍历：\n");
187     InOrder(T);
188 
189     printf("\n---------------------------\n");
190     printf("中序遍历(非递归)：\n");
191     InOrder2(T);
192 
193     printf("\n---------------------------\n");
194     printf("后序遍历：\n");
195     PostOrder(T);
196 
197     printf("\n---------------------------\n");
198     printf("后序遍历(非递归)：\n");
199     PostOrder2(T);
200 
201     printf("\n---------------------------\n");
202     printf("层次遍历：\n");
203     LevelOrder(T);
204     printf("\n---------------------------\n");
205     return 0;
206 }