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

雨点打透心脏的1/2处 2021-12-14 15:34 167阅读 0赞

存档：

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 }

运行结果如下：

![1100338-20171112151424247-1405256783.png][]

转载于:https://www.cnblogs.com/ECJTUACM-873284962/p/7821703.html

[1100338-20171112151424247-1405256783.png]: /images/20211214/7fe030d16bbd4762ad8479d5c1e7e70c.png