《二叉树的基本操作》

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 
  5 #define NUM 100            //二叉树的最大结点数
  6 #define QueueSize 100    //队列初始容量
  7 #define TRUE 1
  8 #define FALSE 0
  9 #define OK 1
 10 #define ERROR 0
 11 #define OVERFLOW -1
 12 
 13 typedef int Status;                //函数结果状态代码
 14 typedef char DataType;            //二叉树结点元素类型为char类型
 15 
 16 //二叉树的存储结构
 17 typedef struct node
 18 {
 19     DataType data;                    //结点元素
 20     struct node *lchild,*rchild;    //左右孩子指针
 21 }BinTNode,*BinTree;
 22 
 23 typedef BinTNode* ElemType;
 24 
 25 //循环队列存储结构
 26 typedef struct
 27 {
 28     ElemType *base;
 29     int front,rear;
 30 }SeQueue;
 31 
 32 Status CreateBiTree(BinTree &bt)
 33 {//按照先序遍历次序递归建立二叉树。
 34  //输入ABC##DE#G##F###
 35     char ch;
 36     scanf_s("%c",&ch);
 37     if(ch == '#')    bt = NULL;
 38     else
 39     {
 40         bt = (BinTNode*)malloc(sizeof(BinTNode));
 41         bt->data = ch;    //生成根结点
 42         CreateBiTree(bt->lchild);    //构造左子树
 43         CreateBiTree(bt->rchild);    //构造右子树
 44     }
 45     return OK;
 46 }
 47 
 48 Status InorderTraversal(BinTree bt)
 49 {//中序遍历二叉树的非递归方法
 50     BinTNode *stack[NUM];        //定义栈数组
 51     int top = 0;                //初始化栈
 52     stack[top] = bt;
 53     do
 54     {
 55         while(NULL!=stack[top])
 56         {//扫描根结点及其所有的左结点并入栈
 57             top = top + 1;
 58             stack[top] = stack[top-1]->lchild;
 59         }
 60         top = top -1;        //退栈
 61         if(top>=0)            //判断栈是否为空
 62         {
 63             printf("%3c",stack[top]->data);    //访问结点
 64             stack[top] = stack[top]->rchild;    //扫描右子树
 65         }
 66     }while(top>=0);
 67     return OK;
 68 }
 69 
 70 void PreOrderTraversal(BinTree bt)
 71 {//先序遍历二叉树
 72     if(bt)
 73     {
 74         printf("%3c",bt->data);
 75         PreOrderTraversal(bt->lchild);
 76         PreOrderTraversal(bt->rchild);
 77     }
 78 }
 79 
 80 void InOrderTraversal(BinTree bt)
 81 {//中序遍历二叉树
 82     if(bt)
 83     {
 84         InOrderTraversal(bt->lchild);
 85         printf("%3c",bt->data);
 86         InOrderTraversal(bt->rchild);
 87     }
 88 }
 89 void PostOrder(BinTree bt)
 90 {//后序遍历二叉树
 91     if(bt)
 92     {
 93         PostOrder(bt->lchild);
 94         PostOrder(bt->rchild);
 95         printf("%3c",bt->data);
 96     }
 97 }
 98 
 99 int Size(BinTree bt)
100 {//统计二叉树中所有结点的个数
101     int num1,num2;
102     if(bt==NULL)
103         return 0;
104     else if(bt->lchild==NULL && bt->rchild==NULL)
105         return 1;
106     else
107     {
108         num1 = Size(bt->lchild);    //统计左子树的结点个数
109         num2 = Size(bt->rchild);    //统计右子树的结点个数
110         return (num1+num2+1);
111     }
112 }
113 
114 int LeafCount(BinTree bt)
115 {//统计二叉树的叶子总数
116     int LeafNum;
117     if(bt==NULL)
118         LeafNum = 0;
119     else if((bt->lchild==NULL) && (bt->rchild==NULL))
120         LeafNum = 1;
121     else 
122         LeafNum = LeafCount(bt->lchild)+LeafCount(bt->rchild);    //叶子总数为左右子树叶子之和
123     return LeafNum;
124 }
125 
126 int Depth(BinTree bt)
127 {//统计二叉树的深度
128     int hl,hr,max;
129     if(bt!=NULL)
130     {
131         hl = Depth(bt->lchild);    //求左子树的深度
132         hr = Depth(bt->rchild);    //求右子树的深度
133         max = hl>hr?hl:hr;
134         return (max+1);            //返回树的深度
135     }
136     else
137         return 0;
138 }
139 
140 void Exchange(BinTree bt)
141 {//交换左右二叉树
142     if(bt == NULL)
143         return;
144     BinTNode *temp;
145     temp = bt->lchild;
146     bt->lchild = bt->rchild;
147     bt->rchild = temp;
148     Exchange(bt->lchild);
149     Exchange(bt->rchild);
150 }
151 
152 //构造一个循环队列
153 Status InitQueue(SeQueue &Q)
154 {
155     Q.base = (ElemType*)malloc(QueueSize*sizeof(ElemType));
156     if(!Q.base)        exit(0);
157     Q.front = Q.rear = 0;
158     return OK;
159 }
160 
161 //插入新的元素为队尾元素
162 Status EnQueue(SeQueue &Q,ElemType e)
163 {//插入的元素为二叉树结点中的元素
164     if((Q.rear+1)%QueueSize == Q.front)
165     {
166         printf("Queue overflow");
167         return 0;
168     }
169     Q.base[Q.rear] = e;
170     Q.rear = (Q.rear+1)%QueueSize;
171     return 1;
172 }
173 
174 //删除队头元素
175 Status DeleteQ(SeQueue &Q,ElemType &e)
176 {
177     if(Q.front == Q.rear)
178     {
179         printf("Queue empty");
180         return ERROR;
181     }
182     e = Q.base[Q.front];
183     Q.front = (Q.front+1)%QueueSize;
184     return OK;
185 }
186 
187 //判空循环队列
188 Status IsEmptyQ(SeQueue Q)
189 {
190     if(Q.front == Q.rear)
191         return TRUE;
192     else
193         return FALSE;
194 }
195 
196 //层次遍历二叉树
197 void LevelOrderTraversal(BinTree bt)
198 {
199     SeQueue Q;
200     ElemType e;
201     InitQueue(Q);        //创建并初始化队列
202     if(bt)    EnQueue(Q,bt);
203     while(!IsEmptyQ(Q))
204     {
205         DeleteQ(Q,e);
206         printf("%3c",e->data);
207         if(e->lchild)    EnQueue(Q,e->lchild);
208         if(e->rchild)    EnQueue(Q,e->rchild);
209     }
210 }
211 
212 void main()
213 {
214     BinTree bt;
215     int xz = 1;
216     int yz,sd;
217     while(xz)
218     {
219         printf("	*************************************
");
220         printf("		二叉树的建立及其基本操作
");
221         printf("	*************************************
");
222         printf("	==============================
");
223         printf("	1,建立二叉树的存储结构
");
224         printf("	2,二叉树的基本操作
");
225         printf("	3,交换二叉树的左右子树
");
226         printf("	4,二叉树的层次遍历
");
227         printf("	0,退出系统
");
228         printf("	==============================
");
229         printf("	请选择：（0~4）
");
230         scanf("%d",&xz);
231         getchar();
232         switch(xz)
233         {//输入:ABC##DE#G##F###
234         case 1:
235             printf("输入二叉树的先序序列结点值：
");
236             CreateBiTree(bt);
237             printf("二叉树的链式存储结构建立完成
");
238             printf("
");
239             break;
240         case 2:
241             printf("该二叉树的先序遍历序列是：");
242             PreOrderTraversal(bt);    //输出ABCDEGF
243             printf("
");
244             printf("该二叉树的中序遍历序列是：");
245             InOrderTraversal(bt);    //输出CBEGDFA
246             printf("
");
247             printf("该二叉树的后序遍历序列是：");
248             PostOrder(bt);            //输出CGEFDBA
249             printf("
");    
250             printf("该二叉树的中序遍历序列是(非递归算法)：");
251             InorderTraversal(bt);    //输出CBEGDFA
252             printf("
");    
253             printf("该二叉树的结点个数是:%d
",Size(bt));
254             yz = LeafCount(bt);
255             printf("叶子结点个数是：%d",yz);
256             printf("
");
257             sd = Depth(bt);
258             printf("该二叉树的深度是：%d
",sd);
259             printf("
");
260             break;
261         case 3:
262             Exchange(bt);
263             printf("该二叉树意已交换左右子树
");
264             printf("
");
265             printf("交换左右子树后，先序遍历序列是：");
266             PreOrderTraversal(bt);
267             printf("
");
268             printf("交换左右子树后，中序遍历序列是：");
269             InorderTraversal(bt);
270             printf("
");
271             printf("交换左右子树后，后序遍历序列是：");
272             PostOrder(bt);
273             printf("
");
274             break;
275         case 4:
276             printf("该二叉树的层次遍历序列是：");
277             LevelOrderTraversal(bt);
278             printf("
");    //输出ABCDEFG
279         case 0:
280             break;
281         default:printf("输入的选项没有对应的操作，请重新选择：
");
282         }
283     }
284 }