二叉树

  1 /*
  2 树 二叉树
  3 LJK 2018-07-05
  4 */
  5 #include<stdio.h>
  6 #include<stdlib.h>
  7 #include<math.h>
  8 
  9 #define OK 1
 10 #define ERROR 0
 11 #define TRUE 1
 12 #define FALSE 0
 13 
 14 typedef int Status;
 15 typedef char TElemType;
 16 
 17 // 节点结构
 18 typedef struct biTNode
 19 {
 20     TElemType data;                        // 节点数据
 21     struct biTNode *lchild, *rchild;    // 左右孩子指针
 22 }BiTNode;
 23 
 24 int index = 0;
 25 char String[] = "AB#D##C##";
 26 
 27 // 构造空二叉树
 28 Status InitBiTree(BiTNode **T)
 29 {
 30     *T = NULL;
 31     return OK;
 32 }
 33 
 34 // 按前序输入二叉树中节点的值（一个字符），#表示空树，构造二叉链表表示二叉树
 35 void CreateBiTree(BiTNode **T)
 36 {
 37     TElemType ch;
 38     ch = String[index++];
 39 
 40     if (ch == '#') *T = NULL;
 41     else
 42     {
 43         *T = (BiTNode *)malloc(sizeof(BiTNode));
 44         if (!(*T)) exit(OVERFLOW);
 45         (*T)->data = ch;
 46         CreateBiTree(&(*T)->lchild);
 47         CreateBiTree(&(*T)->rchild);
 48     }
 49 }
 50 
 51 // 若T为空二叉树，则返回TRUE,否则返回FALSE
 52 Status BiTreeEmpty(BiTNode *T)
 53 {
 54     if (T) return false;
 55     else return TRUE;
 56 }
 57 
 58 // 返回树的深度
 59 int BiTreeDepth(BiTNode *T)
 60 {
 61     int i, j;
 62     if (!T) return 0;
 63     if (T->lchild) i = BiTreeDepth(T->lchild);
 64     else i = 0;
 65     if (T->rchild) j = BiTreeDepth(T->rchild);
 66     else j = 0;
 67     return i > j ? i + 1 : j + 1;
 68 }
 69 
 70 // 若存在，返回T的根
 71 TElemType Root(BiTNode *T)
 72 {
 73     if (BiTreeEmpty(T)) return ' ';
 74     else return T->data;
 75 }
 76 
 77 // 前序递归遍历树
 78 void PreOrderTraverse(BiTNode *T)
 79 {
 80     if (!T) return;
 81     printf("%c ", T->data);
 82     PreOrderTraverse(T->lchild);
 83     PreOrderTraverse(T->rchild);
 84 }
 85 
 86 // 中序递归遍历树
 87 void InOrderTraverse(BiTNode *T)
 88 {
 89     if (!T) return;
 90     InOrderTraverse(T->lchild);
 91     printf("%c ", T->data);
 92     InOrderTraverse(T->rchild);
 93 }
 94 
 95 // 后序递归遍历树
 96 void PostOrderTraverse(BiTNode *T)
 97 {
 98     if (!T) return;
 99     PostOrderTraverse(T->lchild);
100     PostOrderTraverse(T->rchild);
101     printf("%c ", T->data);
102 }
103 
104 // 清空二叉树
105 void ClearBiTree(BiTNode **T)
106 {
107     if (*T)
108     {
109         if ((*T)->lchild)
110             ClearBiTree(&(*T)->lchild);
111         if ((*T)->rchild)
112             ClearBiTree(&(*T)->rchild);
113         free(*T);
114         *T = NULL;
115     }
116 }
117 
118 int main()
119 {
120     //        A
121     //       / 
122     //      B   C
123     //       
124     //        D
125     BiTNode *t; // 头指针
126     TElemType e1;
127     int i;
128 
129     InitBiTree(&t);
130     printf("初始化后，树空否？%d (1:空 0:非空)

", BiTreeEmpty(t));
131 
132     CreateBiTree(&t);
133     printf("构造空二叉树后，树空否? %d (1:空 0:非空)
", BiTreeEmpty(t));
134     printf("构造空二叉树后，树的深度 = %d

", BiTreeDepth(t));
135 
136     e1 = Root(t);
137     printf("RooTree = %c

", e1);
138 
139     printf("前序遍历二叉树: ");
140     PreOrderTraverse(t);
141     printf("

");
142 
143     printf("中序遍历二叉树: ");
144     InOrderTraverse(t);
145     printf("

");
146 
147     printf("后序遍历二叉树: ");
148     PostOrderTraverse(t);
149     printf("

");
150 
151     ClearBiTree(&t);
152     printf("After ClearTree is Empty? %d (1:Yes 0:NO) TreeDepth = %d
", BiTreeEmpty(t), BiTreeDepth(t));
153     i = Root(t);
154     if (i == ' ') printf("Tree Empty No Root.
");
155     getchar();
156     return 0;
157 }