# 算法：二叉排序树的删除节点策略及其图形化（二叉树查找）

Deletion

There are three possible cases to consider:

Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

Deleting a node with one child: Remove the node and replace it with its child.

Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-

order predecessor node, R. Replace the value of N with the value of R, then delete R.

As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most

child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

```/*************************************************************************
> File Name: binarysearchtree.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:05:55 PM CST
************************************************************************/

#ifndef BST_H
#define BST_H

struct node
{
unsigned char item;
};

#endif```
```/*************************************************************************
> File Name: binarysearchtree.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:08:08 PM CST
************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include "binarysearchtree.h"

{
p->item = item;
p->left = p->right = NULL;
return p;
}

{
free(p);
}

{
if (!t)
return NULL;
if (t->item > key)
return search(t->left, key);
if (t->item < key)
return search(t->right, key);
/* if (t->item == key) */
return t;
}

{
if (!t)
return make_node(key);
if (t->item > key) /* insert to left subtree */
t->left = insert(t->left, key);
else /* if (t->item <= key), insert to right subtree */
t->right = insert(t->right, key);
return t;
}

{
if (!t)
return NULL;
if (t->item > key) /* delete from left subtree */
t->left = delete(t->left, key);
else if (t->item < key) /* delete from right subtree */
t->right = delete(t->right, key);
else   /* if (t->item == key) */
{
if (t->left == NULL && t->right == NULL)
{
/* if t is a leaf node */
free_node(t);
t =  NULL;
}
else if (t->left)  /* if t has left subtree */
{
/* replace t with the rightmost node in left subtree */
for (p = t->left; p->right; p = p->right);
t->item = p->item; /* 将左子树下最靠右的节点值赋予想要删除的节点 */
t->left = delete(t->left, t->item);
}

else  /* if t has right subtree */
{
/* replace t with the leftmost node in right subtree */
for (p = t->right; p->left; p = p->left);
t->item = p->item;
t->right = delete(t->right, t->item);
}
}
return t;
}

{
if (t)
{
printf("(");
printf("%d", t->item);
print_tree(t->left);
print_tree(t->right);
printf(")");
}
else
printf("()");
}```
```/*************************************************************************
> File Name: main2.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:22:57 PM CST
************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "binarysearchtree.h"

#define RANGE 100
#define N 6

{
printf("%d", p->item);
}

int main(void)
{
int i, key;
srand(time(NULL));
for (i = 0; i < N; i++)
{
root = insert(root, rand() % RANGE); /* 第一次循环root从NULL变成根节点值，接下去
的循环虽然迭代root，但在插入节点过程中root的值始终不变 */
printf("root = 0x%x\n", (unsigned int)root);
}

printf("\t\\tree");
print_tree(root);
printf("\n\n");

while (root)
{
key = rand() % RANGE;
if (search(root, key))
{
printf("delete %d in tree\n", key);
root = delete(root, key); /* root虽然迭代，但返回的仍是先前的值，即根节点的值保持不变
直到全部节点被删除，root变成NULL即0x0 */
printf("root = 0x%x\n", (unsigned int)root);

printf("\t\\tree");
print_tree(root); /* 传递给函数的一直是根节点的值，直到树清空，root变成NULL */
printf("\n\n");
}
}
return 0;
}```

```link FindMin(link T)
{
if (T != NULL)
while (T->left != NULL)
T = T->left;

return T;
}

{
if (T == NULL)
{
printf("Tree is empty!\n");
return NULL;
}

if (X < T->key) //go left
T->left = delete(X, T->left);
else if (X > T->key) // go right
T->right = delete(X, T->right);

/* found elem to be deleted*/
else if (T->left && T->right) //have two children
{
// replace with smallest in right subtree
tmp = FindMin(T->right);
T->key = tmp->key;
T->right = delete(T->key, T->right);
}
else //one or zero children
{
tmp = T;
if (T->left == NULL)
T = T->right;
else if (T->right == NULL)
T = T->left;
free(tmp);
}

return T;
}```

《大话数据结构》

《linux c 编程一站式学习》

《Data Structures》

0 条评论

## 相关文章

33410

1806

1965

640

2814

### 深入理解Java类加载器机制

Java里面的类加载机制，可以说是Java虚拟机核心组件之一，掌握和理解JVM虚拟机的架构，将有助于我们站在底层原理的角度上来理解Java语言，这也是为什么我们...

542

521

663

24711

2167