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

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

typedef struct Node{
    int data;
    struct Node *left, *right;
} Node;

Node* BSTroot = NULL;

//建新節
Node* newNode(int val)  {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;  
    node->right = node->left = NULL;
    
    return node;
}

//前序印出BST樹
void preOrder(Node* root) {
    if(root) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

//插入BST樹（用while迴圈配合指標做）
void insert(int val){
    Node **ptr = &BSTroot;                  //依址找值
    while(*ptr != NULL){                    //找要插入的樹葉的位址
        if(val < (*ptr)->data)
            ptr = &(*ptr)->left;
        else if(val > (*ptr)->data)
            ptr = &(*ptr)->right;
        else
            break;
    }
    if(*ptr == NULL)                        //要插位的位置為空表示無重複
        *ptr = newNode(val);                        //新節點插入此位址
}

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

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

int main(void){
    int val;
    char SENT;

    //對BST樹的操作
    printf("<1: 插入> <2: 刪除> <3: 列出(前序)> <q: 離開>\n選擇操作 : ");
    scanf(" %c", &SENT);
    while(SENT != 'q'){
        switch(SENT) { 
            case '1':
                printf("輸入要插入的數: ");
                scanf("%d", &val);
                insert(val);
                break; 
            case '2':
                printf("輸入要刪除的數: ");
                scanf("%d", &val);
                remove(val);
                break; 
            case '3':
                preOrder(BSTroot);
                putchar('\n');
                break; 
            default: 
                break;
        }
        printf("\n<1: 插入> <2: 刪除> <3: 列出(前序)> <q: 離開>\n選擇操作 : ");
        scanf(" %c", &SENT);
    }

    system("pause");
    return 0;
}

測試資料1：

依序插入：10 20 30 40 50 25
列出結果：10 20 30 25 40 50

測試資料2：
依序插入：9 5 10 0 6 11 -1 1 2
列出結果：9 5 0 -1 1 2 6 10 11
刪除節點：10
列出結果：9 5 0 -1 1 2 6 11
刪除節點：5
列出結果：9 6 0 -1 1 2 11
刪除節點：9
列出結果：11 6 0 -1 1 2