前言

本文將用C/C++實現(xiàn)二叉搜索樹的基本操作：插入、搜索并齐、刪除妖泄，以及詳細的原理介紹驹沿。

二叉搜索樹

一個節(jié)點的示意

有了這個概念驯妄，那么我們構建二叉搜索樹將會變得異常簡單。

構建

先寫個節(jié)點吧合砂。

typedef struct Node
{
    int data;
    Node *pLeft;
    Node *pRight;
} Node;

這樣青扔，名為Node的節(jié)點便被定義好了。

為了方便儲存root節(jié)點翩伪，那就再定義一個Tree微猖，專門來儲存root節(jié)點吧。

typedef struct Node *Tree;

構建樹的關鍵就在元素的插入上缘屹，所以我們來寫一個插入函數(shù)凛剥。

Node *createNode(int data) // 初始化一個節(jié)點
{
    Node *n = (Node*) malloc(sizeof(Node));
    n -> data = data;
    n -> pLeft = NULL;
    n -> pRight = NULL;
    return n;
}

void insert(int data, Tree *tree) // 向一棵樹中插入數(shù)據(jù)
{
    if (*tree == NULL) // 如果樹是空的，那就直接創(chuàng)建節(jié)點
    {
        *tree = createNode(data); // 創(chuàng)建節(jié)點
    } else {
        Node *current = *tree; // 記錄當前遍歷到的節(jié)點
        while (1) // 其實也能用遞歸寫囊颅，但是循環(huán)比較好理解
        {
            if (data >= current -> data) { // 如果待插入的數(shù)據(jù)比已存在的數(shù)據(jù)大
                if (current -> pRight != NULL) current = current -> pRight; // 如果已存在數(shù)據(jù)当悔，那就繼續(xù)往下遍歷吧
                else
                {
                    current -> pRight = createNode(data); // 到末尾了，那就新建一個節(jié)點吧
                    break; // 跳出尋找空節(jié)點
                }
            }
            else { // 如果待插入的數(shù)據(jù)比已存在的數(shù)據(jù)小
                if (current -> pLeft != NULL) current = current -> pLeft; // 如果已存在數(shù)據(jù)踢代，那就繼續(xù)往下遍歷吧
                else
                {
                    current -> pLeft = createNode(data); // 到末尾了盲憎，那就新建一個節(jié)點吧
                    break; // 跳出尋找空節(jié)點
                }
            }
        }
    }
}

那么在主程序中使用就是這樣的：

int main()
{
    printf("Construct tree (. means end):"); // 輸入數(shù)據(jù)，以“.”結束
    Tree tree = NULL; // 首先設置root節(jié)點的指針為空
    int data; // 數(shù)據(jù)
    int hasNum; // 是否有數(shù)字
    char c; // 讀入的字符
    while (1) // 始終讀入
    {
        data = 0; // 初始化數(shù)字 = 0
        hasNum = 0; // 一開始讀入并沒有數(shù)字
        while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 遇到“空格”或者“回車符”的時候胳挎，如果有數(shù)字饼疙，那就跳出當前數(shù)字的輸入
        {
            if (c >= '0' && c <= '9') { // 遇到了數(shù)字
                data = data * 10 + c - '0'; // 添加至數(shù)據(jù)
                hasNum = 1; // 有數(shù)字了
            }
            if (c == '.') // 遇到了結束輸入的標志
            {
                if (hasNum) insert(data, &tree); // 加入還有數(shù)字輸入，那就加入樹中
                break; // 跳出循環(huán)
            }
        }
        if (c == '.') break; // 遇到結束輸入標志就跳出輸入
        insert(data, &tree); // 插入數(shù)據(jù)至樹
    }
    printf("%p\n",tree); // 輸出root節(jié)點的地址
    printTree_h(tree, 0, NULL, 0); // 打印樹
}

順便附上《C/C++ 二叉樹》中的那個print_binTree();的源碼慕爬。

struct ps {
    int dps;
    int length;
    int type;
};

void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
    if (root == NULL) return;
    
    ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
    if (dps.size() <= d) dps.push_back(p);
    else dps[d] = p;
    print_binTree(root -> right,d + 1, 1, dps);
    for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
    {
        if (i -> type && i -> dps != 0) printf("|");
        else printf(".");
        for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
        {
            printf(".");
        }
    }
    if (d != 0) printf("|-");
    printf("%d",root -> data);
    if (root -> left != NULL || root -> right != NULL) printf("-|");
    printf("\n");
    dps[d].type = root -> left != NULL && lr;
    print_binTree(root -> left,d + 1, 0, dps);
}

這樣窑眯，一顆二叉搜索樹就構建完成了。

操作

之前的構建過程中我們其實已經(jīng)將插入操作實現(xiàn)好了医窿，那么現(xiàn)在我們就來實現(xiàn)一下查找的操作吧磅甩。

如果大家了解過二分法，那么你會發(fā)現(xiàn)姥卢，他其實隱性地使用了二叉查找樹卷要。我們的查找實現(xiàn)也和二分法有一些相似。

搜索

// 搜索節(jié)點
Node* findNode(Tree root, int n)
{
    Node *current = root; // 當前節(jié)點
    while (current != NULL) // 如果當前節(jié)點不為空独榴，那就繼續(xù)往下搜索
    {
        if (n > current -> data) current = current -> pRight; // 如果數(shù)據(jù)大于當前節(jié)點僧叉，那就繼續(xù)往右搜尋
        else if (n < current -> data) current = current -> pLeft; // 如果數(shù)據(jù)小于當前節(jié)點，那就繼續(xù)往左搜尋
        else return current; // 如果數(shù)據(jù)相等棺榔，那就找到了瓶堕，返回找到的節(jié)點指針
    }
    return NULL; // 沒找到
}

刪除

正如所有數(shù)據(jù)結構中的刪除操作一樣，二叉搜索樹中的刪除操作也是所有操作中最復雜的症歇。
我們可以想一下刪除的過程郎笆，由于葉子的位置可以不同谭梗，所以就有很多種情況。

一顆二叉搜索樹

情況1：葉子下面沒有任何子葉子

如果是這樣的話题画，那就直接刪除該葉子節(jié)點默辨，并將其父節(jié)點的指針變量指向NULL。

比如苍息，要刪除8這個數(shù)字缩幸，那就直接從9那邊移除8這個節(jié)點的指針，然后再free掉8這個節(jié)點就行了竞思。

圖示

所以表谊，在刪除之前，我們應先定位到8這個節(jié)點以及它的父節(jié)點9盖喷，以便我們操作爆办。

所以先來實現(xiàn)一個比較高級的查找函數(shù)：

Node* findNodeWithParent(Tree &root, int data, Node** &parent)
{
    Node *current = root; // 當前節(jié)點先置為root節(jié)點
    Node **p = &root; // 取出root節(jié)點的地址
    while (current != NULL)
    {
        if (data > current -> data) { // 和普通搜索一樣，找大小
            p = &current -> pRight; // 將其子節(jié)點的指針的指針給p课梳，方便修改這個指針變量
            current = current -> pRight;
        }
        else if (data < current -> data) {
            p = &current -> pLeft;
            current = current -> pLeft;
        }
        else {
            parent = p; // 賦值給parent
            return current; // 返回找到的當前節(jié)點
        }
    }
    return NULL; // 沒找著
}

這樣就能即找到要刪除的節(jié)點本身距辆，以及該節(jié)點的父節(jié)點指向這個節(jié)點的指針變量的指針了，只有用二次指針我才能修改這個指針變量的值暮刃。

同樣的跨算，我們再寫一個刪除函數(shù)。

void delNode(Node* &del, Node** &parent)
{
    if (del == NULL) printf("NF\n"); // 如果沒找到椭懊，那就打印NF
    else
    {
        // 直接刪除：
        if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點沒有子節(jié)點
            *parent = NULL; // 直接將其父節(jié)點指向它的指針變量置為NULL
            free(del); // 釋放要刪除的元素的內存
        }
    }
}

那么如何調用他們倆呢：

int num_del; // 定義一個讀入待刪除的數(shù)
scanf("%d",&num_del); // 讀入
Node **parent; // 定義準備尋找的待刪除節(jié)點的父親節(jié)點中 指向待刪除節(jié)點的指針變量 的指針
parent =  NULL;
Node *del; // 定義待刪除節(jié)點
del = findNodeWithParent(tree, num_del, parent); // 找節(jié)點
delNode(del, parent); // 刪除節(jié)點
printTree_h(tree, 0, NULL, 0); // 打印刪除之后的樹

這樣诸蚕，簡單的刪除就完成了。

情況2：葉子下面有且僅有一片子葉子

比如刪除我們的4號節(jié)點氧猬。

圖示

過程：和圖中畫的一樣背犯。

• 我們先記錄下4節(jié)點的子節(jié)點——3號節(jié)點；
• 把4號從它的父節(jié)點2號那移除盅抚；
• 將2號節(jié)點中空出來的那個指針變量重新指向4號下方的3號漠魏。

這也是一種比較簡單的刪除方式，代碼實現(xiàn)如下：

if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點有且僅有子左節(jié)點
    *parent = del -> pLeft; // 將其父節(jié)點指向它的子節(jié)點
    free(del); // 釋放要刪除的元素的內存
}
else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要刪除的節(jié)點有且僅有子右節(jié)點
    *parent = del -> pRight; // 將其父節(jié)點指向它的子節(jié)點
    free(del); // 釋放要刪除的元素的內存
}

和之前的函數(shù)整合起來就是這樣：

void delNode(Node* &del, Node** &parent)
{
    if (del == NULL) printf("NF\n"); // 如果沒找到妄均，那就打印NF
    else
    {
        // 直接刪除：
        if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點沒有子節(jié)點
            *parent = NULL; // 直接將其父節(jié)點指向它的指針變量置為NULL
            free(del); // 釋放要刪除的元素的內存
        }
        // 只有一邊
        else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點有且僅有子左節(jié)點
            *parent = del -> pLeft; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
        else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要刪除的節(jié)點有且僅有子右節(jié)點
            *parent = del -> pRight; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
    }
}

情況3：葉子下面有兩片子葉子

這種情況是最復雜的蛉幸，同時也有兩種刪除方式。下面則介紹了這兩種刪除方式的操作：

• 從待刪除節(jié)點的左節(jié)點開始丛晦，找到其余最大的子節(jié)點，并將其數(shù)值給待刪除的節(jié)點提陶，刪除這個最大的子節(jié)點烫沙。
• 從待刪除節(jié)點的右節(jié)點開始，找到其余最小的子節(jié)點隙笆，并將其數(shù)值給待刪除的節(jié)點锌蓄，刪除這個最小的子節(jié)點升筏。

還是圖解比較清晰。

圖示

上圖中瘸爽，我們要刪除5號元素您访，因此我們可以有兩個方案，首先先找到左節(jié)點下最大的子節(jié)點4剪决，把它給5號節(jié)點灵汪，這樣5號就消失了，接下來柑潦，我們在刪除重復的4號元素享言。值得注意的是，最大的子節(jié)點最多還有一個子節(jié)點渗鬼，并不會再次出現(xiàn)同時擁有兩個節(jié)點的情況览露，所以，刪除這個最大或者是最小子節(jié)點只要用前兩種情況中的刪除方式就行了譬胎。另外一個方案其實也十分類似差牛，大家類比一下就好了，沒有區(qū)別的堰乔。

不過關于兩個方案的選擇我還是提一下偏化，如果你的二叉搜索樹沒有嚴格的關系的話，兩種方式均可浩考，如果有允許相同元素存在的話夹孔，那就看情況選擇往左刪還是往右刪。

完整實現(xiàn)代碼：

void delNode(Node* &del, Node** &parent)
{
    if (del == NULL) printf("NF\n"); // 如果沒找到析孽，那就打印NF
    else
    {
        // 直接刪除：
        if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點沒有子節(jié)點
            *parent = NULL; // 直接將其父節(jié)點指向它的指針變量置為NULL
            free(del); // 釋放要刪除的元素的內存
        }
        // 只有一邊
        else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點有且僅有子左節(jié)點
            *parent = del -> pLeft; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
        else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要刪除的節(jié)點有且僅有子右節(jié)點
            *parent = del -> pRight; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
        // 兩邊都有
        else
        {
            printf("Which mode?(l=left,r=right,other=cancel):\n");
            char b;
            scanf(" %c",&b);
            switch (b)
            {
                case 'l':
                    Node *left;
                    left = del -> pLeft;
                    Node *big;
                    Node **maxP;
                    maxP = &del -> pLeft;
                    big = findMaxWithParent(left, maxP);
                    del -> data = big -> data;
                    delNode(big, maxP);
                    break;
                case 'r':
                    Node *right;
                    right = del -> pRight;
                    Node *small;
                    Node **minP;
                    minP = &del -> pRight;
                    small = findMinWithParent(right, minP);
                    del -> data = small -> data;
                    delNode(small, minP);
                    break;
                default:
                    goto cancel;
                    break;
            }
        }
    }
cancel:
    return;
}

我的代碼里實現(xiàn)了選擇用哪種刪除方式搭伤，實際運用時可以不必這么搞，看情況就行了袜瞬。

上邊需要用到的兩個找最大最小值的函數(shù)：

Node* findMaxWithParent(Node *n, Node** &parent)
{
    Node *current = n;
    Node **p = parent;
    while (1)
    {
        if (current -> pRight != NULL) {
            p = &current -> pRight;
            current = current -> pRight;
        } else {
            parent = p;
            break;
        }
    }
    return current;
}

Node* findMinWithParent(Node *n, Node** &parent)
{
    Node *current = n;
    Node **p = parent;
    while (1)
    {
        if (current -> pLeft != NULL) {
            p = &current -> pLeft;
            current = current -> pLeft;
        } else {
            parent = p;
            break;
        }
    }
    return current;
}

到此為止怜俐，我們就已經(jīng)實現(xiàn)了二叉搜索樹的基本操作了，下面是完整代碼邓尤。

完整代碼

//
//  main.cpp
//  BinarySearchTree
//
//  Created by 李弘辰 on 2019/8/9.
//  Copyright ? 2019 李弘辰. All rights reserved.
//

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

using namespace std;

typedef struct Node
{
    int data;
    Node *pLeft;
    Node *pRight;
} Node;

typedef struct Node *Tree;

Node *createNode(int data) // 初始化一個節(jié)點
{
    Node *n = (Node*) malloc(sizeof(Node));
    n -> data = data;
    n -> pLeft = NULL;
    n -> pRight = NULL;
    return n;
}

void insert__(int data, Tree *tree) // 向一棵樹中插入數(shù)據(jù)
{
    if (*tree == NULL) // 如果樹是空的拍鲤，那就直接創(chuàng)建節(jié)點
    {
        *tree = createNode(data); // 創(chuàng)建節(jié)點
    } else {
        Node *current = *tree; // 記錄當前遍歷到的節(jié)點
        while (1) // 其實也能用遞歸寫，但是循環(huán)比較好理解
        {
            if (data >= current -> data) { // 如果待插入的數(shù)據(jù)比已存在的數(shù)據(jù)大
                if (current -> pRight != NULL) current = current -> pRight; // 如果已存在數(shù)據(jù)汞扎，那就繼續(xù)往下遍歷吧
                else
                {
                    current -> pRight = createNode(data); // 到末尾了季稳，那就新建一個節(jié)點吧
                    break; // 跳出尋找空節(jié)點
                }
            }
            else { // 如果待插入的數(shù)據(jù)比已存在的數(shù)據(jù)小
                if (current -> pLeft != NULL) current = current -> pLeft; // 如果已存在數(shù)據(jù)，那就繼續(xù)往下遍歷吧
                else
                {
                    current -> pLeft = createNode(data); // 到末尾了澈魄，那就新建一個節(jié)點吧
                    break; // 跳出尋找空節(jié)點
                }
            }
        }
    }
}

void insert(int data, Tree *node) // 向一棵樹中插入數(shù)據(jù)景鼠，采用遞歸
{
    if (*node == NULL)
    {
        *node = createNode(data);
    } else {
        if (data >= (*node) -> data)
        {
            insert(data, &((*node) -> pRight));
        } else {
            insert(data, &((*node) -> pLeft));
        }
    }
}

void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
    if (n == NULL) return;
    
    for (int i = 0;i < h;i ++)
    {
        if (i == h - 1)
        {
            if (hasNext) printf("├── ");
            else {
                printf("└── ");
                (*l)[i] = 0;
            }
        } else
        {
            if ((*l)[i]) printf("│   ");
            else printf("    ");
        }
    }
    printf("%d\n",n -> data);
    int b = n -> pLeft != NULL;
    if (l == NULL)
    {
        vector<int> arr;
        l = &arr;
    }
    if (l -> size() <= h) l -> push_back(b);
    else (*l)[h] = b;
    // printTree(n -> pRight,h + 1,l,b); // 正常輸出
    printTree_h(n -> pRight,h + 1,l,1); // 可以顯示左右節(jié)點：├為右，└為左
    printTree_h(n -> pLeft,h + 1,l,0);
}

struct ps {
    int dps;
    int length;
    int type;
};

void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
    if (root == NULL) return;
    
    ps p = {d, (int) log10(root -> data) + 1, root -> pRight != NULL && lr == 0};
    if (dps.size() <= d) dps.push_back(p);
    else dps[d] = p;
    print_binTree(root -> pRight,d + 1, 1, dps);
    for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
    {
        if (i -> type && i -> dps != 0) printf("|");
        else printf(".");
        for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
        {
            printf(".");
        }
    }
    if (d != 0) printf("|-");
    printf("%d",root -> data);
    if (root -> pLeft != NULL || root -> pRight != NULL) printf("-|");
    printf("\n");
    dps[d].type = root -> pLeft != NULL && lr;
    print_binTree(root -> pLeft,d + 1, 0, dps);
}

// 搜索節(jié)點
Node* findNode(Tree root, int n)
{
    Node *current = root; // 當前節(jié)點
    while (current != NULL) // 如果當前節(jié)點不為空痹扇，那就繼續(xù)往下搜索
    {
        if (n > current -> data) current = current -> pRight; // 如果數(shù)據(jù)大于當前節(jié)點铛漓，那就繼續(xù)往右搜尋
        else if (n < current -> data) current = current -> pLeft; // 如果數(shù)據(jù)小于當前節(jié)點溯香，那就繼續(xù)往左搜尋
        else return current; // 如果數(shù)據(jù)相等，那就找到了浓恶，返回找到的節(jié)點指針
    }
    return NULL; // 沒找到
}

Node* findNodeWithParent(Tree &root, int data, Node** &parent)
{
    Node *current = root; // 當前節(jié)點先置為root節(jié)點
    Node **p = &root; // 取出root節(jié)點的地址
    while (current != NULL)
    {
        if (data > current -> data) { // 和普通搜索一樣玫坛，找大小
            p = &current -> pRight; // 將其子節(jié)點的指針的指針給p，方便修改這個指針變量
            current = current -> pRight;
        }
        else if (data < current -> data) {
            p = &current -> pLeft;
            current = current -> pLeft;
        }
        else {
            parent = p; // 賦值給parent
            return current; // 返回找到的當前節(jié)點
        }
    }
    return NULL; // 沒找著
}

Node* findMaxWithParent(Node *n, Node** &parent)
{
    Node *current = n;
    Node **p = parent;
    while (1)
    {
        if (current -> pRight != NULL) {
            p = &current -> pRight;
            current = current -> pRight;
        } else {
            parent = p;
            break;
        }
    }
    return current;
}

Node* findMinWithParent(Node *n, Node** &parent)
{
    Node *current = n;
    Node **p = parent;
    while (1)
    {
        if (current -> pLeft != NULL) {
            p = &current -> pLeft;
            current = current -> pLeft;
        } else {
            parent = p;
            break;
        }
    }
    return current;
}

void delNode(Node* &del, Node** &parent)
{
    if (del == NULL) printf("NF\n"); // 如果沒找到包晰，那就打印NF
    else
    {
        // 直接刪除：
        if (del -> pLeft == NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點沒有子節(jié)點
            *parent = NULL; // 直接將其父節(jié)點指向它的指針變量置為NULL
            free(del); // 釋放要刪除的元素的內存
        }
        // 只有一邊
        else if (del -> pLeft != NULL && del -> pRight == NULL) { // 如果要刪除的節(jié)點有且僅有子左節(jié)點
            *parent = del -> pLeft; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
        else if (del -> pLeft == NULL && del -> pRight != NULL) { // 如果要刪除的節(jié)點有且僅有子右節(jié)點
            *parent = del -> pRight; // 將其父節(jié)點指向它的子節(jié)點
            free(del); // 釋放要刪除的元素的內存
        }
        // 兩邊都有
        else
        {
            printf("Which mode?(l=left,r=right,other=cancel):\n");
            char b;
            scanf(" %c",&b);
            switch (b)
            {
                case 'l':
                    Node *left;
                    left = del -> pLeft;
                    Node *big;
                    Node **maxP;
                    maxP = &del -> pLeft;
                    big = findMaxWithParent(left, maxP);
                    del -> data = big -> data;
                    delNode(big, maxP);
                    break;
                case 'r':
                    Node *right;
                    right = del -> pRight;
                    Node *small;
                    Node **minP;
                    minP = &del -> pRight;
                    small = findMinWithParent(right, minP);
                    del -> data = small -> data;
                    delNode(small, minP);
                    break;
                default:
                    goto cancel;
                    break;
            }
        }
    }
cancel:
    return;
}

int main()
{
    printf("Construct tree (. means end):"); // 輸入數(shù)據(jù)湿镀，以“.”結束
    Tree tree = NULL; // 首先設置root節(jié)點的指針為空
    int data; // 數(shù)據(jù)
    int hasNum; // 是否有數(shù)字
    char c; // 讀入的字符
    while (1) // 始終讀入
    {
        data = 0; // 初始化數(shù)字 = 0
        hasNum = 0; // 一開始讀入并沒有數(shù)字
        while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 遇到“空格”或者“回車符”的時候，如果有數(shù)字杜窄，那就跳出當前數(shù)字的輸入
        {
            if (c >= '0' && c <= '9') { // 遇到了數(shù)字
                data = data * 10 + c - '0'; // 添加至數(shù)據(jù)
                hasNum = 1; // 有數(shù)字了
            }
            if (c == '.') // 遇到了結束輸入的標志
            {
                if (hasNum) insert(data, &tree); // 加入還有數(shù)字輸入肠骆，那就加入樹中
                break; // 跳出循環(huán)
            }
        }
        if (c == '.') break; // 遇到結束輸入標志就跳出輸入
        insert(data, &tree); // 插入數(shù)據(jù)至樹
    }
    printf("%p\n",tree); // 輸出root節(jié)點的地址
    // printTree_h(tree, 0, NULL, 0); // 打印樹
    print_binTree(tree,0,1,vector<ps>()); // 打印樹
    while (true) {
        printf("Operate? (i=insert,d=delete,f=find,p=print,other=exit):");
        char choose;
        scanf(" %c",&choose);
        switch (choose) {
        case 'i':
            printf("num:");
            int m;
            scanf("%d",&m);
            insert(m, &tree);
            // printTree_h(tree, 0, NULL, 0);
            print_binTree(tree,0,1,vector<ps>());
            break;
        case 'd':
            printf("num:");
            int num_del; // 定義一個讀入待刪除的數(shù)
            scanf("%d",&num_del); // 讀入
            Node **parent; // 定義準備尋找的待刪除節(jié)點的父親節(jié)點中 指向待刪除節(jié)點的指針變量 的指針
            parent =  NULL;
            Node *del; // 定義待刪除節(jié)點
            del = findNodeWithParent(tree, num_del, parent); // 找節(jié)點
            delNode(del, parent); // 刪除節(jié)點
            // printTree_h(tree, 0, NULL, 0); // 打印刪除之后的樹
            print_binTree(tree,0,1,vector<ps>());
            break;
        case 'f':
            printf("num:");
            int n;
            scanf("%d",&n);
            printf("%d\n", findNode(tree, n) != NULL);
            break;
        case 'p':
            // printTree_h(tree, 0, NULL, 0);
            print_binTree(tree,0,1,vector<ps>());
            break;
        default:
            goto end;
            break;
        }
    }
end:
    
    return 0;
}