树和二叉树的存储结构的实现(C/C++实现)-白红宇

树和二叉树的存储结构的实现(C/C++实现)

阅读量：6886 次

发布时间：2019-06-27

本文共 5521 字，大约阅读时间需要 18 分钟。

存档：

1 #include 
     
       2 #include 
      
        3 #include 
       
         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):"<
        
         >x;45     if(findnode(t,x))46         cout<<"字符存在!";47     else 48         cout<<"字符不存在!";49     cout<
         
          lchild!=NULL)55             cout<
          
           <<"左孩子为:"<
           
            lchild->data<<" ";56 else57 cout<
            
             <<"无左孩子"<<" ";58 if(p->rchild!=NULL)59 cout<
             
              <<"右孩子为:"<
              
               rchild->data<

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<
     
      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<
      
       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<
       
        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<
        
         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<
         
          lchild->data<<' ';132             queue[rear]=t->lchild;133             rear=(rear+1)%max;134         }135         if(t->rchild!=NULL)//输出右孩子,并入队列136         {137             cout<
          
           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;//空树结点个数为0148 else149 {150 num1=nodecount(t->lchild);//左子树结点个数151 num2=nodecount(t->rchild);//右子树结点个数152 return (num1+num2+1);//左子树+右子树+1153 }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<
           
            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 }