樹的定義便是遞歸定義，所以絕大多功能采用遞歸完成
001 #include <stdio.h>
002 #include <malloc.h>
003 #include <stdlib.h>
004 #define MAX 100
005 #define ERROR 0
006 #define OK 1
007 #ifndef Type
008 typedef char Type;
009 #endif
010
011 typedef struct Bitree
012 {
013 Type data;
014 struct Bitree *lchild;
015 struct Bitree *rchild;
016 }BitNode, *BiTree;
017
018 int InitBiTree(BiTree *T)//初始化空樹
019 {
020 *T = NULL;
021 return OK;
022 }<SPAN style="COLOR: #e53333" minmax_bound="true">//假如傳入的參數是指向BitNode的指針，也就是BiTree 由於對於樹的構建是使用遞歸的方式，所以在對子樹
023 //因為子樹的類型也為BiTree 所以此時無法改變其實（傳值，形參），所以參數要使用指向Bitree的指針</SPAN> /*
024 int Creat(BiTree T)
025 {
026 Type p;
027
028 scanf("%c", &p);
029
030 if (p == ' ')
031 T = NULL;
032 else
033 {
034 T->data = p;
035 T->lchild = (BiTree)malloc(sizeof(BitNode));
036 Creat(T->lchild);
037 T->rchild = (BiTree)malloc(sizeof(BitNode));
038 Creat(T->rchild);
039 }
040 return OK;
041 }
042 */
043
044 int CreatBiTree(BiTree *T)//用遞歸的方式創建樹（前序輸入，空格表示子樹為空）
045 {
046 Type p;
047
048 scanf("%c", &p);
049
050 if (p == ' ')
051 *T = NULL;
052 else
053 {
054 *T = (BiTree)malloc(sizeof(BitNode));
055 (*T)->data = p;
056 CreatBiTree(&(*T)->lchild);
057 CreatBiTree(&(*T)->rchild);
058 }
059 return OK;
060 }
061
062 int ClearBiTree(BiTree *T)//清除樹，同樣為遞歸的方式
063 {
064 if ((*T)->lchild)
065 ClearBiTree(&((*T)->lchild));
066 if ((*T)->rchild)
067 ClearBiTree(&((*T)->rchild));
068
069 if ((*T)->lchild == NULL && (*T)->rchild == NULL)
070 {
071 free(*T);
072 *T = NULL;
073 }
074 return OK;
075 }
076
077 int BiTreeEmpty(BiTree T)//判斷樹是否為空
078 {
079 if (T == NULL)
080 return OK;
081 return ERROR;
082 }
083
084 int BiTreeDepth(BiTree T)//樹的深度
085 {
086 int hl, hr;
087 if (T == NULL)
088 return 0;
089 else
090 {
091 hl = BiTreeDepth(T->lchild);
092 hr = BiTreeDepth(T->rchild);
093 if (hl > hr)
094 return hl + 1;
095 else
096 return hr + 1;
097 }
098 }
099
100 BitNode Root(BiTree T)//返回樹的根（節點）
101 {
102 if (T == NULL)
103 {
104 printf("No Root");
105 exit(0);
106 }
107 return *T;
108 }
109
110 int InserInc(BiTree *T, Type e)//按照字母序插入節點 （小於該節點的為其左子樹，大於該節點的為其右子樹）
111 {
112 BiTree temp;
113
114 temp = (BiTree)malloc(sizeof(BitNode));
115 temp->data = e;
116
117 if (*T == NULL)
118 {
119 temp->lchild = NULL;
120 temp->rchild = NULL;
121 *T = temp;
122 }
123 else
124 {
125 if (e < (*T)->data)
126 InserInc(&((*T)->lchild), e);
127 else
128 InserInc(&((*T)->rchild), e);
129 }
130 return OK;
131 }
132
133
134 BiTree Search(BiTree T, Type p)//返回值為p的節點，否則為空
135 {
136 BiTree temp;
137 if (T == NULL)
138 return ERROR;
139 else
140 {
141 if (T->data == p)
142 return T;
143 else
144 {
145 temp = Search(T->lchild, p);
146 if (temp == NULL)
147 temp = Search(T->rchild, p);
148 }
149 }
150 return temp;
151 }
152
153 int DeleteChild(BiTree *T, BiTree p, int flag)//刪除值為p的節點的子樹，flag=1刪除右子樹，flag=0刪除左子樹
154 {
155 BiTree tar;
156
157 tar = Search(*T, p->data);
158 if (tar == NULL)
159 return ERROR;
160 if (flag == 0)
161 {
162 ClearBiTree(&(tar->lchild));
163 tar->lchild = NULL;
164 }
165 else
166 {
167 ClearBiTree(&(tar->rchild));
168 tar->rchild = NULL;
169 }
170 return OK;
171 }
172
173
174 BiTree Parent(BiTree T, Type e)//返回值為e的節點的父母
175 {
176 BiTree cur;
177
178 if (T == NULL)
179 return NULL;
180 else
181 {
182 if ((T->lchild)->data == e || (T->rchild)->data == e)
183 cur = T;
184 else
185 {
186 cur = Parent(T->lchild, e);
187 if (cur == NULL)
188 cur = Parent(T->rchild, e);
189 }
190 }
191 return cur;
192 }
193
194 BiTree LeftChild(BiTree T, Type e)//返回左孩子
195 {
196 BiTree result;
197
198 if (T == NULL)
199 return NULL;
200 else
201 {
202 if (T->data == e)
203 return T->lchild;
204 else
205 {
206 result = LeftChild(T->lchild, e);
207 if (result == NULL)
208 result = LeftChild(T->rchild, e);
209 }
210 }
211 return result;
212 }
213
214 BiTree LeftSibling(BiTree T, Type e)//返回左兄弟
215 {
216 BiTree result;
217
218 if (T->lchild == NULL || T->rchild == NULL)
219 return NULL;
220 else
221 {
222 if (T->lchild->data == e && T->rchild)
223 return T->rchild;
224 else
225 {
226 result = LeftSibling(T->lchild, e);
227 if (result == NULL)
228 result = LeftSibling(T->rchild, e);
229 }
230 }
231 return result;
232 }
233
234 int main()
235 {
236 BiTree T;
237 BitNode root;
238 BiTree temp;
239 int depth;
240
241 CreatBiTree(&T);
242 //ClearBiTree(&T);
243 //depth = BiTreeDepth(T);
244 //root = Root(T);
245 //InserInc(&T, 'd');
246 //temp = Search(T, 'a');
247 //Delete(&T, 'd');
248 //DeleteChild(&T, temp, 1);
249 //temp = Parent(T, 'c');
250 temp = LeftSibling(T, 'a');
251 return 0;
252 }
