数据结构|二叉树初阶1、数据结构|算法

目录
1、树概念及结构：
1.1、树的概念：
1.2 、树的相关概念：
1.3 、树的表示：
1.4 、树在实际中的运用（表示文件系统的目录树结构）：
2、二叉树概念及结构：
2.1、概念：
2.2、现实中的二叉树：
2.3、特殊的二叉树：
2.4、二叉树的性质：
2.5、例题1：
1、树概念及结构： 1.1、树的概念：树是一种在逻辑上为非线性的数据结构，它是由 n（n>=0）个有限结点，每个结点中都存储一个data数据，组成一个具有层次关系的集合，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的、 1、在一个非空树中，有且只有一个特殊的结点，称为根结点，根节点没有前驱结点、 2、除根节点外，若还存在其他的结点，则其余结点被分成 M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树，每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，若除根结点外不存在其他的结点，则子树的个数就是0 个，因此，树是递归定义的、
文章图片
每颗树都可以分解成根和n颗子树，其中，n>=0、
注意：树形结构中，子树之间不能有交集，否则就不是树形结构、
文章图片

各个子树之间是不能相交的，即是不可以构成回路的，否则在递归时就会造成死循环，如果带回路(带环)的话，如上图，就不叫做树了，而是叫
做图，图是另外一种数据结构、
1.2 、树的相关概念：
文章图片

树和二叉树不是一个概念，二叉树是一种特殊的树，子树也是树、节点的度：一个节点含有的子树的个数称为该节点的度；如上图： A的为6、叶节点或终端节点：度为0的节点称为叶节点，如上图： B、C、H、I...等节点为叶节点、非终端节点或分支节点：度不为0的节点，如上图： D、E、F、G...等节点为分支节点、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图： A是B的父节点、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图： B是A的孩子节点、兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图： B、C是兄弟节点、树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6、节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；也可以从0开始起，但是一般都从1开始算起，若从1开始计算的话，上图中，树的高度或深度则为4，若从0开始计算的话，树的高度或深度则为3，但是一般都从1开始计算，比较合理，比如，若一棵树中只有一个结点的话，若从1开始计算，则该树的深度或高度则为1，若从0开始计算，则该树的深度或者高度则为0，显然后者比较奇怪，或者再如，有一颗空树，即，一个结点都没有的树，若从1开始计算的话，该树的深度或者高度则为0，若从0开始计算的话，则该树的深度或者高度则为-1，所以后者不太容易理解，所以一般都从1开始计算、树的高度或深度：树中节点的最大层次；如上图：树的高度为4、堂兄弟节点：双亲结点在同一层的节点互为堂兄弟；如上图： H、I互为堂兄弟节点、一般所说的兄弟结点默认指的是亲兄弟结点、节点的祖先：从根到该节点所经分支上的所有节点，包括该结点本身（除非题目明确说明不包括该节点本身）；如上图： A是所有节点的祖先、再如结点Q的祖先有A，E，J，Q、对于结点P和Q而言，他们的祖先分别是：A，E，J，P，和A，E，J，Q，其中结点A，E，J，是节点P和Q的公共祖先，对于P和Q而言，J是他两个的最近公共祖先，再如，F的祖先有A，F，而K的祖先有A，F，K，对于F和K的公共祖先有A，F，所以， F和K的最近公共祖先就是F、子孙：以某节点为根的子树中任一节点都称为该节点的子孙，包括该节点本身，（除非题目明确说明不包括该节点本身），如上图：所有节点都是A的子孙，也可认为结点A也是结点A的子孙、森林：由m（m>0）棵互不相交的树的集合称为森林，一棵树也可以叫做森林，这个概念在并查集中会用到、1.3 、树的表示：树结构相对线性表示就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等，我们这里就简单的了解其中最常用的孩子兄弟表示法、树的表示比较麻烦，是因为某一个节点的孩子的个数，即某一个节点的度，是不确定的、
文章图片

#define _CRT_SECURE_NO_WARNINGS 1 #include //树要使用链式结构来实现、方法一: 定义结构体,即定义节点的结构、不清楚某一个节点的孩子的个数,即不清楚某一个节点的度、假设指定了树的度,而树的度即指一棵树中,最大的节点的度,也就是说指定了树中每一个节点最多有几个孩子,假设树的度为5,则意味着在该整个树中, 每一个节点的孩子最多为5个,即每一个节点的度最多为5、如果指定了树的度等于5,则在该树中,至少有一个节点有5个孩子,即至少有一个节点的度为5、 //#define N 5 //typedef int Datatype; //struct TreeNode //{ // Datatype data; // //定义指向某一个节点孩子的指针变量,即定义指向某一个节点的子节点的指针变量、 // struct TreeNode* subs[N]; //指针数组,用来存放指向某一个节点孩子的指针变量,即用来存放指向某一个节点的子节点的指针变量、 // //这样定义的话,会存在一定的缺陷,是因为并不是每个节点都有5个孩子,若部分节点的孩子不够5个的话,而每个节点中都开辟5个空间来存储指向该节点孩子的指针变量,就会造成空间浪费、 //方法二: 当未指定树的度时,即未规定所有的节点最多有几个孩子、 //typedef int Datatype; //struct TreeNode //{ //Datatype data; // //用顺序表存储指向该节点孩子的指针变量、 // //SeqList _sl; //在每个节点内部都定义一个顺序表,而顺序表中每个元素的类型都是struct TreeNode* 类型,即SLDatetype -> struct TreeNode*; ////由于访问树时是从根节点依次往下访问的,所以当某一些节点未访问到时,是不清楚这些节点有几个孩子的,即不知道这些节点的度是多少，所以无法直接这些节点开辟对应的度的空间 ////只有先动态开辟某几个空间,当访问到这些节点时,若空间不够再进行增容、 // //然后再对每个节点中的顺序表进行动态开辟某个个数的内存空间,当空间不够使用时再增容空间即可,但是这种方法的实现比较麻烦,在C++中可以更加简单的实现这种方法,如下： // //vector本质上就是顺序表、 // //vector subs; C++,在此不对该方法进行研究,等到C++时再做研究、 //}; //方法三: //孩子兄弟表示法、 //存储树最优秀的结构,没有之一、 typedef int DataType; struct TreeNode { // 第一个孩子结点,指向该节点的第一个孩子、 struct TreeNode* firstChild1; // 指向该节点的下一个兄弟结点、 struct TreeNode* pNextBrother ; // 结点中的数据域、 DataTypedata; }; int main() { return 0; }

1.4 、树在实际中的运用（表示文件系统的目录树结构）：

文章图片

2、二叉树概念及结构： 2.1、概念：二叉树（Binary tree）是指计算机科学中每个结点最多有两个子树的树结构，其子树被称作“左子树”（left subtree）和“右子树”（rightsubtree），
常被用于实现二叉查找树和二叉堆、
二叉树的度小于等于2，即二叉树的度大于等于0，小于等于2，则二叉树的度可能为：0，1，2，在树结构中，一个元素也称作一个结点，当节点
集合为空时，即树中不存在节点时，即称其为空树，空树也属于树，对于空树而言，默认其度为0，则属于二叉树，即度为0的二叉树，通常称该
二叉树为空二叉树、
一、
对于度为2的树，不是说该树中的每一个节点的度都为2，而是该树中，每一个节点的度最大为2，并且在该树中至少存在一个节点的度等于2，即
在该树中，有的节点的度可能是0，也有的节点的度是1，有的节点的度是2，但不可能存在某一个节点的度是3或者以上的情况，由于树的度是指
【数据结构|二叉树初阶1、】在一棵树中，最大的节点的度，而已知树的度为2，即代表着在该树中，至少存在一个节点的度等于2，由于树的度为2，所以其属于二叉树，即
度为2的二叉树、
二、
对于度为1的树，不是说该树中的每一个节点的度都为1，而是该树中，每一个节点的度最大为1，并且在该树中至少存在一个节点的度等于1，即
在该树中，有的节点的度可能是0，也有的节点的度是1，但不可能存在某一个节点的度是2或者以上的情况，由于树的度是指在一棵树中，最大
的节点的度，而已知树的度为1，即代表着在该树中，至少存在一个节点的度等于1，由于树的度为1，所以其属于二叉树，即度为1的二叉树、
三、
对于度为0的树，则有两种情况：
1、该树结构中只有根节点一个节点，若除根节点外还存在其他节点的话，则根节点的度就大于等于1，所以树的度就不可能为0，所以该树的度
为0，也属于二叉树，即度为0的二叉树，通常叫做只有一个根结点的二叉树、
2、当树结构中不存在节点时，即为空树时，空树也属于树，默认树的度为0，所以该树的度为0，也属于二叉树，即度为0的二叉树，通常叫做空
二叉树、

一棵二叉树是节点的一个有限集合，该集合：1、或者为空，即在一个树中，若不存在节点，就称其为空树，空树也属于树，默认空树的度为0 ，则空树也属于二叉树，即度为0的二叉树，通常称其为空二叉树、 2、或者由一个根节点加上两棵分别称为根节点的左子树和根节点的右子树组成，而根节点的左右子树也属于二叉树，根节点的左子树的度为1，则属于二叉树，即为度为1的二叉树，根节点的右子树的度为2，则属于二叉树，即度为2的二叉树、

文章图片
从上图可以看出：1、二叉树不存在度大于2的结点、 2、二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树、注意：对于任意的二叉树都是由以下几种情况复合而成的：二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

文章图片

当树的结构中，不存在节点时，则称其为空树，空树也属于树，默认空树的度为0，则属于二叉树，即度为0的二叉树，通常称其为空二叉树，当
树的结构中，只存在一个根节点时，也称其为树，则该树的度为0，也属于二叉树，即度为0的二叉树，通常称其为只有一个根节点的二叉树，当
树结构中只有左子树时，则右子树为空，当只有右子树时，则左子树为空，上图这两种情况中的树的度都为1，属于二叉树，即度为1的二叉树，
当左右子树均存在时，即上图树的度为2，也属于二叉树，即度为2的二叉树，称其为完全二叉树、

只需要知道度为0和1的二叉树也属于二叉树即可，通常情况下所谓的二叉树或者是未明确表明度为多少的二叉树，均默认其度为2，即默认其是
度为2的二叉树、
2.2、现实中的二叉树：

文章图片

2.3、特殊的二叉树：只需要知道度为0和1的二叉树也属于二叉树即可，通常情况下所谓的二叉树或者是未明确表明度为多少的二叉树，均默认其度为2，即默认
其是度为2的二叉树、
1、满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数为K（根结点为第一层），且结点总数是 2^K - 1 ，则它就是满二叉树，即除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树、 2、完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，满二叉树是完全二叉树的一种特例，对于深度为K (根结点为第一层) 的，有 n个结点的二叉树，当且仅当其每一个结点都与深度为K (根结点为第一层) 的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树，要注意的是满二叉树是一种特殊的完全二叉树，即前K-1层都是满的，最后一层不满，但是最后一层从左往右是连续的、

文章图片
完全二叉树和满二叉树最大的意义之一是用来表示堆，堆是一种数据结构，和进程地址空间，即内存中的堆区，名字是重复的，但是意义是不一样的，此处所指的堆，是一种数据结构、堆排序和快排是一个档次的，但是速度略低于快排、堆可以通过满二叉树来实现，也可通过完全二叉树来实现，要记住，满二叉树是完全二叉树的一种特例、堆是具体怎么通过满二叉树或完全二叉树进行实现的呢？

文章图片

2.4、二叉树的性质： 1、若规定根节点的层数为1 ，则一棵非空二叉树的第k层上最多有 2^(k-1)个结点、 2、若规定根节点的层数为1 ，则非空二叉树中，深度为h的二叉树的最多结点数是2^h - 1、 3、对任何一棵非空二叉树，如果度为0的叶结点个数为N0，度为2的分支结点个数为N2，则有：N0=N2+1，即度为0的节点的个数比度为2的节
点的个数永远多1，只要增加一个度为2的节点，则就会增加一个度为0的节点，从而导致度为0的节点的个数永远保持比度为2的节点的个数多1、
4、若规定根节点的层数为1 ，具有 n个结点的满二叉树的深度， h= log以2为底，(n+1)的对数、 5. 对于具有 n个结点的完全二叉树，如果按照从上至下从左至右的顺序表顺序对所有节点从0开始编号，则对于序号为 i 的结点有：(1)、若 i>0，则 i 位置节点的双亲序号为：(i-1)/2，若 i=0，则 i 为根节点编号，即无双亲节点、 (2)、若2i+1=n，否则无左孩子、 (3)、若2i+2=n，否则无右孩子、
2.5、例题1：数据结构|二叉树初阶1、