数据结构Note-Binary Seeking Tree

---

定义

二分查找树BST（也叫二叉查找树、二叉排序树）的提出是为了提供查找效率，之所以称为二分查找树，因为该二叉树对应着二分查找算法，查找平均的时间复杂度为o(logn)，所以该数据结构的提出是为了提高查找效率。
二分查找树或者是一棵空树，或者具有下列性质：
    1.若它的左子树不为空，则左子树上所有结点的值均小于根结点的值；
    2.若它的右子树不为空，则右子树上所有结点的值均大于根结点的值；
    3.它的左右子树均为二分查找树。

操作

二分查找树的操作主要包括：插入、查找、删除。

---

C/C++代码如下：

namespace ST {
typedef struct Node {
    double data;
    Node* _left;
    Node* _right;
    Node* _parent;
};

Node* init() {
    Node* t = (Node*)malloc(sizeof(Node));
    t->data = 0;
    t->_left = NULL;
    t->_right = NULL;
    t->_parent = NULL;
    return t;
}

Node* insert(Node* now, double x) {
    if (x < now->data) {
        if (now->_left == NULL) { now->_left = init(); now->_left->data = x; now->_left->_parent = now; }
        else { insert(now->_left, x); }
    }
    else if (x > now->data) {
        if (now->_right == NULL) { now->_right = init(); now->_right->data = x; now->_right->_parent = now;
        }
        else { insert(now->_right, x); }
    }
    return now;
}

bool find(Node* now, double x) {
    if (x < now->data) {
        if (now->_left != NULL)find(now->_left, x);
        else return false;
    }
    else if (x > now->data) {
        if (now->_right != NULL)find(now->_right, x);
        else return false;
    }
    return true;
}

double findmax_left(Node * left) {
    if (left == NULL)return 0;//当前左子树为空
    else if (left->_right == NULL)return left->data;//若当前子树存在右侧为空，直接返回data
    return findmax_left(left->_right);//若当前子树及其右子树存在，查询右子树
}

Node* remove(Node* root, double x) {
    if (x < root->data) {
        if (root->_left != NULL)remove(root->_left, x);
        else return root;
    }
    else if (x > root->data) {
        if (root->_right != NULL)remove(root->_right, x);
        else return root;
    }
    else {
        if (root->_left == NULL && root->_right == NULL) {
            root == NULL;
            return root;
        }
        if (root->_left == NULL && root->_right != NULL) {
            root = root->_right;
            return root;
        }
        if (root->_left != NULL && root->_right == NULL) {
            root = root->_left;
            return root;
        }
        if (root->_left != NULL && root->_right != NULL) {
            double val = findmax_left(root->_left);
            root->data = val;
            root->_left = remove(root->_left, val);
            return root;
        }
    }
    return root;
}

void depth_first_search(Node* root) {
    if (root != NULL) {
        //operational function//
        depth_first_search(root->_left);
        depth_first_search(root->_right);
    }
    }
}

---