二叉树排序树插入、创建、删除和查找#

1
// 二叉排序树插入
2
void search_createBinarySortTree_insert(TreeNode* r, int value)
3
{
4
    int v = 0;
5
    while(1)
6
    {
7
        v = r->value;
8

9
        if(value < v)
10
        {
11
            // 当value小于当前结点的值时
12

13
            if(r->lchild == NULL)
14
            {
15
                // 若当前结点没有左子树，将value赋给当前节点的左子树
16

17
                // 创建一个二叉树结点并添加到当前结点的相应位置
18
                addTreeNodeChild(r, createTreeNode(value), 'l');
19
                return;
20
            }
21
            else
22
            {
23
                // 当当前节点有左子树，去左子树找
24
                r = r->lchild;
25
            }
26
        }
27
        else
28
        {
29
            // 当value大于当前节点的值时
30

31
            if(r->rchild == NULL)
32
            {
33
                // 若当前节点没有右子树，将value赋给当前节点的左子树
34

35
                addTreeNodeChild(r, createTreeNode(value), 'r');
36
                return;
37
            }
38
            else
39
            {
40
                // 当当前节点有右子树时，去右子树找
41
                r = r->rchild;
42
            }
43
        }
44
    }
45
}

1
// 生成二叉排序树
2
TreeNode* search_createBinarySortTree(int* arr, int len)
3
{
4
    // 因为一开始是空树，所有先创建一个根节点
5
    TreeNode* root = createTreeNode(arr[0]);
6

7
    // 对剩下的元素进行插入
8
    for(int i = 1; i < len; i ++)
9
    {
10
        search_createBinarySortTree_insert(root, arr[i]);
11
    }
12
    return root;
13
}

1
// 二叉排序树删除节点
2
/*
3
target：要删除的结点
4
parent：双亲结点
5
targetIs：要删除的结点是双亲的左孩子还是右孩子，'r'表示右孩子；'l'表示左孩子。为了看起来方便没用0，1表示但发现写起来还是用0，1舒服
6
*/
7
void search_createBinarySortTree_delete(TreeNode* target, TreeNode* parent, char targetIs)
8
{
9
    if(target->lchild == NULL && target->rchild == NULL)
10
    {
11
        // 是叶子结点，直接删除
12
        deleteTreeNodeChild(parent, targetIs);
13
    }
14
    else if(target->lchild && target->rchild)
15
    {
16
        TreeNode* tmp;
17
        TreeNode* tmp_past = NULL;
18
        // 有两个孩子结点
19

20
        /*
21
        用右子树的最左边结点替代当前结点
22
        */
23
        tmp = target->rchild;
24
        while(tmp->lchild)
25
        {
26
            tmp_past = tmp;
27
            tmp = tmp->lchild;
28
        }
29

30
        // 将要替换的结点从树中删除
31
        deleteTreeNodeChild(tmp_past? tmp_past:target, tmp_past? 'l':'r');
32

33
        // 替换要删除的节点
34
        // 替换子树
35
        tmp->rchild = target->rchild;
36
        tmp->lchild = target->lchild;
37
        // 替换双亲
38
        addTreeNodeChild(parent, tmp, targetIs);
39
    }
40
    else
41
    {
42
        // 当前结点只有一个子树
43
        char haveChild;
44
        if(target->lchild)
45
            haveChild = 'l';
46
        else
47
            haveChild = 'r';
48

49
        // 让子树替代当前节点的位置
50
        addTreeNodeChild(parent, deleteTreeNodeChild(target, haveChild), targetIs);
51
    }
52

53
    // 将要删除节点的子树置空
54
    deleteTreeNodeChild(target, 'r');
55
    deleteTreeNodeChild(target, 'l');
56
}

1
// 二叉树查找
2
// 返回删除的节点
3
TreeNode* search_binarySortTreeSearch(TreeNode* root, int value)
4
{
5
    // 用来存放要删除结点的双亲
6
    TreeNode* r_past = root;
7
    //RL：用来表示要删除的结点相对于双亲是左子树还是右子树
8
    char RL;
9
    while(1)
10
    {
11
        // 未找到，返回空
12
        if(root == NULL) return NULL;
13

14
        // 找到，退出循环
15
        if(root->value == value)
16
        {
17
            break;
18
        }
19
        else if(value < root->value)
20
        {
21
            r_past = root;
22
            root = root->lchild;
23
            RL = 'l';
24
        }
25
        else
26
        {
27
            r_past = root;
28
            root = root->rchild;
29
            RL = 'r';
30
        }
31
    }
32

33
    // 删除相应结点，并返回
34
    search_createBinarySortTree_delete(root, r_past, RL);
35
    return root;
36
}

1
/*
2
测试数据：-1,5,2,7,1,4,6,8,3
3
因为忘记写根节点处理了，所有加个-1结点
4
*/
5

6
/*
7
tree：二叉排序树
8
value：要查找的树
9
*/
10
void print_result(TreeNode* tree, int value)
11
{
12
    tree = search_binarySortTreeSearch(tree, value);
13
    if(tree)
14
    {
15
        printf("找到值为 %d 的元素\n", tree->value);
16
    }
17
    else
18
    {
19
        printf("没找到值为 %d 的元素\n", value);
20
    }
21
    // 通过先序遍历和中序遍历确认树结构
22
    printf("\n先序遍历：");
23
    preOrder(tree, "%d ");
24
    printf("\n中序遍历：");
25
    inOrder(tree, "%d ");
26
}