前言

二叉查找树的插入，删除等操作上都运用了递归来实现。首先，需要了解递归在执行递归调用之后的语句要以之前保存的变量反方向执行。

Insert


这里的if-else看成一块，而return看成另一块。

  1. 每次插入会比较节点的大小，大的return右孩子，小的return左孩子，直到找的到孩子为NULL就创建节点
    T->Left = Insert(X, T->Left);T->Right = Insert(X, T->Right);

  2. 如果，我们传入根节点，那么递归调用之前的语句被执行后，均按被调函数相反的顺序执行。所以，最后会传回根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
SearchTree Insert(ElementType X, SearchTree T)
{
    if(T == NULL)
    {
        /* Create and return a one-node tree */
        T = malloc(sizeof(TreeNode));
        if(T == NULL)
            Error("Out of space.");
        else
        {
            T->e = X;
            T->Left = T->Right = NULL;
        }
    }
    else if(X < T->e)
        T->Left = Insert(X, T->Left);
    else if(X > T->e)
        T->Right = Insert(X, T->Right);

    return T;
}

Delete

main idea

  1. 节点N只有一个儿子（或没有儿子）
    查找N。TmpCell记录N，将N的节点指向N的唯一一个儿子（或NULL），再free掉TmpCell
  2. N有两个儿子
    查找N。将N->e = (N的右子树中最小的e)。
    再查找那个最小的e，free掉（即删除N只有一个儿子的操作）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
SearchTree Delete(ElementType X, SearchTree T)。
{
    Position TmpCell;
    if(T == NULL)
        Error("Element not found");
    else if(X < T->e)
        T->Left = Delete(X, T->Left);
    else if(X > T->e)
        T->Right = Delete(X, T->Right);
    else if(T->Left && T->Right)/* two children */
    {
        TmpCell = FindMin(T->Right);
        T->e = TmpCell->e;
        T->Right = Delete(T->e, T->Right);//T->Right = Delete的返回值
    }
    else/* One or zero children */
    {
        TmpCell = T;
        if(T->Left == NULL)
            T = T->Right;
        else if(T->Right == NULL)
            T = T->Left;
        free(TmpCell);
    }
    return T;
}

Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#ifndef _Tree_H

#include<stdio.h>
#include<stdlib.h>
#define Error(str) fprintf(stderr, "%s\n", str),exit(1)
typedef int ElementType;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef struct TreeNode
{
    ElementType e;
    SearchTree Left;
    SearchTree Right;
}TreeNode;

SearchTree MakeEmpty(SearchTree T);

Position Find(ElementType X, SearchTree T);

Position FindMin(SearchTree T);

Position FindMax(SearchTree T);

SearchTree Insert(ElementType X, SearchTree T);

SearchTree Delete(ElementType X, SearchTree T);
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include "tree.h"

SearchTree MakeEmpty(SearchTree T)
{
    if(T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X, SearchTree T)
{
    if(T == NULL)
        return NULL;
    else if(X > T->e)
        return Find(X, T->Left);
    else if(X < T->e)
        return Find(X, T->Right);
    else
        return T;
}

Position FindMin(SearchTree T)
{
    if(T == NULL)
        return NULL;
    else if(T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
}

Position FindMax(SearchTree T)
{
    if(T != NULL)
        while (T->Right != NULL)
            T = T->Right;

    return T;
}

SearchTree Insert(ElementType X, SearchTree T)
{
    if(T == NULL)
    {
        /* Create and return a one-node tree */
        T = malloc(sizeof(TreeNode));
        if(T == NULL)
            Error("Out of space.");
        else
        {
            T->e = X;
            T->Left = T->Right = NULL;
        }
    }
    else if(X < T->e)
        T->Left = Insert(X, T->Left);
    else if(X > T->e)
        T->Right = Insert(X, T->Right);

    return T;
}

SearchTree Delete(ElementType X, SearchTree T)
{
    Position TmpCell;
    if(T == NULL)
        Error("Element not found");
    else if(X < T->e)
        T->Left = Delete(X, T->Left);
    else if(X > T->e)
        T->Right = Delete(X, T->Right);
    else if(T->Left && T->Right)
    {
        TmpCell = FindMin(T->Right);
        T->e = TmpCell->e;
        T->Right = Delete(T->e, T->Right);//T->Right = Delete的返回值
    }
    else
    {
        TmpCell = T;
        if(T->Left == NULL)
            T = T->Right;
        else if(T->Right == NULL)
            T = T->Left;
        free(TmpCell);
    }
    return T;
}