二叉树的基本运算

  1 #include <iostream>
  2 #include <cstdlib>
  3 using namespace std;
  4 #define datatype char
  5 typedef struct node
  6 {
  7     datatype data;
  8     struct node *lchild;
  9     struct node *rchild;
 10 }*bitree,binode;                        /*二叉树*/
 11 void initbitree(bitree *T)
 12 {
 13     *T=NULL;
 14 }
 15 void destroybitree(bitree *T)                /*二维指针*/
 16 {
 17     if(*T)                        /*如果是非空二叉树*/
 18     {
 19         if((*T)->lchild)
 20             destroybitree(&((*T)->lchild));
 21         if((*T)->rchild)
 22             destroybitree(&((*T)->rchild));
 23         free(*T);
 24         *T=NULL;
 25     }
 26 }
 27 void creatbitree(bitree *T)
 28 {
 29     datatype ch;                    /*递归创建二叉树*/
 30     cin>>ch;
 31     if(ch=='#')                        /*表示该处不生成结点*/
 32         *T=NULL;
 33     else
 34     {
 35         *T=new binode;
 36         if(!(*T))
 37             exit(-1);
 38         (*T)->data=ch;
 39         creatbitree(&((*T)->lchild));        /*构造左子树*/
 40         creatbitree(&((*T)->rchild));        /*构造右子树*/
 41     }
 42 }
 43 int insertleftchild(bitree p,bitree c)        /*二叉树的左插入*/
 44 {
 45     if(p)
 46     {
 47         c->rchild=p->lchild;    /*将c子树插入到T中，使得c成为p的做子树*/
 48         p->lchild=c;        /*p的左子树成为c的右子树*/
 49         return 1;
 50     }
 51     return 0;
 52 }
 53 int insertrightchild(bitree p,bitree c)        /*二叉树的右插入*/
 54 {
 55     if(p)
 56     {
 57         c->rchild=c->lchild;
 58         p->rchild=c;
 59         return 1;
 60     }
 61     return 0;
 62 }
 63 bitree point(bitree T,datatype e)            /*查找元素为e的结点的指针*/
 64 {
 65     bitree q[1000];
 66     int front=0,rear=0;                /*头节点不存储元素*/
 67     binode *p;
 68     if(T)
 69     {
 70         q[rear]=T;
 71         rear++;
 72         while(front!=rear)            /*利用队列查找*/
 73         {
 74             p=q[front];
 75             front++;
 76             if(p->data==e)
 77                 return p;
 78             if(p->lchild)
 79                 q[rear++]=p->lchild;
 80             if(p->rchild)
 81                 q[rear++]=p->rchild;
 82         }
 83     }
 84     return NULL;
 85 }
 86 datatype leftchild(bitree T,datatype e)        /*返回二叉树结点左孩子元素值*/
 87 {
 88     bitree p;
 89     if(T)
 90     {
 91         p=point(T,e);
 92         if(p&&p->lchild)
 93             return p->lchild->data;
 94     }
 95     return 0;
 96 }
 97 datatype rightchile(bitree T,datatype e)
 98 {
 99     bitree p;
100     if(T)
101     {
102         p=point(T,e);                /*寻找该节点*/
103         if(p&&p->rchild)
104             return p->rchild->data;
105     }
106     return 0;
107 }
108 int deleteleftchild(bitree p)                /*删除二叉树左子树的操作*/
109 {
110     if(p)
111     {
112         destroybitree(&(p->lchild));
113         return 1;
114     }
115     return 0;
116 }
117 int deleterightchild(bitree p)            /*删除右子树*/
118 {
119     if(p)
120     {
121         destroybitree(&(p->rchild));
122         return 1;
123     }
124     return 0;
125 }
126 int main()
127 {
128     bitree T;
129     initbitree(&T);
130     creatbitree(&T);
131 }