数据结构考研笔记（十三）——二叉排序树

1.二叉排序树

二叉排序树 BST 也称二叉查找树

二叉排序树或者为空树，或者为非空树，当为非空树时有如下特点:
1)若左子树排空，则左子树上所有结点关键字值均小于根结点的关键字。
2)若右子树排空，则右子树上所有结点关键字值均大于根结点的关键字。
3)左、右子树本身也分别是一 棵二叉排序树。

中序遍历序列: 1 2 3 4 5 7 8 10 16
左子树 根 右子树
左子树结点值<根结点值<右子树结点值
二叉排序树的中序遍历序列是一 个递增有序序列

2.查找

查找

二叉树非空时，查找根结点，若相等则查找成功;
若不等，则当小于根结点值时，查找左子树;当大于根结点的值时，查找右子树。
当查找到叶节点仍没查找到相应的值，则查找失败。

BSTNode *BST_ Search(BiTree T，ElemType key, BSTNode *&p) {
    //指针引用 *&p.P = NULL;//双亲结点 空while (T!=NULL G key!=T->data) {
     //p=T;//双亲结点赋值if(key < T->data)//小查左子树T = T->lchild ; else//大，右子树T = T->rchild ;}return T:
}

3.插入

插入

 若二叉排序树为空，则直接插入结点;若二叉排序树非空，当值小于根结点时，插入左子树;当值大于根结点时，插入右子树;当值等于根结点时不进行插入。

int BST_ Insert (BiTree GT,KeyType k) (//要插入的树，k 要插入的值1f (T==NULL) {
     //该二叉树是否为空T = (BiTree) malloc (s1 zeof (BSTNode)) ;T->key = k;T->lchild = T->rchlid = NULL;return 1 ;}else if(k == T->key)return 0 ;else 1f(k < T->key)//插入左子树return BST_ Insert (T->lchild, k);else//插入右子树return BST_ Insert (T->rchild, k);
}

4.构造

构造二叉排序树

   读入一个元素并建立结点，若二叉树为空将其作为根结点;若二叉排序树非空，当值小于根结点时，插入左子树;当值大于根结点时，插入右子树;当值等于根结点时不进行插入。

void Create_ BST (BiTree &T， KeyType str[]， int n){
      //str 结点值的数组T = NULL;int i = 0;while(i < n) {
    BST_ Insert(T, str[i]) ;i++;}
}

顺序不同，树也不同

5.删除

删除

    1)若被删除结点z是叶结点，则直接删除;2)若被删除结点z只有一-棵子树，则让z的子树成为z父结点的子树，代替z结点。3)若被删除结点z有两棵子树，则让z的中序序列直接后继代替z，并删去直接后继结点。

下面的例子是 第三种情况，删除的结点z有两颗子树。 删除结点4

在二叉排序树中删除并插入某节点，得到的二叉排序树可能相同可能不同，如下面的两个例子

6.查找效率

查找效率
平均查找长度(ASL) 取决于树的高度。

解析：结点2经历一个结点，结点1和结点4都分别经历了两个结点（2*2） 结点3 经历3个结点。

二叉排序树尽量构造成一个平衡二叉树，此时效率做高