1 #include <stdio.h>
2
3 typedef struct tagBinaryTree* Node;
4 typedef struct tagBinaryTree BinaryTree;
5
6 struct tagBinaryTree{
7 int key;
8 Node lchild;
9 Node rchild;
10 Node parent;
11 };
12 typedef struct //定义栈的结构体
13 {
14 Node *base; //在栈构造前和销毁后，base的值为NULL
15 Node *top; //栈顶指针
16 int stacksize; //当前已分配的存储空间，以元素为单位
17 }Stack;
18 int Key(Node branch)
19 {
20 if(branch == NULL) return 0;
21 return branch->key;
22 }
23
24 Node Left(Node branch)
25 {
26 if(branch == NULL) return NULL;
27 return branch->lchild;
28 }
29
30 Node Right(Node branch)
31 {
32 if(branch == NULL) return NULL;
33 return branch->rchild;
34 }
35
36 Node Parent(Node branch)
37 {
38 if(branch == NULL) return NULL;
39 return branch->parent;
40 }
41 Node LookUp(Node T, int key)
42 {
43 while(T != NULL && Key(T) != key){
44 if(key < Key(T)){
45 T = Left(T);
46 }else{
47 T = Right(T);
48 }
49 }
50 return T;
51 }
52 Node CreateLeaf(int x, Node* T)
53 {
54 Node n = malloc(sizeof(BinaryTree));
55 n->lchild = n->rchild = n->parent = NULL;
56
57 n->key = x;
58 *T = n;
59 return n;
60 }
61
62 int InsertKey(int key, Node* T)
63 {
64 Node root = *T,parent = NULL,x = NULL;
65 x = LookUp(*T, key);
66 if(x != NULL) return 0;
67 CreateLeaf(key, &x);
68
69 while(root != NULL){
70 parent = root;
71 if(key < Key(root)){
72 root = Left(root);
73 }else if(key > Key(root)){
74 root = Right(root);
75 }else{
76 return 0;
77 }
78 }
79 x->parent = parent;
80
81 if(parent == NULL) {
82 *T = x;
83 return 0;
84 }else if(key < Key(parent)){
85 parent->lchild = x;
86 }else{
87 parent->rchild= x;
88 }
89 return 0;
90 }
91
92 int PreOrderTravel(Node T, Stack S)
93 {
94 while( S.base != S.top|| T != NULL) //判断栈和树是否为空
95 {
96 while( T !=NULL ) //向左子树一直循环到最左的节点
97 {
98 printf("%d ",T->key); //输出元素
99 *S.top++ = T;
100 T = T->lchild;
101 }
102 T = *--S.top; //实现出栈
103 T = T->rchild; //转向右子树
104 }
105 printf("\n");
106 return 0;
107 }
108 int InOder(Node T,Stack S) //实现非递归中序遍历函数
109 {
110 while( S.base != S.top || T != NULL) //判断栈和树是否为空
111 {
112 while(T!=NULL) //向左子树一直循环到最左的节点
113 {
114 *S.top++ = T;
115 T = T->lchild;
116 }
117 T = *--S.top; //实现出栈
118 printf("%d ", T->key);
119 T = T->rchild; //转向右子树
120 }
121 printf("\n");
122 return 0;
123 }
124
125 int PostOrder(Node T,Stack S) //实现非递归后序遍历函数
126 {
127 Node temp=NULL; //定义临时变量，用来标记刚刚访问过的节点
128 while( S.base != S.top || T!= NULL ) //判断栈和树是否为空
129 {
130 while(T!=NULL) //向左子树一直循环到最左的节点
131 {
132 *S.top++ = T;
133 T = T->lchild;
134 }
135 T = *(S.top-1); //取栈顶节点
136 if( T->rchild == NULL || T->rchild == temp)
137 { //如果该节点没有右孩子或者其右孩子刚刚被访问过
138 printf("%d ",T->key); //输出元素
139 S.top--; //已访问，使其出栈
140 temp=T; //标记为刚刚访问过
141 T=NULL; //若遍历完以该节点为根的子树，且栈空，则结束，否则继续
142 } else{
143 T = T->rchild; //转向右子树
144 }
145 }
146 printf("\n");
147 return 0;
148 }
149 int CreatStack(Stack* S) //实现栈的建立函数
150 {
151 S->base=(Node*)malloc(100*sizeof(Node));
152 if(!S->base) //判断是否建立失败
153 return -1;
154 S->top=S->base;
155 S->stacksize=100;
156 return 0;
157 }
158 void DestoryStack(Stack* s)
159 {
160 if(!s || !s->base){
161 return ;
162 }
163 free(s->base);
164 memset(s, 0, sizeof(Stack));
165 }
166 Node FollowNode(Node T, int key)
167 {
168 Node cur = LookUp(T, key);
169
170 if(cur->rchild){
171 Node right = cur->rchild;
172 while(right->lchild != NULL){
173 right = right->lchild;
174 }
175 return right;
176 }else if(Parent(cur)){
177 Node parent= Parent(cur);
178 while(parent != NULL && Right(parent) == cur ){
179 cur=parent;
180 parent = Parent(parent);
181 }
182 return parent;
183 }
184 return NULL;
185 }
186
187 Node PreNode(Node T, int key)
188 {
189 Node cur = LookUp(T, key);
190 if(cur->lchild){
191 Node left = cur->lchild;
192 while(left->rchild != NULL){
193 left = left->rchild;
194 }
195 return left;
196 }else if(Parent(cur)){
197 Node parent = Parent(cur);
198 while(parent != NULL && Left(parent) == cur){
199 cur = parent;
200 parent = Parent(parent);
201 }
202 return parent;
203 }
204 return NULL;
205 }
206 Node DeleteNode(Node* T, int key)
207 {
208 Node cur = LookUp(*T, key);
209 Node root = *T,old_cur = cur, parent = NULL;
210
211 if(root == NULL || cur == NULL){
212 return *T;
213 }
214 parent = cur->parent;
215 if(cur->lchild == NULL){
216 cur = cur->rchild;
217 }else if(cur->rchild == NULL){
218 cur = cur->lchild;
219 }else{
220 Node right = cur->rchild;
221 while(right->lchild != NULL){
222 right = right->lchild;
223 }
224 cur->key = right->key;
225 if(right->parent != cur){
226 right->parent->lchild = right->rchild;
227 if(right->rchild != NULL){
228 right->rchild->parent = right->parent;
229 }
230 }else{
231 cur->rchild = right->rchild;
232 if(right->rchild != NULL){
233 right->rchild->parent = right->parent;
234 }
235 }
236 free(right);
237 right = NULL;
238 return root;
239 }
240 if(cur != NULL){
241 cur->parent = parent;
242 }else{
243 //printf("cur is NULL\n");
244 }
245 if(root == old_cur && root->lchild == NULL && root->rchild == NULL){
246 *T = NULL;
247 //do nothing
248 }else if(parent == NULL){
249 *T =root = cur;
250 }else{
251 if(parent->lchild == old_cur){
252 parent->lchild = cur;
253 }else{
254 parent->rchild = cur;
255 }
256 }
257 free(old_cur);
258 old_cur = NULL;
259 return root;
260 }
261
262 int main(int argc, char** argv)
263 {
264 Node root = NULL, pNode = NULL;
265 Stack stack = {0};
266 int len = 0, i = 0;
267 unsigned int tdata[21] = {30, 11, 71, 15, 9, 31, 12, 24, 18,10, 3,13, 14,33,80, 47,8,5,6,26};
268 CreatStack(&stack);
269
270 while(i < 20){
271 InsertKey(tdata[i], &root);
272 i++;
273 }
274
275 PreOrderTravel(root, stack);
276 InOder(root,stack);
277 PostOrder(root,stack);
278
279 pNode = FollowNode(root, 30);
280 printf("30 follow node:%d\n", pNode->key);
281 pNode = PreNode(root, 47);
282 printf("47 pre node :%d\n", pNode->key);
283 DeleteNode(&root, 31);
284
285 PreOrderTravel(root, stack);
286 InOder(root,stack);
287 PostOrder(root,stack);
288 pNode = FollowNode(root, 30);
289 printf("30 follow node:%d\n", pNode->key);
290 pNode = PreNode(root, 47);
291 printf("47 pre node :%d\n", pNode->key);
292
293 i = 0;
294 while(i < 20){
295 DeleteNode(&root, tdata[i]);
296 i++;
297 }
298 DestoryStack(&stack);
299 return 0;
300 }
