139 ? ? }

140?

141 ? ? return 0;

142 }

143?

144 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value)

145 {//删除结点

146 ? ? BTNode *temp;

147 ? ? BTNode *root;

148 ? ? int flag; ? ? ? ?//flag标记被删除的节点，默认顶部节点flag为0，左边节点flag为-1，右边节点flag为1

149?

150 ? ? if(*phead == NULL)

151 ? ? ? ? return 0;

152 ? ? ? ??

153 ? ? if(*phead == BT->phead){

154 ? ? ? ? flag = 0;

155 ? ? ? ? root = *phead;

156 ? ? }

157?

158 ? ? else if((*phead)->lchild != NULL){

159 ? ? ? ? flag = -1;

160 ? ? ? ? root = (*phead)->lchild;

161 ? ? }

162?

163 ? ? else if((*phead)->rchild != NULL){

164 ? ? ? ? flag = 1;

165 ? ? ? ? root = (*phead)->rchild;

166 ? ? }

167 ? ? else if((*phead)->lchild == NULL && (*phead)->rchild == NULL)

168 ? ? ? ? root = *phead;

169 ? ??

170 ? ? if(root->data == value){

171 ? ? ? ? if(root->lchild != NULL){

172 ? ? ? ? ? ? temp = BT->search_max(BT, &root->lchild, 1);

173 ? ? ? ? ? ? temp->lchild = root->lchild;

174 ? ? ? ? ? ? ?temp->rchild = root->rchild;

175 ? ? ? ? ? ? free(root);

176 ? ? ? ? ? ? root = temp;

177 ? ? ? ? ? ? if(flag == 0)

178 ? ? ? ? ? ? ? ? BT->phead = root;

179 ? ? ? ? ? ? else

180 ? ? ? ? ? ? ? ? (*phead)->lchild = root;

181 ? ? ? ? }

182 ? ? ? ? else if(root->rchild != NULL){

183 ? ? ? ? ? ? temp = BT->search_min(BT, &root->rchild, 1); ??

184 ? ? ? ? ? ? temp->lchild = root->lchild;

185 ? ? ? ? ? ? temp->rchild = root->rchild;

186 ? ? ? ? ? ? free(root);

187 ? ? ? ? ? ? root = temp;

188 ? ? ? ? ? ? if(flag == 0)

189 ? ? ? ? ? ? ? ? BT->phead = root;

190 ? ? ? ? ? ? else

191 ? ? ? ? ? ? ? ? (*phead)->rchild = root;

192 ? ? ? ? }

193 ? ? ? ? else{

194 ? ? ? ? ? ? if(flag == 0)

195 ? ? ? ? ? ? ? ? free(*phead);

196 ? ? ? ? ? ? else if(flag = -1){

197 ? ? ? ? ? ? ? ? free((*phead)->lchild);

198 ? ? ? ? ? ? ? ? (*phead)->lchild = NULL;

199 ? ? ? ? ? ? }

200 ? ? ? ? ? ? else if(flag = 1){

201 ? ? ? ? ? ? ? ? free((*phead)->rchild);

202 ? ? ? ? ? ? ? ? (*phead)->rchild = NULL;

203 ? ? ? ? ? ? }

204 ? ? ? ? }

205 ? ? ? ? ?

206 ? ? ? ? tree_height(BT, BT->phead); ? ?//删除节点后，求每个节点的新高度

207?

208 ? ? ? ? if(flag == 0)

209 ? ? ? ? ? ? return 1;

210 ? ? ? ? if(flag == -1){

211 ? ? ? ? ? ? if(tree_node_height(BT, (*phead)->rchild) - tree_node_height(BT, (*phead)->lchild) == 2){

212 ? ? ? ? ? ? ? ? if((*phead)->rchild->rchild != NULL){

213 ? ? ? ? ? ? ? ? ? ? root = singleRotateRR(BT, *phead);

214 ? ? ? ? ? ? ? ? }

215 ? ? ? ? ? ? ? ? else{

216 ? ? ? ? ? ? ? ? ? ? root = doubleRotateRL(BT, *phead);

217 ? ? ? ? ? ? ? ? }

218 ? ? ? ? ? ? }

219 ? ? ? ? }

220 ? ? ? ? else{

221 ? ? ? ? ? ? if(tree_node_height(BT, (*phead)->lchild) - tree_node_height(BT, (*phead)->rchild) == 2){

222 ? ? ? ? ? ? ? ? if((*phead)->lchild->lchild != NULL){

223 ? ? ? ? ? ? ? ? ? ? root = singleRotateLL(BT, *phead);

224 ? ? ? ? ? ? ? ? }

225 ? ? ? ? ? ? ? ? else{

226 ? ? ? ? ? ? ? ? ? ? root = doubleRotateLR(BT, *phead);

227 ? ? ? ? ? ? ? ? }

228 ? ? ? ? ? ? }

229 ? ? ? ? }

230 ? ? ? ? ? ??

231 ? ? ? ? return 1;

232 ? ? }

233 ? ? else if(root->data > value)

234 ? ? ? ? return BT->del(BT, &root->lchild, value);

235 ? ? else

236 ? ? ? ? return BT->del(BT, &root->rchild, value);

237?

238 ? ? return 0;

239 }

240?

241 static BOOL tree_del_tree(BTree *BT, BTNode **phead)

242 {//删除二叉树

243 ? ? if(*phead == NULL)

244 ? ? ? ? return 0;

245 ? ??

246 ? ? if((*phead)->lchild != NULL)

247 ? ? ? ? BT->del_tree(BT, &(*phead)->lchild);

248 ? ? if((*phead)->rchild != NULL)

249 ? ? ? ? BT->del_tree(BT, &(*phead)->rchild);

250?

251 ? ? free(*phead);

252 ? ? *phead = NULL;

253?