[数据结构与算法]树与二叉树的应用

二叉排序树

定义

二叉排序树，又称二叉查找树（BST）

左子树中的结点值<根结点值<右子树结点值

中序遍历可以得到一个递增的有序序列

查找

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ta2HdlMQ-1627293652889)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723204229610.png)]

//非递归方式

//定义二叉排序树
typedef struct BSTNode{
    ElemType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

//非递归
BSTNode *BST_Search(BSTree T,ElemType key){
    while(T!=NULL && T->key!=key){
        if(key<T->key) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

//递归方式
BSTNode *BST_Search(BSTree T,ElemType key){
    if(T==NULL)
        return NULL;
    if(key==T->key)
        return T;
    else if(key<T->key)
        return BST_Search(T->lchid,key);
    else if(key>T->key)
        return BST_Search(T->rchild,key);
}

插入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ApwNlMsW-1627293652893)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723205254090.png)]

//递归方式
int BST_Insert(BSTree &T,ElemType k){
    //若树为空，则创建一个结点进行插入
    if(T==NULL){
        //创建新结点
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;					//插入成功
    }
    else if(k==T->key){			//已经存在，失败
        return 0;
    }
    else if(k<T->key){
  	     return BST_Insert(T->lchid,k);			//插入左子树
    }
    else if(k>T->key){
     	return   BST_Insert(T->rchild,k);			//插入右子树
    }
}

//非递归方式
int BST_Insert(BSTree &T,ElemType k){
    while(T!=NULL){
        if(k==T->key){
            return 0;			//失败，重复
        }
        else if(k<T->key) T=T->lchild;
        else if(k>T->key) T=T->rchild;
    }
    
    T=(BSTNode *)malloc(sizeof(BSTNode));
    T->key==k;
    T->lchild=T->rchild=NULL;
    return 1;		//成功
}

构造

//构造二叉排序树的过程就是不断进行插入的过程
//按照str[]中的关键字序列建立二叉排序树
void Create_BST(BSTree &T,int str[],int n){
    T=NULL;			//初始时T为空树
    int i=0;
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}

//不同关键字序列可能得到同款二叉排序树
//不同关键字序列也可能得到不同的二叉排序树

删除

删除的结点是叶节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jhg5YXGw-1627293652895)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723212935953.png)]

删除的结点只有左子树或者只有右子树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kxMnazge-1627293652900)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723213014853.png)]

删除的结点既有左子树又有右子树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DheEwGKL-1627293652903)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723213120492.png)]

查找效率分析

查找长度：在查找运算中，需要比对关键字的次数称为查找长度，反映了查找时间复杂度

平均查找长度ASL（Average Search Length）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4iGFJSxt-1627293652905)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723214006398.png)]

查找失败

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9830bPLd-1627293652907)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210723214159785.png)]

平衡二叉树（AVL树）

树上任何一节点的左子树与右子树之差不超过1

结点的平衡因子：左子树高度-右子树高度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hsmWTohA-1627293652909)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210726171940862.png)]

查找效率分析

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7IjQMqPp-1627293652912)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210726173135415.png)]

哈夫曼树

构造哈夫曼树—带权路径长度最小

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O9Kq42k2-1627293652913)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210726173952885.png)]

哈夫曼编码

总结

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uW4Kkq9n-1627293652916)(C:\Users\25720\AppData\Roaming\Typora\typora-user-images\image-20210726175028007.png)]