数据结构 ——平衡二叉树

🕗 发布于 2024-12-13 13:02 数据结构

数据结构 ——平衡二叉树

1、平衡二叉树的定义：任意节点的子树的高度差都小于等于 1
判断「平衡二叉树」的 2 个条件：

是「二叉排序树」
任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

2、二叉排序树的概念

若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
它的左、右树又分为⼆叉排序树

如下为一颗不平衡的二叉排序树，通过左旋和右旋操作转换为平衡二叉树的过程
左旋：右子树重，当前节点的右孩子成为新的根节点，旧根节点连到新根节点的最左的左子树上
右旋：左子树重，当前节点的左孩子成为新的根节点，旧根节点连到新根节点的最右的右子树上
在这里插入图片描述

3、代码实现
以下代码包括二叉树的创建，平衡过程，遍历：前序、中序、后序和按层遍历，画图和销毁等操作

#include<stdio.h>
#include<stdlib.h>
#include "../test11_queuelist/queueList.h"
#define NAMESIZE 32
//以无头节点的链表构建二叉树
struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};
struct node_st
{
    struct score_st data;
    struct node_st *l,*r;
};
struct node_st *tree=NULL;
void print_s1(struct score_st *d)
{
    printf("%d %s %d %d\n",d->id,d->name,d->math,d->chinese);
}
//插入原则：比当前节点小的插入左子树，比节点大的插入右子树 
int insert(struct node_st **root,struct score_st *data)
{
    struct node_st *node;
    //走到空节点或叶子节点
    if(*root==NULL)
    {
        node=(struct node_st*)malloc(sizeof(struct node_st));
        if(node==NULL)
            return -1;
        node->data=*data;
        node->l=NULL;//防止野指针的出现
        node->r=NULL;
        *root=node;//根节点指向创建出来的新节点，后面递归时root为传入的左或右子树的指针
        return 0; 
    }
    //比当前节点小的插入左子树，比节点大的插入右子树,递归遍历
    if(data->id<=(*root)->data.id)
     return insert(&(*root)->l,data);
    return insert(&(*root)->r,data);
}
struct score_st *find(struct node_st *root,int id)
{
    //传过来的节点为叶子节点空的左或右孩子，说明走到了一个不存在的分支
    if(root==NULL)
        return NULL;
    if(id==root->data.id)
        return &(root->data);
    //传进来的id比当前节点小，往左子树找
    if(id<root->data.id)
        return find(root->l,id);
    //传进来的id比当前节点大，往右子树找
    return find(root->r,id);
}
void draw_(struct node_st *root,int level)
{
    /*往左边倒，画出树的结构，先画当前节点的右子树，再跟节点，最后
      root->r
      root
      root->l
    */
   if(root==NULL)
       return; //空节点或空的叶子结点
   //先画右子树，右子树不止一层，所以递归调用，画右子树的右子树（当前层的下一层）
    draw_(root->r,level+1);
    //画空格,即当前节点前面的空格
    for(int i=0;i<level;i++)
        printf("  ");
    //画根节点
    print_s1(&root->data);
    //画左子树
    draw_(root->l,level+1);

}
void draw(struct node_st *root)
{
    //根据层数画出树和空格
    draw_(root,0);
    #if 0
    //测试平衡过程
    printf("\n\n");
    getchar();//暂停
    #endif
}
//以当前节点为根，计算一共有多少个节点，包括根节点
static int get_num(struct node_st *root)
{
    if(root==NULL)
        return 0;
    //左子树节点数+1（根节点）+右子树节点数
    return get_num(root->l)+1+get_num(root->r);
}
//找当前节点的左子树的叶子节点
static struct node_st *find_min(struct node_st *root)
{
    if(root->l==NULL)
        return root;
    return find_min(root->l);
}
//改变根节点的指向，传二级指针 左翻转
static void turn_left(struct node_st **root)
{
    //保存当前根节点
    struct node_st *cur=*root;
    //当前的根节点的右孩子为新的根节点
    *root = cur->r;
    cur->r=NULL;//脱链等待新连接为新根节点的左子树
    //由于新根节点可能也有左孩子，因此要找到新根节点最左的左孩子，再把旧的根节点连上去
    find_min(*root)->l=cur;
 //   draw(tree);
}
static struct node_st *find_max(struct node_st *root)
{
    if(root->r==NULL)
        return root;
    return find_max(root->r);
}
//右旋转，同理
static void turn_right(struct node_st **root)
{
    struct node_st *cur=*root;
    *root = cur->l;
    cur->l=NULL;
    find_max(*root)->r=cur;
  //  draw(tree);
}
//平衡二叉树：要改变跟节点的指向，传二级指针
void balance(struct node_st **root)
{
    int sub;
    //拿到叶子节点或空节点
    if(*root==NULL)
        return;
    while(10)
    {
        //平衡二叉树：左右子树的高度差不能超过1，先获取左右子树高度的差值
        sub=get_num((*root)->l)-get_num((*root)->r);
        //-1~1之间，说明二叉树已经平衡，不需要调整,退出循环
        if(sub>=-1 && sub<=1)
            break;
        if(sub<-1)
            //右子树的高度大于左子树的高度，左旋转
            turn_left(root);
        else
            //左子树的高度大于右子树的高度，右旋转
            turn_right(root);
    }
    //找到总的根节点，继续以新的根节点平衡左右子树
    balance(&(*root)->l);
    balance(&(*root)->r);
}
void delete(struct node_st **root,int id)
{
    //删除原则：选定删除当前节点，让其节点的左孩子顶上来
    struct node_st **node=root;
    struct node_st *cur=NULL;
    while(*node!=NULL && (*node)->data.id!=id)
    {
        //传过来的id比当前节点小，往左子树找
        if(id<(*node)->data.id)
        /*注意此处node指向当前节点的左指针，下一次循环时node拿到当前节点的左指针指向的内容数据
         即(*node)->l->data进行比较 */
            node=&(*node)->l;
        else
            node=&(*node)->r;
    }
    if(*node==NULL)
        return ;
    cur=*node;//待删除结点
    if(cur->l==NULL)
        //没有左孩子，直接用右孩子顶替？为啥是node=cur->r?
        *node=cur->r;
    else
    {
        //找到待删节点的左孩子的最右节点后，把待删节点的右孩子连到（找到的最右节点的）右边
        *node=cur->l;
        find_max(cur->l)->r=cur->r;
    }
    free(cur);
}
//先序遍历：根左右
void travelPre(struct node_st *root)
{
    if(root==NULL)
        return ;
    print_s1(&root->data);
    travelPre(root->l);
    travelPre(root->r);
}
//中序遍历：左根右
void travelMid(struct node_st *root)
{
     if(root==NULL)
        return ;
    travelMid(root->l);
    print_s1(&root->data);
    travelMid(root->r);
}
//后序遍历：左右根
void travelPost(struct node_st *root)
{
     if(root==NULL)
        return ;
    travelPost(root->l);
    travelPost(root->r);
    print_s1(&root->data);
}
//按层遍历:借助队列实现，当前节点出队时，把节点的左右孩子入队，然后再把节点出队，直到队列为空
void travelLevel(struct node_st *root)
{
    QUEUELIST *qu;
    int ret;
    struct node_st *cur;
    //sizeof(struct node_st *)=4,分配一个指针的大小，由链式队列的封装知，若传结构体的大小进去，下面就传结构体的类型的地址过去 const void *
    qu=queueList_create(sizeof(struct node_st *));
  //   qu=queueList_create(sizeof(struct node_st));
    if(qu==NULL)
        return ;
    //创建传的是指针的大小进去（指向树的起始地址），为了逻辑匹配，此处也传指针的地址进去
     queueList_en(qu,&root);
   // queueList_en(qu,root);
    while (1)
    {
        //当前节点出队,cur表示把出队的节点放到cur指针上
        ret=queueList_de(qu,&cur);
    //  ret=queueList_de(qu,cur);
        if(ret==-1)
            break;
        print_s1(&cur->data);
        //把当前节点的左右孩子入队
        if(cur->l!=NULL)
           queueList_en(qu,&cur->l);
           // queueList_en(qu,cur->l);
        if(cur->r!=NULL)
             queueList_en(qu,&cur->r);
           // queueList_en(qu,cur->r);
    }
    queueList_destroy(qu);
}
//销毁二叉树，后序遍历思想：先销毁当前节点的左子树，再销毁当前节点的右子树，最后销毁当前节点
void destroy(struct node_st *root)
{
    if(root==NULL)
        return ;
    destroy(root->l);
    destroy(root->r);
    free(root);
}
int main()
{
    int arr[]={1,2,3,7,6,5,9,8,4};
   // int arr[]={1,2,3,4,5,6};
    int i;
    struct score_st tmp,*datap;
    printf("%d \n",sizeof(struct node_st *));
    printf("%d \n",sizeof(struct node_st ));
    for(i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
    {
        tmp.id=arr[i];
        snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);
        tmp.math=rand()%100;
        tmp.chinese=rand()%100;
        //无头节点要改变指针的指向，传二级指针
        insert(&tree,&tmp);
    }
    draw(tree);
    printf("\n\n");
    balance(&tree);
    draw(tree);
    printf("\n\n");
   // travelPre(tree);
   // travelMid(tree);
   // travelPost(tree);
    travelLevel(tree);
    destroy(tree);
    #if 0
    //测试删除
    int tmpid=7;
    delete(&tree,tmpid);
    draw(tree);
    #endif
    #if 0
    //测试查找
    int tmpid=1;
    datap=find(tree,tmpid);
    if(datap==NULL)
        printf("Can not find the id %d!\n",tmpid);
    else 
        print_s1(datap);
    #endif
    return 0;
}
//gcc.exe .\balanceTree.c  ..\test11_queuelist\queueList.c ..\change\llist_change.c -o main.exe

疑问解答：
对于按层遍历中部分代码疑问解答：
void travelLevel(struct node_st *root) 实现中，
queueList_en(qu,&root);为什么传参传的是二级指针&root？
在这里插入图片描述删除结点实现

 while(*node!=NULL && (*node)->data.id!=id)
    {
        //传过来的id比当前节点小，往左子树找
        if(id<(*node)->data.id)
        /*注意此处node指向当前节点的左指针，下一次循环时node拿到当前节点的左指针指向的内容数据
         即(*node)->l->data进行比较 */
            node=&(*node)->l;
        else
            node=&(*node)->r;
    }

删除逻辑：要明白指针的含义，存放的是变量的地址，如下图片为删除id为3后，由于无左孩子，右孩子直接顶替上来的示意图
*node存储的地址变化过程为01 ，04，56
在这里插入图片描述
多级指针的指向关系

原文地址：https://blog.csdn.net/m0_55967108/article/details/144429303

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：java+ssm+mysql校园物品租赁网
下一篇：如何快速切换更新电脑网络的ip地址

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

数据结构 ——平衡二叉树

数据结构 ——平衡二叉树

相关文章