BST数据结构

二叉查找树（Binary Search Treee），也称二叉搜索树，是指一课空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉搜索树；

二叉搜索树相比其他数据结构的优势在于查找、插入的时间复杂度较低。为O（log n）

插入

向一个二叉搜索树b中插入一个节点s的算法过程为：

1. 若b是空树，则将s所指节点作为根节点插入，否则：
2. 若s->data 等于b的根节点的数据域之值，则返沪，否则：
3. 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
4. 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

/* 当二元搜尋樹T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回 FALSE */
Status InsertBST(BiTree *&T, ElemType e) {
    if (!T) {
        s = new BiTNode;
        s->data = e;
        s->lchild = s->rchild = NULL;
        T = s; // 被插節点*s为新的根结点
    } else if (e.key == T->data.key)
        return false;// 关键字等于e.key的数据元素，返回錯誤
    if (e.key < T->data.key)
        InsertBST(T->lchild, e);  // 將 e 插入左子樹
    else
        InsertBST(T->rchild, e);  // 將 e 插入右子樹
    return true;
}

查找

在二叉搜索树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
    // 在根指针T所指二元查找樹中递归地查找其關键字等於key的數據元素，若查找成功，
    // 則指针p指向該數據元素節點，并返回TRUE，否則指针指向查找路徑上訪問的最後
    // 一個節點并返回FALSE，指针f指向T的雙親，其初始调用值為NULL
    if (!T) { // 查找不成功
        p = f;
        return false;
    } else if (key == T->data.key) { // 查找成功
        p = T;
        return true;
    } else if (key < T->data.key) // 在左子樹中繼續查找
        return SearchBST(T->lchild, key, T, p);
    else // 在右子樹中繼續查找
        return SearchBST(T->rchild, key, T, p);
}

遍历

中序遍历 二叉查找树的Python代码：

if node is None:
    return
traverse_binary_tree(node.leftChild, callback)
callback(node.value)
traverse_binary_tree(node.rightChild, callback)

Code

#include <iostream>


 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool addElem(TreeNode*& node, int i)
{
    if (!node) {
        node = new TreeNode(i);
        return true;
    } else {
        if (node->val==i) {
            return false;
        }
        else if (node->val<i) {
            addElem(node->right,i);
        }
        else{
            addElem(node->left,i);
        }
        return true;
    }
}

bool searchBST(TreeNode* tree,TreeNode node)
{
    if (!tree) {
        return false;
    }
    else
    {
        if (tree->val==node.val) {
            return true;
        }
        else if (tree->val>node.val)
        {
           return  searchBST(tree->left, node);
        }
        else
        {
           return  searchBST(tree->right, node);
        }
    }
}
void  inOrderTraversal(TreeNode* node)
{
    if (node) {
        inOrderTraversal(node->left);
        printf("%d ",node->val);
        inOrderTraversal(node->right);
    }
    
}
int main(int argc, const char * argv[]) {
     TreeNode*  head=NULL;
    
     addElem(head,8);
     addElem(head,3);
     addElem(head,5);
     addElem(head,6);
     addElem(head,9);
     addElem(head,7);

     inOrderTraversal(head);
    
    TreeNode tmp=TreeNode(10);
    TreeNode tmp2=TreeNode(5);
    printf("\n search tmp %d tmp2 %d\n",searchBST(head,tmp),searchBST(head,tmp2));
    
    return 0;
}