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

╰+哭是因爲堅強的太久メ 2022-12-16 06:00 102阅读 0赞

### 二叉排序树 ###

*   *  1.二叉排序树
     *  2.查找
     *  3.插入
     *  4.构造
     *  5.删除
     *  6.查找效率

## 1.二叉排序树 ##

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

二叉排序树或者为空树，或者为非空树，当为非空树时有如下特点:  
1)若左子树排空，则左子树上所有结点关键字值均小于根结点的关键字。  
2)若右子树排空，则右子树上所有结点关键字值均大于根结点的关键字。  
3)左、右子树本身也分别是一 棵二叉排序树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]  
中序遍历序列: 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++;
    	}
    }

顺序不同，树也不同  
![在这里插入图片描述][20201018220111285.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]

## 5.删除 ##

**删除**

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

下面的例子是 第三种情况，删除的结点z有两颗子树。 删除结点4  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]  
在二叉排序树中删除并插入某节点，得到的二叉排序树可能相同可能不同，如下面的两个例子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 6]

## 6.查找效率 ##

**查找效率**  
平均查找长度(ASL) 取决于树的高度。  
![在这里插入图片描述][20201018221249530.png_pic_center]

解析：结点2经历一个结点，结点1和结点4都分别经历了两个结点（2\*2） 结点3 经历3个结点。  
![在这里插入图片描述][20201018221304731.png_pic_center]  
二叉排序树尽量构造成一个平衡二叉树，此时效率做高

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/66619a48da4a4de599f4f237f1c3ddde.png
[20201018220111285.png_pic_center]: /images/20221123/db86d233f8af46fa86f675ae80fe31b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/29d60f21bc0348a8a247875127b9d8ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/e5da5a49b84b46f7ade954d23c5dda93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/ea0141b049a94455a045b0f0b8545038.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/b734573d0bb04666a7be1b6649ffc79d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/f9d2d5761a1747e3b4ab8e752a8ac712.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/f317a872f4b34a27bbeb559a15bc898a.png
[20201018221249530.png_pic_center]: /images/20221123/b9f7ec3b478b4ae6985fb0f6037df8d9.png
[20201018221304731.png_pic_center]: /images/20221123/acbe6360bce64f6cb842eba3fdd43df6.png