主要内容 #

1. 二叉排序树
2. 二叉排序树的查找
3. 二叉排序树的删除

1. 二叉排序树 #

二叉排序树，又称二叉查找树（BST，Binary Search Tree），如图1所示。一棵二叉树或者空二叉树，或者是具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字。
• 右子树上所有结点的关键字均大于根结点的关键字。
• 左子树和右子树又各是一棵二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。二叉排序树可用于元素的有序组织、搜索。

2. 二叉排序树的查找 #

左子树结点值 < 根节点值 < 右子树根节点值若树非空，目标值与根结点的值比较：

• 若相等，则查找成功；
• 若小于根结点，则在左子树上查找，否则在右子树上查找。
• 查找成功，返回结点指针；查找失败，返回NULL。

在上节课的基础上，采用递归的方式对二叉树进行查找：

tree findn(tree bt, int n){
    if(bt){        //如果节点不为空
        if(n < bt->data) findn(bt->lchild, n); //查找左子树
        else if(n < bt->data) findn(bt->rchild, n);//查找右子树
        else return bt;
    }else return NULL;
}

3. 二叉排序树的插入 #

若原有二叉排序树为空，则直接插入结点；否则，若关键字n小于根结点的值，则插入左子树，若关键字n大于根结点值，则插入右子树。
说明：新插入的结点一定是叶子结点。

void insert(tree &bt, int n){   //插入一个节点到排序二叉树中
    if(bt){
        if(n < bt -> data) insert(bt->lchild, n);
        else if(n > bt -> data) insert(bt->rchild, n);
    }else{
        bt = new node;     //开一个新空间
        bt -> data = n;
        bt -> lchild = NULL;
        bt -> rchild = NULL;

    }
}