Binary Search Tree (BST) 二元搜尋樹

↓ 這是Binary Tree，一個Node下面只能有兩個Node

↓下圖是 Binary Search Tree，4是根(root)，4左邊的左子樹中所有的Node都會小於4，右子樹的值則都會大於4

玩玩看Binary Search Tree↓

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

如何實作 Insert

從root開始，將要插入的的key值與node的data比大小，key比較大則往右走，否則往左走，走到NULL，則代表是要插入的位置。

如何實作 Search

從root開始，將要搜尋的key跟當下的node比對，如果一樣代表找到了，如果不同，將key與node的data比大小，key比較大則往右走，否則往左走，走到NULL，則代表找不到。

如何實作 preorder traversal

進階題目，有時間可自行研究，就像是DFS

如何實作 delete

進階題目，有時間可自行研究

參考資料

* http://alrightchiu.github.io/SecondRound/binary-search-tree-searchsou-xun-zi-liao-insertxin-zeng-zi-liao.html


#include<iostream>
using namespace std;

struct Node
{
    int data;
    Node *left;
    Node *right;
    Node(int num){
        data = num;
        left=NULL;
        right=NULL;
    }
};

void insertNode(Node *root ,int value){

    Node *parent = NULL;  // ptr的parent
    Node *ptr = NULL;
    Node *node = new Node(value);   // node為將要新增的node

    ptr = root; //ptr會往下探索，找出該插入Node的位置
    while (ptr != NULL) {
        parent = ptr;
        if (node->data < ptr->data){ // 判斷node是要往left 還是right 前進
            ptr = ptr->left;
        }
        else{
            ptr = ptr->right;
        }
    }

    if (node->data < parent->data){ //判斷ptr要插在端點的左邊還是右邊
        parent->left = node;
    }
    else{
        parent->right = node;
    }
}

Node* searchNode(Node *root,int key){

    Node *current = root;               // 將curent指向root作為traversal起點

    while (current != NULL && key != current->data) {  // 兩種情況跳出迴圈：
                                                      // 1.沒找到 2.有找到
        if (key < current->data){
            current = current->left;   // 向左走
        }
        else {
            current = current->right;  // 向右走
        }
    }
    return current;
}


int main(){
    int value;
    Node *root=NULL;
    root = new Node(5);

    insertNode(root,1);
    insertNode(root,3);
    insertNode(root,10);
    insertNode(root,8);

    cout<<"請輸入要找得的值:";
    cin>>value;
    if(searchNode(root,value)){
        cout<<"找到了"<<value<<endl;
    }else{
        cout<<"找不到"<<value<<endl;
    }

}

10-2 Binary Search Tree 二元搜尋樹