- 论坛徽章:
- 0
|
1 要删除的节点存在左右子树时 ，删除有点问题，从验证程序看出来的
2 要删除的节点只有左子树 或 只有又子树 删除成功 但遍历之后最前边多出一个0.
下面附上所有文件内容
------------代码有点长，出错只有删除某个任意节点！！！！！----------------------------------------
BSTree.c 文件如下
#include"BSTree.h"
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<assert.h>
5
6 //创建一个树
7 tree* create_tree(ElementType *e)
8 {
9 node *n=(node*)malloc(sizeof(node));
10 assert(n!=NULL);
11 n->element=*e;
12 n->left=NULL;
13 n->right=NULL;
14
15 tree *t=(tree*)malloc(sizeof(tree));
16 if(t==NULL)
17 {
18 free(n);
19 return NULL;
20 }
21 t->root=n;
22 return t;
23 }
static void destroy_node(node* n)
26 {
27 if(n==NULL) return;
28 destroy_node(n->left);
29 destroy_node(n->right);
30 free(n);
31 }
32
33 //销毁树
34 void destroy_tree(tree *t)
35 {
36 if(t==NULL); return;
37 destroy_node(t->root);
38 free(t);
39 }
40
41 static node* add_node(node *n,ElementType* e)
42 {
43 node *new=(node*)malloc(sizeof(node));
assert(new!=NULL);
45 new->element=*e;
46 if(n==NULL) return new;
47 else if(*e < (n->element))
48 {
49 n->left =add_node(n->left,e);
50 }
51 else if(*e>(n->element))
52 {
53 n->right=add_node(n->right,e);
54 }
55 return n;
56 }
57 //添加一个节点
58 int add_element(tree *t,ElementType *e)
59 {
60 if(t==NULL || e==NULL) return 0;
61 t->root=add_node(t->root,e);
62 return 1;
63 }
65 static node* find_min(node* n)
66 {
67 if(n->left==NULL) return n;
68 return find_min(n->left);
69 }
70 //找到前驱节点
71 static node* qianqu_node(node* n)
72 {
73 if(n==NULL) return NULL;
74 if(n->right) n=qianqu_node(n->right);
75 return n;
76 }
77 //找到后继节点
78 static node* houji_node(node* n)
79 {
80 if(n==NULL) return NULL;
81 if(n->left) n=houji_node(n->left);
82 return n;
83 }
85 static node* remove_node(node* n,ElementType *e)
86 {
87 if(n==NULL) return NULL;
88 //递归找到要删除的节点
89 if(*e < n->element)
90 n->left=remove_node(n->left,e);
91 else if(*e > n->element)
92 n->right=remove_node(n->right,e);
93 else
94 {
95 //node* temp;
96 //要删除节点左右子树都存在
97 if(n->left && n->right)
98 {
99 node* temp;
100 node *temp1;
101 temp=qianqu_node(n->left);
102 n->element=temp->element;
103 while(temp->left)
104 {
105 temp1=qianqu_node(temp->left);
106 temp->element=temp1->element;
107 temp=temp1;
108 free(temp1);
109 temp1=NULL;
110 }
111 free(temp);
112 temp=NULL;
113 }
114 //要删除节点只有左子树
115 else if(n->left)
116 {
117 node* temp;
118 temp=qianqu_node(n->left);
119 n->element=temp->element;
120 while(temp->left)
121 {
122 temp=qianqu_node(temp->left);
123 n->element=temp->element;
124 }
125 free(temp);
126 temp=NULL;
127 }
128 //要删除节点只有右子树
129 else if(n->right)
130 {
131 node* temp;
132 temp=houji_node(n->right);
133 n->element=temp->element;
134 while(temp->right)
135 {
136 temp=houji_node(temp->right);
137 n->element=temp->element;
138 }
139 free(temp);
140 temp=NULL;
141 }
142 //要删除节点为叶子节点
143 else
144 {
145 node* temp;
146 free(n);
147 n=NULL;
148 }
149 return n;
150 }
151 return n;
152 }
153 //删除一个节点
154 int remove_element(tree *t,ElementType *e)
155 {
156 if(t==NULL || e==NULL) return 0;
157 remove_node(t->root,e);
158 return 1;
159 }
160
161 static node* find_node(node* n,ElementType* e)
162 {
163 if(n==NULL ||e==NULL) return NULL;
164 if(n->element == *e) return n;
165 else if(*e < n->element)
166 return find_node(n->left,e);
167 return find_node(n->right,e);
168 }
169
170 //查找一个元素是否存在
171 ElementType* find_element(tree* t,ElementType *e)
172 {
173 if(t==NULL || e==NULL) return NULL;
174 node* n=find_node(t->root,e);
175 if(n==NULL)
176 return NULL;
177 return &(n->element);
178 }
179
180 static saze_t size_node(node* n)
181 {
182 if(n==NULL) return 0;
183 return 1+size_node(n->left)+size_node(n->right);
184 }
185
186 //所有元素个数
187 saze_t size(tree* t)
188 {
189 if(t==NULL) return 0;
190 return size_node(t->root);
191 }
193 static void node_iterator(node* n)
194 {
195 if(n==NULL) return;
196 node_iterator(n->left);
197 printf("%d,",n->element);
198 node_iterator(n->right);
199 }
200
201 //中序遍历树
202 void mid_iterator(tree *t)
203 {
204 if(t==NULL) return;
205 node_iterator(t->root);
206 printf("\n");
207 }
208 |
|
免费注册
发表于 2015-05-09 14:02
