【数据结构】二叉树

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct BITree{
  4     char data;
  5     BITree *lchild;
  6     BITree *rchild;
  7 }BITree,*BiTree;
  8 typedef struct Stack{
  9     BiTree data;
 10     Stack *next;
 11 }Stack;
 12 BITree *pop(Stack *p)
 13 {
 14     Stack *q;
 15     q = p->next;
 16     p ->next = q->next;
 17     return q->data;
 18 }
 19 void push(Stack *q,BiTree &p)
 20 {
 21     Stack *q1;
 22     q1 = (Stack*)malloc(sizeof(Stack));
 23     if(!q1)exit(0);
 24     q1->data=p;
 25     q1->next = q->next;
 26     q->next=q1;
 27 }
 28 
 29 //创建二叉树 
 30 void CreateBiTree(BiTree &p)
 31 {
 32     char d;
 33     scanf("%c",&d);
 34     fflush(stdin);
 35     if(d=='#')p=NULL;
 36     else{
 37         p=(BITree*)malloc(sizeof(BITree));
 38         if(!p)exit(0);
 39         p->data=d;
 40         CreateBiTree(p->lchild);
 41         CreateBiTree(p->rchild);
 42     }
 43 }
 44 
 45 //前序遍历 
 46 void Q_BiTree(BiTree &p)
 47 {
 48     if(p==NULL)
 49     return ;
 50     else{
 51         printf("%c",p->data);
 52         Q_BiTree(p->lchild);
 53         Q_BiTree(p->rchild);
 54     }
 55 }
 56 
 57 //中序遍历 
 58 void Z_BiTree(BiTree &p)
 59 {
 60     if(p==NULL)
 61         return;
 62     else{
 63         Z_BiTree(p->lchild);
 64         printf("%c",p->data);
 65         Z_BiTree(p->rchild);
 66     }
 67 }
 68 
 69 // 后续遍历 
 70 void H_BiTree(BiTree &p)
 71 {
 72     if(p==NULL)
 73         return ;
 74         else{
 75             H_BiTree(p->lchild);
 76             H_BiTree(p->rchild);
 77             printf("%c",p->data);
 78         }
 79 }
 80 
 81 //求二叉树的深度 
 82 int depth(BiTree &p)
 83 {
 84     if(p==NULL)
 85         return 0;
 86     else
 87     {
 88         int l=depth(p->lchild);
 89         int r=depth(p->rchild);
 90         return (l>r?l:r)+1;
 91     }
 92 }
 93 
 94 //求二叉树的节点数 
 95 int num_of_nodes(BiTree &p)
 96 {
 97     if(p==NULL)
 98         return 0;
 99     return 1+num_of_nodes(p->lchild)+num_of_nodes(p->rchild);
100 }
101 
102 //求二叉树的叶子接点 
103 int num_of_yezi(BiTree &p)
104 {
105     if(p==NULL)
106         return 0;
107     if((p->lchild==NULL)&&(p->rchild==NULL))
108         return 1;
109     return num_of_nodes(p->lchild)+num_of_yezi(p->rchild);
110 }
111 
112 //求只有一个节点 
113 int num_of_1nodes(BiTree &p)
114 {
115 
116     if(p==NULL)
117         return 0;
118     if((p->lchild==NULL&&p->rchild!=NULL)||(p->lchild!=NULL&&p->rchild==NULL))
119         return 1;
120     return num_of_1nodes(p->lchild)+num_of_1nodes(p->rchild);
121 }
122 
123 //交换左右子树 
124 void changeNode(BiTree &p)
125 {
126     if(p==NULL)
127         return ;
128     else{
129         BiTree q;
130         q=p->lchild;
131         p->lchild=q->rchild;
132         q->rchild=q;
133     }
134     changeNode(p->lchild);
135     changeNode(p->rchild);
136 }
137 
138 //非递归，前序遍历 
139 void F_Q_BiTree(BiTree &p)
140 {
141     Stack *q;
142     q=(Stack *)malloc(sizeof(Stack));
143     if(!q)exit(0);
144     q->next=NULL;
145     while(p||q->next!=NULL)
146     {
147         while(p)
148         {
149             push(q,p);
150             printf("%c",p->data);
151             p=p->lchild;
152         }
153         p=pop(q);
154         p=p->rchild;
155     }
156 }
157 //非递归，中序遍历 
158 void F_Z_BiTree(BiTree &p)
159 {
160     Stack *q;
161     q=(Stack *)malloc(sizeof(Stack));
162     if(!q)exit(0);
163     q->next=NULL;
164     while(p||q->next!=NULL)
165     {
166         while(p)
167         {
168             push(q,p);
169             p=p->lchild;
170         }
171         p=pop(q);
172         printf("%c",p->data);
173         p=p->rchild;
174     }
175 }
176 void F_H_BiTree(BiTree &p)
177 {
178     //buxiele
179 }
180 int main()
181 {
182     int n=0;
183     BiTree p;
184     CreateBiTree(p);
185     /*n=num_of_nodes(p);
186     n=num_of_yezi(p);
187     n=depth(p);
188     n=num_of_1nodes(p);
189     printf("%d",n);
190     changeNode(p);*/
191     F_Q_BiTree(p);
192 //    Q_BiTree(p);
193 
194 
195 }