文档章节

平衡二叉树的建立 c语言范例

y
 yky20190625
发布于 07/19 20:10
字数 634
阅读 1
收藏 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    int high;
    struct node *lt, *rt;
};

int max(int a, int b)
{
    return a>b?a:b;
}
///深度
int deep(struct node *root)
{
    if(root==NULL)
        return -1;
    else return root->high;
}

struct node *LL(struct node *root)   // 左儿子变为根, 根变为左儿子的右儿子. 
{
    struct node *p=root->lt;
    root->lt=p->rt;     //先把p的右儿子变为root的左儿子,root的左儿子发生改变.  但是root的右儿子没变
    p->rt=root;       //根作为p的右儿子
    root->high=max(deep(root->lt), deep(root->rt))+1;  //root的左儿子lt变了, 所以root的高需要重算
    return p;     //    p的右儿子变了, 新的root也是需要重算高度的,  重算放在Insert函数最后进行
}

struct node *RR(struct node *root)  // 右儿子变为根, 根变为右儿子的左儿子. 
    struct node *p=root->rt;
    root->rt=p->lt;  //root的右儿子发生改变.  但是root的左儿子没变
    p->lt=root;
    root->high=max(deep(root->lt), deep(root->rt))+1;   //root 的右儿子变了, 需要重算高度
    return p;        //新的root也是需要重算高度的,  重算放在Insert函数最后进行
}

struct node *RL(struct node *root)
{
    root->rt=LL(root->rt);
    root=RR(root);
    return root;
}

struct node *LR(struct node *root)
{
    root->lt=RR(root->lt);
    root=LL(root);
    return root;
}

struct node *Insert(struct node *root, int num)
{
    if(!root)
    {
        root=(struct node *)malloc(sizeof(struct node));
        root->data=num;
        root->high=0;
        root->lt=NULL;
        root->rt=NULL;
    }
    else
    {
        if(num<root->data)///数据比根小
        {
            root->lt=Insert(root->lt, num);///加到左子树上

            ///先判断是否要转
            if(abs(deep(root->lt)-deep(root->rt))>1)//深度之差大于一就转
            {
               if(num>=root->lt->data)///比左子根大,转两次,即LR
                {
                    root=LR(root);
                }
                else ///比左子根小,转一次,即LL
                {
                    root=LL(root);
                }
            }

        }
        else///比根大
        {
            root->rt=Insert(root->rt, num);///加到右子树上
            if(abs(deep(root->lt)-deep(root->rt))>1)
            {
                if(num>=root->rt->data)///加到右子树的右边,转一次,RR
                {
                    root=RR(root);
                }
                else///加到右子树的左边,转两次,RL
                {
                    root=RL(root);
                }
            }
        }
    }

    root->high=max(deep(root->lt), deep(root->rt))+1;
    printf("node-data=%d, node-high=%d\n",root->data,root->high);
    return root;
}
int main()
{
    struct node *root=NULL;

    root=Insert(root,23);
    printf("root-data=%d\n", root->data);
    root=Insert(root,10);
    printf("root-data=%d\n", root->data);
    root=Insert(root,17);
    printf("root-data=%d\n", root->data);
    root=Insert(root,73);
    printf("root-data=%d\n", root->data);
    root=Insert(root,8);
    printf("root-data=%d\n", root->data);
    root=Insert(root,11);
    root=Insert(root,46);
    root=Insert(root,27);
    root=Insert(root,6);
    root=Insert(root,3);
    root=Insert(root,10);
    printf("root-data=%d\n", root->data);
    return 0;
}

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13524
作品 0
荆州
私信 提问
数据结构查找实验之平衡二叉树代码实例

数据结构查找实验之平衡二叉树代码实例 Problem Description 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 Input 输入一组测试数据。数据的第1行给出一个正整数N(n...

动感超人_Crush
2017/12/21
0
0
数据结构实验之查找二:平衡二叉树

数据结构实验之查找二:平衡二叉树 Time Limit: 400MS Memory Limit: 65536KB Submit Statistic Problem Description 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 ...

Horizonhui
2017/12/13
0
0
平衡二叉树(AVL)树

1、平衡二叉树定义 是一种二叉排序树(二叉查找树、二叉搜索树),其中每个节点的左子树和右子树的高度差不大于1。(左右子树也是平衡二叉树) 平衡因子BF = 二叉树节点的左子树深度减去右子...

笨拙的小Q
2016/07/02
70
0
谁能给我一分 c语言代码 二叉树

建立一棵二叉树,并按照先序遍历的方法输出二叉树中存储的数据 谁能给我一分 c语言代码

Andrew
2010/11/06
213
1
linux c/c++ 面试题目整理(二)

11、编写一个二分查找函数,下界为low,上界为high 递归法: 非递归法: 注意:二分查找算法前提是已经排好序的。 12、字符串逆序方法 一是原始字符串的头和尾进行交换; 二是另外开辟一个字...

晟夏的叶
2017/04/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

哪些情况下适合使用云服务器?

我们一直在说云服务器价格适中,具备弹性扩展机制,适合部署中小规模的网站或应用。那么云服务器到底适用于哪些情况呢?如果您需要经常原始计算能力,那么使用独立服务器就能满足需求,因为他...

云漫网络Ruan
今天
5
0
Java 中的 String 有没有长度限制

转载: https://juejin.im/post/5d53653f5188257315539f9a String是Java中很重要的一个数据类型,除了基本数据类型以外,String是被使用的最广泛的了,但是,关于String,其实还是有很多东西...

低至一折起
今天
17
0
OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
11
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
9
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部