二叉树的实现

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 /*本程序作为数据结构课程（使用教材“数据结构与算法分析-C语言描述”，M. A. Ｗeiss著）关于二叉树部分的补充程序。*/ 
  4 /*本程序使用纯 C 语言*/
  5 
  6 typedef char ElementType;
  7 typedef struct TreeNode {
  8     ElementType Element;
  9     struct TreeNode *Left;
 10     struct TreeNode *Right;
 11 } BTNode;
 12 
 13 BTNode *CreateTree(BTNode *root)
 14 {
 15 //先序递归创建二叉树，
 16 //输入范例：abd#g##e##cf#h###
 17 /*
 18        a
 19      /  
 20     /    
 21    b      c
 22   /     /
 23  d   e  f
 24         
 25    g      h
 26 
 27  */
 28 
 29 //对应于：  a(b(d(,g),e),c(f(,h),))
 30     char ch;
 31     scanf("%c",&ch);
 32     if(ch=='#') {
 33         //printf("--%c$$$
",ch);
 34         return NULL;
 35     }
 36     else
 37     {
 38         //printf("++%c***
",ch);
 39         root=(BTNode *)malloc(sizeof(BTNode));
 40         root->Element=ch;
 41         root->Left=CreateTree(root->Left);
 42         root->Right=CreateTree(root->Right);
 43     }
 44     return root;
 45 }
 46 
 47 void PreOrder(BTNode *b)     /*先序遍历的递归算法*/
 48 {
 49     if (b!=NULL) {
 50         printf("%c ",b->Element); /*访问根结点*/
 51         PreOrder(b->Left);
 52         PreOrder(b->Right);
 53     }
 54 }
 55 
 56 void InOrder(BTNode *b)     /*中序遍历的递归算法*/
 57 {
 58     if (b!=NULL) {
 59         InOrder(b->Left);
 60         printf("%c ",b->Element); /*访问根结点*/
 61         InOrder(b->Right);
 62     }
 63 }
 64 
 65 void PostOrder(BTNode *b) /*后序遍历递归算法*/
 66 {
 67     if (b!=NULL) {
 68         PostOrder(b->Left);
 69         PostOrder(b->Right);
 70         printf("%c ",b->Element); /*访问根结点*/
 71     }
 72 }
 73 
 74 int CountNode(BTNode *T) /*计算二叉树节点个数*/
 75 {
 76     if ( T == NULL )
 77         return 0;
 78     else 
 79         return 1+CountNode(T->Left)+CountNode(T->Right);
 80 }
 81 
 82 int CountLeafNode(BTNode *T) /*计算二叉树叶子节点个数*/
 83 {
 84     if ( T == NULL )
 85         return 0;
 86     else if ((T->Left==NULL)&&(T->Right==NULL))
 87         return 1;
 88     else 
 89         return CountLeafNode(T->Left)+CountLeafNode(T->Right);
 90 }
 91 
 92     
 93 int TreeDepth(BTNode *b)    /*求二叉树的深度 */
 94 {
 95     int leftDep,rightDep;
 96     if (b==NULL) return(0); /*空树的深度为0*/
 97     else  
 98     {
 99         leftDep=TreeDepth(b->Left);
100         /*求左子树的深度*/
101         rightDep=TreeDepth(b->Right);
102         /*求右子树的深度*/
103         return(leftDep>rightDep)?(leftDep+1):(rightDep+1);
104     }
105 }
106 
107 BTNode *FindNode(BTNode *b,ElementType x) 
108 {
109 //在二叉树中查找值为x的结点
110     BTNode *p;
111     if (b==NULL)   return NULL;
112     else if (b->Element==x)   return b;
113     else
114     {
115         p=FindNode(b->Left,x);
116         if (p!=NULL) return p; //判断子递归返回值
117         else   return FindNode(b->Right,x);
118     }
119 }
120 
121 int Like(BTNode *b1,BTNode *b2)
122 {
123     /*b1和b2两棵二叉树相似时返回1,否则返回0*/
124     int like1,like2;
125     if (b1==NULL && b2==NULL) return 1;
126     else if (b1==NULL || b2==NULL)  return 0;
127     else
128     {
129         like1=Like(b1->Left,b2->Left);
130         like2=Like(b1->Right,b2->Right);
131         return (like1 & like2);
132         /*返回like1和like2的与*/
133     }
134 }
135 
136 
137 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
138 
139 int main(int argc, char *argv[]) {
140     BTNode *T,*p;
141     T=CreateTree(p);
142     PreOrder(T);
143     printf("
Node:%i
",CountNode(T));
144     printf("LeafNode:%i
",CountLeafNode(T));
145     printf("Depth:%i
",TreeDepth(T));
146     
147     BTNode *f=FindNode(T,'c');
148     PreOrder(f);
149     
150     return 0;
151 }