数据结构---二叉树

news/2024/4/24 20:26:33/

专栏:数据结构
个人主页:HaiFan.
专栏简介:这里是HaiFan.的数据结构专栏,今天的内容是二叉树。

二叉树

  • 树的概念及结构
  • 二叉树概念及结构
    • 二叉树的概念
    • 二叉树的存储结构
  • 二叉树的顺序结构及实现
    • 大根堆和小根堆
    • 堆的实现及其各个接口
      • 堆的初始化和空间销毁
      • 入堆
      • 删除堆顶元素
      • 返回堆顶元素
      • 返回堆的大小
      • 判断堆是否为空
  • 二叉树的链式实现
    • 二叉树的初始化
    • 二叉树的创建
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 二叉树的销毁
    • 二叉树的大小
    • 二叉树第k层的大小
    • 二叉树查找数据

树的概念及结构

树是一种非线性的数据结构,是由n个有限结点组成的具有一个层次关系的集合,把称为树是因为把它倒着看很像一颗树。

  • 有一个特殊的结点,称为根节点,根节点没有前驱结点
  • 除根结点之后,其余的结点都是互不相交的集合,每一个集合都是一颗结构与树类似的子树。
  • 树是递归定义的

在这里插入图片描述

像这样,就被称为树。

子树一旦相交,就不再叫做树,而是另一种特殊的数据结构—图

在这里插入图片描述


除此之外,树还有一些性质。

在这里插入图片描述

节点的度:一个节点含有的子树的个数称为该节点的度,如1的度为2

叶节点或终端节点:度为0的节点称为叶节点,如4,5,6,7都是叶节点

非终端节点或分支节点:度不为0的节点 ,如1,2,3

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点 ,如1是2的父节点

孩子节点或子节点:一个节点含有的子树的根节点,如2是1的孩子节点

兄弟结点:具有同一个父节点的子树,如2和3就互为兄弟结点

树的度:树最大的节点的度称为树的度,如树的度为2

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为3

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:4和6

节点的祖先:从根到该节点所经分支上的所有节点;如上图:1是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是1的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林


那么树是怎么表示的呢?

树的结构就有点复杂了,用线性表定义树的话呢,会面临一个问题:就是一个节点可能有n个子树,那么定义多少个接口来存储该节点和子树的关系呢?这个不太好解决。于是,有大佬相出了解决办法:孩子兄弟表示法,孩子表示法等等,在这里讲解一下孩子兄弟表示法。

struct Node
{struct Node* left_child; //左孩子struct Node* right_child;//右兄弟int data;//数据
}

就比如上图中的树,

在这里插入图片描述

这样存,不管有多少个子树,都可以存储,left存左二子,right存兄弟。


二叉树概念及结构

二叉树的概念

二叉树是一种特殊的树形结构,它有一个根节点以及每个节点最多有两个子节点(一个左孩子,一个右孩子)

性质:

  1. 因为每个节点最多两个孩子,所以二叉树的最大的度不超过2
  2. 左儿子是左儿子,右儿子是右儿子,有顺序之分
  3. 叶子节点没有子节点
  4. 每一层上的节点数目都不超过2的n - 1次方,根节点为第一层
  5. 对于深度为k的二叉树来说,最多有2的n次方-1个节点,最少有k个节点
  6. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2,则有n0 = n2 + 1
  7. 若规定根节点的层数为1,具有n个结点的满二叉树的深度**,**h= log(n + 1). (ps: 是log以2为底,n+1为对数)

特殊的二叉树

满二叉树:深度为k且有2的k次方-1个节点的二叉树称为满二叉树

完全二叉树:对于深度为k的二叉树来说,除了第k层节点从左到右连续排列外,其余层节点都连续的排列

二叉树的存储结构

提到存储结构,肯定是顺序结构和链式结构。

  1. 二叉树的顺序结构就是利用数组去存储,一般使用数组只适合完全二叉树,因为不是完全二叉树会有空间的浪费(完全二叉树会使得数组中的每一个位置都存的有元素,而非完全二叉树会造成空间的浪费,想一想为什么)

  2. 链式存储:定义一个结构体,结构体中 有两个结构体指针,一个存数据,一个指针用来指向左二子,一个指针用来指向右儿子。

    typedef char TreeDataType;
    typedef struct BinaryTreeNode
    {TreeDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
    }BTNode;
    

二叉树的顺序结构及实现

普通的二叉树不适合用数组来存储数据,因为可能会造成大量的空间浪费,而完全二叉树比较适合使用顺序结构存储。

提到完全二叉树,就不得不提到堆这一概念,堆是一个数据结构而不是管理内存的一块区域分段。

大根堆和小根堆

大根堆就是每个节点的值都大于等于父节点的值,根节点的值最大

在这里插入图片描述

小根堆就是每个节点的值都小于等于父节点的值,根节点的值最小

在这里插入图片描述

堆的实现及其各个接口

实现堆,还是结构体那一套。

typedef struct Heap
{int capacity;HeapDataType* val;int count;
}Heap;void HeapInit(Heap* ps);//初始化
void HeapDestory(Heap* ps);//销毁空间void HeapPush(Heap* ps, HeapDataType x);//入堆
void HeapPop(Heap* ps);//出堆HeapDataType HeapTop(Heap* ps);//返回堆顶元素int HeapSize(Heap* ps);//堆的大小
bool HeapEmpty(Heap* ps);//堆是否为空

堆的初始化和空间销毁

之前的链表,顺序表,双链表等数据结构会的话相信堆的初始化和销毁难不倒各位。

void HeapInit(Heap* ps)
{ps->capacity = 4;ps->count = 0;ps->val = (HeapDataType*)malloc(sizeof(HeapDataType) * ps->capacity);
}void HeapDestory(Heap* ps)
{ps->capacity = ps->count = 0;free(ps->val);ps->val = NULL;
}

入堆

入堆之前要检查数组的空间是否够用,够用则直接加入数据,不够则扩容。

void HeapPush(Heap* ps, HeapDataType x)
{assert(ps);if (ps->capacity == ps->count){ps->capacity *= 2;HeapDataType* tmp = (HeapDataType*)realloc(ps->val, sizeof(HeapDataType) * ps->capacity);if (tmp == NULL){perror("malloc fail");exit(-1);}}ps->val[ps->count++] = x;HeapJustUp(ps->val, ps->count);
}

但是光加入数据可不行,要进行向上调整,把数据调整成小根堆或者大根堆,但是调整是有前提的,左右子树必须是一个堆,才不会导致堆内数据乱。所以我们每加入一个数据调整一次,即可做到堆是一个大堆或者小堆。


void HeapJustUp(HeapDataType* a, int n)
{int parent = n - 2 >> 1;int child = n - 1;while (parent >= 0){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){std::swap(a[parent], a[child]);child = parent;parent = child - 1 >> 1;}else{break;}}}

向上调整堆,要找到父亲和孩子,父亲就是元素的总个数-2之后在/2,孩子就是元素总个数-1.

因为是向上调整,父亲节点的下标会慢慢变小,所以循环条件可以设置成parent>=0,有了循环条件,还要比较左右孩子哪个大,然后在让孩子和父亲比较,最后更新父亲下标和孩子下标即可。

删除堆顶元素

删除堆顶元素就是让堆顶元素和堆底元素进行一个交换,然后元素个数-1.交换完成之后,要进行向下调整,向下调整要求左右子树是大根堆或者小根堆,在入堆这一步,我们已经完成了这个操作,所以可以直接调整。

void HeapPop(Heap* ps)
{assert(ps);assert(ps->count);std::swap(ps->val[0], ps->val[ps->count--]);HeapJustDown(ps->val, 0, ps->count);
}

那么向下调整是怎么调的呢?

因为要把堆顶元素调到下面,所以从下标为0的位置开始向下调整。

0的位置就是父亲节点,然后要找到儿子节点child = parent * 2 + 1,然后判断左右孩子哪个大,在判断父亲节点和孩子节点的大小关系,更新下标即可。

void HeapJustDown(HeapDataType* a, int parent, int n)
{int child = parent * 2 + 1;while (child <= n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){std::swap(a[parent], a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

返回堆顶元素

HeapDataType HeapTop(Heap* ps)
{assert(ps);return ps->val[0];
}

返回堆的大小

int HeapSize(Heap* ps)
{assert(ps);return ps->count;
}

判断堆是否为空

bool HeapEmpty(Heap* ps)
{assert(ps);return ps->count == 0;
}

二叉树的链式实现

typedef char TreeDataType;typedef struct BinaryTreeNode
{TreeDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* TreeInit();//初始化BTNode* BinaryTreeCreate();//创建二叉树void BinaryTreeDestory(BTNode* root);//销毁二叉树int BinaryTreeSize(BTNode* root);//二叉树的大小int BinaryTreeLeveKSize(BTNode* root, int k);//第k层有多少个元素BTNode* BinaryTreeFind(BTNode* root, TreeDataType x);//查找数据void PrevOrder(BTNode* root);//前序遍历void InOrder(BTNode* root);//中序遍历void PosOrder(BTNode* root);//后序遍历

二叉树的初始化

BTNode* TreeInit()
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = 0;root->left = NULL;root->right = NULL;return root;
}

二叉树的创建

BTNode* Creat(BTNode* t)
{TreeDataType ch;cin >> ch;if (ch == '-1'){t = NULL;}else{t->val = ch;Creat(t->left);Creat(t->right);}
}
----------------------------------------------------------BTNode* BuyNode(TreeDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BinaryTreeCreate()
{BTNode* newnode1 = BuyNode('A');BTNode* newnode2 = BuyNode('B');BTNode* newnode3 = BuyNode('C');BTNode* newnode4 = BuyNode('D');BTNode* newnode5 = BuyNode('E');BTNode* newnode6 = BuyNode('F');BTNode* newnode7 = BuyNode('G');newnode1->left = newnode2;newnode1->right = newnode3;newnode2->left = newnode4;newnode4->left = newnode7;newnode3->left = newnode5;newnode3->right = newnode6;return newnode1;
}

两种方法创建二叉树,第一种方法是用前序遍历的方法创建二叉树,第二种是自己手动创建一个二叉树。

前序遍历

二叉树的前序遍历是先访问根节点,在访问左子树,在访问右子树,是以递归的形式进行的

void PrevOrder(BTNode* root)
{if (root == NULL){cout << "NULL ";return;}cout << root->val << ' ';PrevOrder(root->left);PrevOrder(root->right);
}

在这里插入图片描述

在这里插入图片描述

中序遍历

二叉树的中序遍历是先访问左子树,在访问根节点,然后右子树,同样是以递归的形式进行的。

void PrevOrder(BTNode* root)
{if (root == NULL){cout << "NULL ";return;}cout << root->val << ' ';PrevOrder(root->left);PrevOrder(root->right);
}

后序遍历

先左子树,在右子树,最后根节点

void InOrder(BTNode* root)
{if (root == NULL){cout << "NULL ";return;}InOrder(root->left);cout << root->val << ' ';InOrder(root->right);
}

二叉树的销毁

二叉树的创建是用的先序遍历,而二叉树的销毁则用的是后续遍历

void BinaryTreeDestory(BTNode* root)
{if (!root){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

二叉树的大小

二叉树的大小很好判断,想一想一个树很深,很多叶子,每个子树上都有一个小领导,小领导来查他管理的地区的叶子,然后层层向上汇报,直到汇报给最大的领导,就可以完成了。

int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}int l = BinaryTreeSize(root->left);int r = BinaryTreeSize(root->right);return l + r + 1;}

二叉树第k层的大小

第k层的大小该怎么判断呢,还是用上面的办法,找到第k层的小领导,让他把第k层的情况汇报给你即可

int BinaryTreeLeveKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}int l = BinaryTreeLeveKSize(root->left, k - 1);int r = BinaryTreeLeveKSize(root->right, k - 1);return l + r;}

二叉树查找数据

查找数据,从左子树找,从右子树找,依次递归即可

BTNode* BinaryTreeFind(BTNode* root, TreeDataType x)
{if (root == NULL){return NULL;}if (root->val == x){return root;}BTNode* l = BinaryTreeFind(root->left, x);if (l){return l;}BTNode* r = BinaryTreeFind(root->right, x);if (r){return r;}return NULL;}

http://www.ppmy.cn/news/47253.html

相关文章

DLRover: 云上自动扩缩容 DeepRec 分布式训练作业

背景 如今&#xff0c;深度学习已广泛应用在搜索、广告、推荐等业务中&#xff0c;这类业务场景普遍有两个特点&#xff1a; 1&#xff09;训练样本量大&#xff0c;需要分布式训练提升训练速度&#xff1b; 2&#xff09;模型稀疏&#xff0c;即模型结构中离散特征计算逻辑占…

【Vue】学习笔记-Vue生命周期

引出生命周期 生命周期 a.又名生命周期回调函数、生命周期函数、生命周期钩子 b.是什么&#xff1a;vue 在关键时刻帮助我们调用一些特殊名称的函数 c.生命周期函数的名字不可更改&#xff0c;但函数的具体内容是程序员根据需求编写的 d.生命周期函数中的this指向是vm或组件实…

SpringBoot 表单提交全局日期格式转换器

参考资料 SpringBoot–LocalDateTime格式转换(前端入参)SpringBoot InitBinder注解绑定请求参数 目录 一. 实现Converter<S, T>接口的方式二. 全局ControllerAdvice InitBinder注解的方式三. RequestMappingHandlerAdapter的方式四. 效果 分析 ⏹当前台的提交数据的Con…

计及氢能的综合能源优化调度研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

AI数据标注工程师这个职业怎么样?

本篇文章主要讲解ai数据标注工程师这个职业的具体情况和相关的职业前景 作者&#xff1a;任聪聪 日期&#xff1a;2023年4月18日 数据是ai的灵魂&#xff0c;自然界中相对应的数据都活多少存在不准确、杂乱、无效等属性&#xff0c;需要人为进行收集、整理、分类和处理。其中ai…

最优化方法Python计算:连续函数的单峰区间计算

我们知道&#xff0c;闭区间上的一元连续函数必在区间上取得最大值和最小值。实践中我们需要能数值地确定含有 f ( x ) f(x) f(x)的唯一最优解 x 0 x_0 x0​的区间 [ a , b ] [a,b] [a,b]。这里介绍寻求连续函数 f ( x ) f(x) f(x)在一点 x ∗ x^* x∗附近单峰区间的包围算法及…

学习小程序基础内容之逻辑交互

我们先来看一下实现的效果。 然后再来分享结构。 结构分为左右3:7 分配&#xff0c; 左侧是类别&#xff0c;右侧是该类别对应的品牌。 后台会在onload的请求把左侧的类别返回来&#xff0c;然后我们通过循环把数据展示出来。然后通过点击事件&#xff0c;把对应的品牌请求回来…

学习同步异步的概念,并了解MQ消息队列

文章目录 一、 同步和异步1.1 同步调用1.2 异步调用 二、MQ1.1 介绍1.2 MQ的优点和使用场景 一、 同步和异步 1.1 同步调用 同步调用是一种程序调用方式&#xff0c;在该调用方式中&#xff0c;调用者发起一个请求&#xff0c;然后一直等待被调用者返回响应结果后再继续执行。…

《Android性能优化》一次失败的启动速度优化

正文 在优化APP启动之前&#xff0c;我们首先需要知道&#xff0c;APP启动时究竟发生了什么&#xff0c;才能有的放矢的优化。 APP的启动过程 APP的启动过程就是指&#xff0c;在手机屏幕上点击某个APP的图标&#xff0c;到APP的首页显示在用户面前的过程。 一般APP的启动过…

【数据分析之道-NumPy(三)】numpy切片与索引

文章目录 专栏导读1、前言2、NumPy数组切片2.1一维数组切片2.2多维数组切片 3、NumPy数组索引3.1一维数组索引3.2多维数组索引 4、NumPy数组高级索引4.1整数数组索引4.2布尔数组索引4.3数组索引 总结 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN Python领域新星创作…

【一】MATLAB基础知识

【一】MATLAB基础知识 1 数值数据类型的分类 整型 无符号整数&#xff1a;无符号8位整数、无符号16位整数、无符号32位整数、 无符号64位整数。 带符号整数&#xff1a;带符号8位整数、带符号16位整数、带符号32位整数、 带符号64位整数。 无符号8位整数数据范围&#xff…

耗时半月,终于把牛客网上的软件测试面试八股文整理成了PDF合集(测试基础+linux+MySQL+接口测试+自动化测试+测试框架+jmeter测试+测试开发)

大家好&#xff0c;最近有不少小伙伴在后台留言&#xff0c;近期的面试越来越难了&#xff0c;要背的八股文越来越多了&#xff0c;考察得越来越细&#xff0c;越来越底层&#xff0c;明摆着就是想让我们徒手造航母嘛&#xff01;实在是太为难我们这些程序员了。 这不&#xf…

软件生存周期

软件生存周期 同任何事物一样&#xff0c;一个软件产品或软件系统也要经历孕育、诞生、成长、成熟、衰亡的许 多阶段&#xff0c;一般称为软件生存周期。把整个软件生存周期划分为若干阶段&#xff0c;每个阶段的任务相对 独立&#xff0c;而且比较简单&#xff0c;便于不同人员…

嵌入式Linux(7):字符设备驱动--申请设备号

文章目录 1、字符设备和杂项设备的区别2、注册字符类设备号的两个办法第一种&#xff1a;静态分配一个设备号第二种&#xff1a;动态分配注销设备号 写代码不带参数测试&#xff08;动态分配&#xff09;&#xff1a;带参数测试&#xff08;静态设置&#xff09;&#xff1a; 建…

C/C++编译器内存优化技术:内存优化关注程序对内存的访问和使用,以提高内存访问速度和减少内存占用。

目录标题 引言缓存优化数据局部性 数据对齐&#xff1a;优化数据结构的布局&#xff0c;以提高内存访问速度。内存池&#xff1a;为对象分配使用预先分配的内存池&#xff0c;以减少动态内存分配和释放的开销。垃圾收集优化&#xff1a;针对使用垃圾收集的语言&#xff0c;优化…

jsp有哪些内置对象?作用分别是什么?

JSP(Java Server Pages)中有以下九个内置对象&#xff1a; 1.request: 表示客户端的HTTP请求。可以使用它来获取客户端提交的表单数据、URL参数、HTTP头等信息。 <!DOCTYPE html> <html> <head><title>获取request对象信息</title> </head&…

运行时内存数据区之方法区(二)

方法区的演进细节 首先明确&#xff1a;只有HotSpot才有永久代。BEA JRockit、IBMJ9等来说&#xff0c;是不存在永久代的概念的。原则上如何实现方法区属于虚拟机实现细节&#xff0c;不受《]Va虚拟机规范》管束&#xff0c;并不要求统一。Hotspot中方法区的变化&#xff1a; …

学系统集成项目管理工程师(中项)系列08b_合同管理(下)

1. 项目变更约定 1.1. 合同生效后&#xff0c;当事人不得因姓名、名称的变更或者法定代表人、负责人、承办人的变动而不履行合同义务 2. 违约责任的承担方式 2.1. 继续履行 2.2. 采取补救措施 2.3. 赔偿损失 2.4. 支付约定违约金或定金 3. 注意事项 3.1. 当事人的法律资…

业余爱好者想入门编程,一定远离那些只会说No的家伙,尤其程序员

视频&#xff1a;https://haokan.baidu.com/v?pdwisenatural&vid3050207991292418741 自媒体上的程序员群体有一个非常有意思的特点&#xff0c;就是特别愿意否定别人&#xff0c;特别喜欢说no&#xff0c;还有一个特点&#xff0c;特别不爱分享一些有用的技术和知识&…

jdk8到jdk17新增新特性介绍

JDK 8: Lambda表达式和函数式接口 Lambda表达式是一个匿名方法&#xff0c;可以用于将行为作为参数传递给方法&#xff0c;或者在函数式接口中直接表示行为。Lambda表达式使用箭头 -> 将参数列表分隔开来&#xff0c;并且主体由花括号包含。以下是一个简单的Lambda表达式示…