二叉树详解一万字(基础版)看着一篇就够了(上))

简介: 树的结构是一种非线性的数据结构,它是由n(n>=0)个节点组成的一个有层次的关系集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说他是根朝上,而叶朝下。


树的概念与结构:


1.1树的结构


树的结构是一种非线性的数据结构,它是由n(n>=0)个节点组成的一个有层次的关系集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说他是根朝上,而叶朝下。

3c69c6f1ee5a46478baacf1c873de24e.png


   有一个特殊的结点,称为根结点,根节点没有前驱结点


   除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继


   所以树是被递归定义的(一个问题可以分成几个子问题并且具有相同的解决办法)


15c91f50241a4fb2a1176ce1762e3309.png


(就像这样将根节点去掉,它就是多个树,它只有一个前驱,但是可以有多个后继)


注意:树的结构中,子树之间不能有交集,否则就不是树形结构


f4730e2842cc41a9bf25b93caac04766.png


1.2树的相关概念


8c992c93755a4a2e800fb6d47d0bed35.png


节点的度:一个节点含有的子树的个数称为这个节点的度;比如上图中A的度为6,D的度为1;


叶节点或者终端节点:度为0的节点叫做叶节点,就像上图中的BHIPQ...,就是每个枝端最后的一个节点

非终端节点或者分支节点:度不为0的节点,如上图中的DEFGJ

双亲节点或父节点:若一个节点含有子节点,那么这个节点就称为其子节点的父节点,如上图:A就是BCDEFG的父节点

D就是H的父节点

孩子节点或者子节点:一个节点含有子树的根节点叫该节点的子节点:如上图:BCD就是A的子节点

兄弟节点:具有相同父节点的节点就互相为兄弟节点;就像上图中:BCD是,IJ也是。

树的度:一颗树中,最大节点的度叫做树的度;如上图树的度是。

节点的层次:从根开始定义,根为第一层,根的节点是第二层......

树的高度或深度:树中节点的最大层次,如上图树的深度为4、

堂兄弟节点:双亲在同一层的节点互为堂兄弟;就像上图中的HI\HK;

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

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

森林:由 m(M>0)棵不相交的树的集合叫做森林。


1.3树的表示


树的表示法有:


1.孩子表示法:


就是每个节点保存值域与孩子的指针域。注意:有几个孩子就需要几个指针域,节点中的字段个数:要比树的度大一(要保存值域)


就像A就需要4个字段,三个孩子的指针域和一个值域

a22d83bb8e524cc08fa253102f680b05.png



优势:找某个节点的孩子很方便


缺点:找双亲不是很方便


2.双亲表示法:


每个节点既要保存值域,也要保存双亲的位置,也就是每个节点需要两个字段


优势:找某个节点的双亲时比较方便

缺点:找某个节点的孩子不是很方便


3.孩子双亲表示法


孩子表示法+双亲表示法结合起来

每个节点既要保存值域,还要保存其双亲与孩子的地址


4.孩子兄弟表示法


每个节点既要保存第一个孩子的节点还要保存下一个兄弟的节点与节点中的数据域
typedef int DataType;
struct Node
{ struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};


91ee39d947bb4f078c36972df7ea7ba2.png

6f820b2d47a74827b92e8c006837fefe.png


二叉树的概念与结构


2.1概念


一棵二叉树是结点的一个有限集合,该集合:

1. 空

2. 由一个根节点以及加上两棵别称为左子树和右子树的二叉树组成

14fddc2d1ce94e4ba5a04057072c8f80.png


一个节点最多只有两个孩子,可以一个都没,或者只有一个节点

二叉树的左右子树也是一个二叉树,定义也是递归的,二叉树有左右之分的,二叉树是有序树。

注意:对于任意的二叉树都是由以下几种情况复合而成的:

bc737d0156444c7ca6beea2accff0dee.png


满二叉树


每层的节点个数都是2^(i-1)


完全二叉树


假设二叉树的高度为h,前h-1层达到了最大值,第h层的节点是从左到右依次排列的


假设二叉树中有n个节点,如果该二叉树中前N个节点与高度相同的完全二叉树的前n个节点相同,那么就叫二叉树为完全二叉树


二叉树的性质


1.若规定根节点的层数为1,则一颗非空二叉树的第i层上最多有2^(i-1)个节点


2.若规定根节点的层数为1,那么深度为h的二叉树的最大节点个数为2^-1(等比数列的前n项和)

3.对任意的一颗二叉树,如果度为0,其叶节点的个数为n0,度为二的分 支节点个数为n2,则有n0 = n2+1;通俗的说就是度为0的节点比度为2的节点个数多1个


a8888c29b6b44632b97011df126ef987.png

1df92c6ac801403fb0a62be458a93a77.png




n0 = 3;


n2 = 2;

n0 = n2+1;

这个方法是用总边数证明的

7490bf41af7b44d4b309b06536db497c.png

4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= log2^(n+1)(ps: 是log以2

为底,n+1为对数)

完全二叉树计算出来可能是小数,需要向上取整,就是大于其最近的一个整数

5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对 于序号为i的结点有:

1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

2. 若2i+1,左孩子序号:2i+1,2i+1>=n否则无左孩子

3. 若2i+2,右孩子序号:2i+2,2i+2>=n否则无右孩子

好处:二叉树可以用数组来进行,完全二叉树用数组进行储存空间浪费较少


二叉树的存储结构


二叉树一般有两种存储结构,一种是顺序结构一种是链式结构,顺序结构更适合完全二叉树,否则会有大量的空间浪费,二叉树在物理上是一个数组,在逻辑上是一颗二叉树。


对于顺序结构:


b020479eb9184631b7ac75917726c9d5.png


对于链式结构来说:


     使用链表来构建一颗树,在来链表的节点中保存数据域和左右指针域。链式结构又分为二叉链和三叉链。

4a4f219569be4db78577e3769f68faef.png

cbf42067911e414ca0bbf170a3982c1f.png


二叉树的顺序结构:


普通二叉树不适合使用数组来储存,会造成大量的空间浪费,完全二叉树适合顺序结构进行储存。现实中我们通常使用堆来进行储存(注意,这里的堆和操作系统中的虚拟空间不是一个东西,一个是数据结构,一个是操作系统中管理内存的一段区域分段)


堆的概念与结构:


说明白点,堆就是从小到大或者从大到小的完全二叉树


所以,堆的性质就是,堆中的某个节点总是不大于或者不小于它的父节点,堆总是一个完全二叉树


小堆也叫小根堆,大堆也叫大根堆

28d10eb93bb94cf89dd29ad781803c6c.png

目录
相关文章
|
搜索推荐
二分查找(非要5个字)
二分查找(非要5个字)
44 0
LeetCode题解-让所有学生保持开心的分组方法数
LeetCode题解-让所有学生保持开心的分组方法数
|
7月前
|
网络协议 网络安全 网络虚拟化
网工大题题型总结(3)------2018到2022大题类型总结
网工大题题型总结(3)------2018到2022大题类型总结
34 2
|
7月前
|
C++
[蓝桥杯 2023 省 A] 填空问题--幸运数
[蓝桥杯 2023 省 A] 填空问题--幸运数
83 0
L1-058 6翻了 (15 分)(while的巧妙使用)
L1-058 6翻了 (15 分)(while的巧妙使用)
70 0
|
算法 C++
【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念
【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念
115 0
二叉树详解一万字(基础版)看着一篇就够了(下)
对于堆的调整相当于是对数组的一种调整,将数组的首地址传进来,要调整的数组的长度,相当于是退出的循环条件,向下传给进来parent(root),向上传给child(size-1),然后再用一个表示另外一个。将参数传进来之后进行比较,先比较两个孩子,找出小的那个,然后交换较小孩子和双亲节点,在比较左右孩子的时候要保证右孩子也存在才可以进行比较,就是child+1<size,原因就是这里是堆,是完全二叉树
64 0
编号(太晚了,先发一题,可能以后题都单发了,方便分类整理)
编号(太晚了,先发一题,可能以后题都单发了,方便分类整理)
65 0
|
算法 BI C++
蓝桥杯练习题十四 - 次数差(c++)
蓝桥杯练习题十四 - 次数差(c++)
103 0
随机练习题:浅浅固定思路
随机练习题:浅浅固定思路
271 0