[C/C++] BST樹，插入及刪除（使用指標）

1
#include
2
#include
3

4
typedef struct Node{
5
    int data;
6
    struct Node *left, *right;
7
} Node;
8

9
Node* BSTroot = NULL;
10

11
//建新節
12
Node* newNode(int val)  {
13
    Node* node = (Node*)malloc(sizeof(Node));
14
    node->data = val;
15
    node->right = node->left = NULL;
16

17
    return node;
18
}
19

20
//前序印出BST樹
21
void preOrder(Node* root) {
22
    if(root) {
23
        printf("%d ", root->data);
24
        preOrder(root->left);
25
        preOrder(root->right);
26
    }
27
}
28

29
//插入BST樹（用while迴圈配合指標做）
30
void insert(int val){
31
    Node **ptr = &BSTroot;                  //依址找值
32
    while(*ptr != NULL){                    //找要插入的樹葉的位址
33
        if(val data)
34
            ptr = &(*ptr)->left;
35
        else if(val > (*ptr)->data)
36
            ptr = &(*ptr)->right;
37
        else
38
            break;
39
    }
40
    if(*ptr == NULL)                        //要插位的位置為空表示無重複
41
        *ptr = newNode(val);                        //新節點插入此位址
42
}
43

44
//找子樹中最小的樹 (從根開始往左走直到不能走)
45
Node* minValue(Node* rootT){
46
    Node* ptr = rootT;
47
    while(ptr->left)
48
        ptr = ptr->left;
49
    return ptr;
50
}
51

52
//自BST樹中刪除（用while迴圈配合指標做）
53
void remove(int val){
54
    Node **ptr = &BSTroot;                          //依址找值
55
    while(*ptr == NULL || (*ptr)->data != val){     //找要刪除的節點的位址
56
        if(val data)
57
            ptr = &(*ptr)->left;
58
        else if(val > (*ptr)->data)
59
            ptr = &(*ptr)->right;
60
    }
61
    if(*ptr != NULL){                               //要刪位的位置為空表示有找到值
62
        if((*ptr)->left == NULL || (*ptr)->right == NULL){                      //若目前節點的子樹數量為 0(無子樹) 或 1(僅左或右子樹)
63
            Node* childT = ((*ptr)->left!=NULL)? (*ptr)->left: (*ptr)->right;           //暫存左子樹或右子樹
64
            free((*ptr));                                                               //釋放目前子樹樹根記憶體
65
            (*ptr) = childT;                                                            //若無子樹，令目前節點為空 否則令其為其暫存的子樹
66
        }else{                                                                  //若目前節點 左、右子樹皆有
67
            Node* minNode = minValue((*ptr)->right);                                    //取得 右子樹最小的節點
68
            int minValue = minNode->data;                                               //取得 右子樹最小的節點的值
69
            remove(minValue);                                                           //刪除剛剛找到的節點 (註：因為右子樹最小的節點必無左子樹，故遞迴結果必為第1或第2個if)
70
            (*ptr)->data = minValue;                                                    //設目前子樹樹根的數字 為剛剛找到的節點的數字
71
        }
72
    }
73
}
74

75
int main(void){
76
    int val;
77
    char SENT;
78

79
    //對BST樹的操作
80
    printf("   \n選擇操作 : ");
81
    scanf(" %c", &SENT);
82
    while(SENT != 'q'){
83
        switch(SENT) {
84
            case '1':
85
                printf("輸入要插入的數: ");
86
                scanf("%d", &val);
87
                insert(val);
88
                break;
89
            case '2':
90
                printf("輸入要刪除的數: ");
91
                scanf("%d", &val);
92
                remove(val);
93
                break;
94
            case '3':
95
                preOrder(BSTroot);
96
                putchar('\n');
97
                break;
98
            default:
99
                break;
100
        }
101
        printf("\n   \n選擇操作 : ");
102
        scanf(" %c", &SENT);
103
    }
104

105
    system("pause");
106
    return 0;
107
}