数据结构浙大陈姥姥版第四章

绝地灬酷狼 2023-07-01 04:23 2阅读 0赞

### 文章目录 ###

*  二叉搜索树
 *   *  什么是二叉搜索树(Binary Search Tree, BST)
     *  二叉搜索树的查找操作：Find
     *  查找最大和最小元素
     *  二叉搜索树的插入
     *  二叉搜索树的删除
     *  平衡二叉树
     *   *  什么是平衡二叉树
     *  平衡二叉树的调整
     *  专场：判别是不是同一个二叉搜索树
     *   *  搜索树的表示
         *  如何建搜索树
         *  搜索树的表示
         *  如何建搜索树

# 二叉搜索树 #

查找问题：

*  静态查找与动态查找
 *  针对动态查找，数据如何组织

## 什么是二叉搜索树(Binary Search Tree, BST) ##

又叫 二叉查找树，二叉排序树

二叉树不为空时，性质：

1.  非空左子树的所以键值小于其根结点的键值
2.  非空右子树的所有键值大于其根结点的键值
3.  左、右子树都是二叉搜索树

typedef struct TreeNode *BinTree;//结构指针
    typedef BinTree Position;//结构指针重命名为Position
    struct TreeNode{ 
    	ElementType Data;
    	BinTree Left;
    	BinTree Right;
    }

## 二叉搜索树的查找操作：Find ##

思路

*  查找从根结点开始，如果树为空，返回NULL
 *  若搜索树非空，则**根节点关键字和X比较**，并进行不同的处理：
    
    1.  若X小于根结点键值，只需要在左子树中继续搜索
    2.  若X大于根结点的键值，在右子树中继续搜索
    3.  若两者比较结果相等，搜索完成。返回指向该结点的指针

Position Find(ElementType X, BinTree BST)
    { 
    	if(!BST)
    		return NULL;//查找失败
    	if(X > BTS->Data)
        	return Find(X, BTS->Right);//右子树继续查找,尾递归
        Else if(X < BTS->Data)
        	return Find(X, BTS->Left);//左子树继续查找
        else//X == BTS->Data
        	return BST;//查找成功，返回找到结点的地址
    }

非递归函数的执行效率更高，可将“尾递归”函数改为循环函数

Position IterFind(ElementType X, BinTree BST)
    { 
    	while(BST){ 
    		if(X > BST->Right);
    			BST = BST->Right;//向右子树中移送，继续查找
    		else if(X < BST->Data)
    			BST = BST->Left;//向左子树中移送，继续查找
    		else 
    			return BST;//查找成功，返回结点的地址
    	}
    	return NULL;//查找失败
    			
    }

## 查找最大和最小元素 ##

*  **最大元素**一定在树的最**右**分支的端结点上
 *  最小元素一定在树的最左分支的端结点上

Position FindMin(BinTree BST)
    { 
    	if(!BST)
    		return NULL;//空的二叉树，返回NULL
    	else if(!BST->)
    		return BST;//找到最左结点并返回
    	else
    		return FindMin(BST->Left);//沿着左分支继续查找
    }

//查找最大元素的递归函数
    Position FinMax(BinTree BST)
    { 
    	if(!BST)
    		return NULL;
    	else if(!BST->Right)
    		return BST;
    	else
    		return FinMax(BST->Right);
    }

//查找最大元素的迭代函数
    Position FindMax(BinTree BST)
    { 
    	if(BST)
    		while(BST->Right)
    			BST = BST->Right;//沿着右分支查找，直到找到最右结点
    	return BST;
    }

## 二叉搜索树的插入 ##

思路：找到元素应该插入的位置。可以采用与Find类似的方法

BinTree Insert(ElementType X, BinTree BST)
    { 
    	if(!BST)//若原树为空，生成并返回一个结点的二叉搜索树
    	{ 
    		BST = malloc(sizeof(struct TreeNode));//申请空间
    		BST->Data = X;//把这个值设为X
    		BST-Left = BST->Right = NULL;//左右两边都设为NULL
    	}
    	else
    		if(X < BST->Data)
    			BST->Left = Insert(X, BST->Left);
    		else if(X > BST->Data)
    			BST->Right = Insert(X, BST->Right);
    	
    	return BST;
    }

## 二叉搜索树的删除 ##

三种情况：

1.  要删除的结点是叶结点
2.  要删除的结点只有一个子树
3.  要删除的结点有左右两颗子树
    
    1.  去右子树中的最小值替代
    2.  去左子树中找最大值替代

//
    BinTree Delete(ElementType X, BinTree BST)
    { 
        Position tmp;
        if(!BST)
            printf("not find");
        else if(X < BST->Data)
            BST->Left = Delete(X, BST->Left);//左子树递归删除
        else if(X > BST->Data)
            BST->Right = Delete(X, BST->Right);//右子树递归删除
        else//找到要删除的结点
        { 
            if(BST->Left && BST->Right)//被删除的结点有左右两个子结点
            { 
    			tmp = FindMin(BST->Right);//去右子树找最小的元素来填充被删除的结点
                BST->Data = tmp->Data;
                BST->Right = Delete(BST->Data, BST->Right);//删掉右子树的最小元素
            }
            else{ //被删除的结点有一个或者没有子结点
                tmp = BST;
                if(!BST->Left)//没有左结点或无子结点
                    BST = BST->Right;
                else if(!BST->Right)
                    BST = BST->Left;
                free(tmp);
            }
           
        }
        return BST;
    }

## 平衡二叉树 ##

### 什么是平衡二叉树 ###

结点不同的插入次序，将导致不同的**深度**和不同的查找效率及**平均查找长度ASL**

**平衡因子**(Balance Factor BF)：BF(T) = h\_L - h\_R，其中h\_L，h\_R分别是T的左右子树的高度。

**平衡二叉树**(Balance Binary Tree)(**AVL树**)：

空树，或者任一结点左右子树高度差的绝对值不超过1，即\*\*|BF(T)| <= 1\*\*

平衡二叉树的高度

斐波那契数列：

## 平衡二叉树的调整 ##

RR旋转

LL旋转

LR旋转