存档:
1 #include <iostream.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #define max 20
5 typedef char elemtype;
6 #include "tree.h"
7 void main()
8 {
9 btree t,p;
10 char x;
11 int i=0,num=0;
12 cout<<"(1)初始化二叉树initbt(t):"<<endl;
13 initbt(t);
14 cout<<"(2)输入先序遍历序列,创建二叉树(空树以#表示)createbt(t):"<<endl;
15 createbt(t);
16 cout<<"判断二叉树是否为空树emptybt(t):";
17 i=emptybt(t);
18 if(i==1)
19 cout<<"二叉树为空树!"<<endl;
20 else
21 cout<<"二叉树非空!"<<endl;
22 cout<<"(4)输出二叉树的括号描述displaybt(t):";
23 displaybt(t);
24 cout<<endl;
25 cout<<"(5)二叉树的深度depthbt(t)为:"<<depthbt(t)<<endl;
26 cout<<"(6)二叉树的叶子结点的个数leafcount(t,num)为:";
27 leafcount(t,num);
28 cout<<num<<endl;
29 cout<<"(7)二叉树的结点总个数nodecount(t)为:"<<nodecount(t)<<endl;
30 cout<<"(8)先序遍历preorder(t)的结果为:";
31 preorder(t);
32 cout<<endl;
33 cout<<"(9)中序遍历inorder(t)的结果为:";
34 inorder(t);
35 cout<<endl;
36 cout<<"(10)后序遍历postorder(t)的结果为:";
37 postorder(t);
38 cout<<endl;
39 cout<<"(11)层次遍历levelorder(t)的结果为:";
40 levelorder(t);
41 cout<<endl;
42 fflush(stdin);//清空缓存
43 cout<<"(12)输入一个字符,并在树中查找该字符是否存在findnode(t,x):";
44 cin>>x;
45 if(findnode(t,x))
46 cout<<"字符存在!";
47 else
48 cout<<"字符不存在!";
49 cout<<endl;
50 cout<<"(13)字符"<<x<<"对应结点findnode1(t,x)的孩子为:"<<endl;
51 p=findnode1(t,x);
52 if(p!=NULL)
53 {
54 if(p->lchild!=NULL)
55 cout<<x<<"左孩子为:"<<p->lchild->data<<" ";
56 else
57 cout<<x<<"无左孩子"<<" ";
58 if(p->rchild!=NULL)
59 cout<<x<<"右孩子为:"<<p->rchild->data<<endl;
60 else
61 cout<<x<<"无右孩子"<<endl;
62 }
63 else
64 cout<<x<<"不存在"<<endl;
65 cout<<"(14)清空clearbt(t)的结果为:";
66 clearbt(t);
67 if(emptybt(t))
68 cout<<"二叉树为空树!"<<endl;
69 else
70 cout<<"二叉树非空!"<<endl;
71 cout<<"(15)按照二叉树的括号描述createbt1(t,str)创建二叉树A(B(D,E),C(,F))";
72 createbt1(t,"A(B(D,E),C(,F))");
73 cout<<endl;
74 cout<<"输出二叉树的括号描述displaybt(t):";
75 displaybt(t);
76 cout<<endl;
77 cout<<"先序遍历preorder(t)的结果为:";
78 preorder(t);
79 cout<<endl;
80 cout<<"中序遍历inorder(t)的结果为:";
81 inorder(t);
82 cout<<endl;
83 clearbt(t);
84 system("pause");
85 }
1 struct node
2 {
3 elemtype data;//数据元素
4 struct node *lchild;//指向左孩子
5 struct node *rchild;//指向右孩子
6 };
7 typedef struct node btnode;//定义结构体的别名btnode
8 typedef struct node *btree;//定义结构体指针的别名btree
9 void initbt(btree &t)//初始化函数,构造一棵空树
10 {
11 t=NULL;
12 }
13 void createbt(btree &t)//先序遍历序列创建二叉树
14 {
15 elemtype ch;
16 cin>>ch;
17 if(ch=='#')
18 t=NULL;//#表示空树,递归终止
19 else
20 {
21 t=new btnode;//创建新结点
22 if(t==NULL)//如果创建结点失败,就退出
23 exit(-2);
24 t->data=ch;//生成根结点
25 createbt(t->lchild);//构造左子树
26 createbt(t->rchild);//构造右子树
27 }
28 }
29 int emptybt(btree t)//判断树是否为空树
30 {
31 if(t==NULL)
32 return 1;//空树返回1
33 else
34 return 0;//非空树返回0
35 }
36 int depthbt(btree t)//求二叉树t的深度
37 {
38 if(t==NULL)
39 return 0;//空树深度为0
40 else
41 {
42 int depthl=depthbt(t->lchild);//求左子树的高度为depthl
43 int depthr=depthbt(t->rchild);//求右子树的高度为depthr
44 return 1+(depthl>depthr?depthl:depthr);//子树深度最大的+1
45 }
46 }
47 int findnode(btree t,elemtype x)//仿照先序遍历,查找data域为x的结点是否存在
48 {
49 int i;
50 if(t==NULL)
51 return 0;//t为空树,无结点,不存在x,返回0
52 else if(t->data==x)//t结点恰好是x对应结点,返回1
53 return 1;
54 else
55 {
56 i=findnode(t->lchild,x);//在左子树中去查找x
57 if(i!=0)//如果找到了就返回
58 return i;
59 else
60 return findnode(t->rchild,x);//没找到就去右子树中查找x
61 }
62 }
63 btree findnode1(btree t,elemtype x)//仿照先序遍历,查找data域为x的结点,返回结点指针
64 {
65 btree p;
66 if(t==NULL)
67 return NULL;//t为空树,不存在x,返回NULL
68 else if(t->data==x)//t结点恰好是x对应结点,返回t
69 return t;
70 else
71 {
72 p=findnode1(t->lchild,x);//在左子树中去查找x
73 if(p!=NULL)//如果找到了就返回
74 return p;
75 else
76 return findnode1(t->rchild,x);//没找到就去右子树中查找x
77 }
78 }
79 void preorder(btree t)//先序遍历的递归算法
80 {
81 if(t!=NULL)
82 {
83 cout<<t->data<<' ';//访问根结点
84 preorder(t->lchild);//递归访问左子树
85 preorder(t->rchild);//递归访问右子树
86 }
87 }
88 void inorder(btree t)//中序遍历的递归算法
89 {
90 if(t!=NULL)
91 {
92 inorder(t->lchild);//递归访问左子树
93 cout<<t->data<<' ';//访问根结点
94 inorder(t->rchild);//递归访问右子树
95 }
96 }
97 void postorder(btree t)//后序遍历的递归算法
98 {
99 if(t!=NULL)
100 {
101 postorder(t->lchild);//递归访问左子树
102 postorder(t->rchild);//递归访问右子树
103 cout<<t->data<<' ';//访问根结点
104 }
105 }
106 void clearbt(btree &t)//仿照后序遍历的递归算法
107 {
108 if(t!=NULL)
109 {
110 clearbt(t->lchild);//先清空左子树
111 clearbt(t->rchild);//后清空右子树
112 delete t;//删除根结点
113 t=NULL;
114 }
115 }
116 void levelorder(btree t)//借助循环队列的原理,实现层次遍历
117 {
118 btree queue[max];//定义循环队列
119 int front,rear;//定义队首和队尾指针
120 front=rear=0;//置队列为空队列
121 if(t!=NULL)
122 cout<<t->data<<' ';//先访问再入队列
123 queue[rear]=t;
124 rear++;//结点指针入队列
125 while(rear!=front)//队列不为空,继续循环
126 {
127 t=queue[front];//队头出队列
128 front=(front+1)%max;
129 if(t->lchild!=NULL)//输出左孩子,并入队列
130 {
131 cout<<t->lchild->data<<' ';
132 queue[rear]=t->lchild;
133 rear=(rear+1)%max;
134 }
135 if(t->rchild!=NULL)//输出右孩子,并入队列
136 {
137 cout<<t->rchild->data<<' ';
138 queue[rear]=t->rchild;
139 rear=(rear+1)%max;
140 }
141 }
142 }
143 int nodecount(btree t)//求二叉树t的结点个数
144 {
145 int num1,num2;
146 if(t==NULL)
147 return 0;//空树结点个数为0
148 else
149 {
150 num1=nodecount(t->lchild);//左子树结点个数
151 num2=nodecount(t->rchild);//右子树结点个数
152 return (num1+num2+1);//左子树+右子树+1
153 }
154 }
155 void leafcount(btree t,int &count)//求二叉树t的叶子结点的个数
156 {
157 if(t!=NULL)
158 {
159 if(t->lchild==NULL&&t->rchild==NULL)
160 count++;//叶子结点计算
161 leafcount(t->lchild,count);//左子树叶子个数
162 leafcount(t->rchild,count);//右子树叶子个数
163 }
164 }
165 void displaybt(btree t)//以广义表法输出二叉树
166 {
167 if(t!=NULL)
168 {
169 cout<<t->data;
170 if(t->lchild!=NULL||t->rchild!=NULL)
171 {
172 cout<<'(';
173 displaybt(t->lchild);
174 if(t->rchild!=NULL)
175 cout<<',';
176 displaybt(t->rchild);
177 cout<<')';
178 }
179 }
180 }
181 void createbt1(btree &t,char *str)//由广义表str串创建二叉链
182 {
183 btnode *st[max];
184 btnode *p=NULL;
185 int top=-1,k,j=0;
186 char ch;
187 t=NULL;//建立的二叉树初始化为空
188 ch=str[j];
189 while(ch!='\0')//str未扫描完时循环
190 {
191 switch(ch)
192 {
193 case '(':top++;st[top]=p;k=1;break;//为左结点
194 case ')':top--;break;
195 case ',':k=2;break;//为右结点
196 default:p=new btnode;
197 p->data=ch;
198 p->lchild=p->rchild=NULL;
199 if(t==NULL)//p指向二叉树的根结点
200 t=p;
201 else//已建立二叉树根结点
202 {
203 switch(k)
204 {
205 case 1:st[top]->lchild=p;break;
206 case 2:st[top]->rchild=p;break;
207 }
208 }
209 }
210 j++;
211 ch=str[j];
212 }
213 }
运行结果如下: