树和二叉树的存储结构的实现(C/C++实现)详解编程语言

存档:

 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 }

运行结果如下:

树和二叉树的存储结构的实现(C/C++实现)详解编程语言

 

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/11844.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论