树和二叉树的存储结构的实现(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 }