详解树的概念和结构

       少年
        天将晨，
     雷声滚滚震忠魂。
        震忠魂：
       倾洒热血，
       造福万民。
     熊甘虎胆尚铄今，
     捷报纷飞传佳讯。
         传佳讯：
        今日少年，
        明年伟人。
           ——《少年的青春》

•知识回顾

大家好啊！我是vince，我们继续进入纯C实现数据结构的坑里来，上一篇文章 vince 详解了栈和队列，将栈和队列做以实现，当然走到这里数据结构中的线性结构目前就告一段落啦~

线性结构结束后，当然就对应着非线性结构，而这里我们首先接触的就是树这种非线性结构。vnce今天先给大家带来树的概念和结构等基础知识，后面再逐一上升。☀️也希望 vince 的总结在方便后面复习的同时也能给大家带来帮助。

当然在大家看这篇文章之前，vince 还是建议大家先复习复习前面的顺序表和链表，毕竟后面树的实现也与他们息息相关。

知识连线时刻（直接点击即可）

  复习回顾
     详解顺序表
   详解双向带头循环链表

• 知识点一：树的相关概念

• 1. 树的定义及结构

•1.1 树的概念

树是一种非线性的数据结构\colorbox{#FFA}{树是一种非线性的数据结构} 树是一种非线性的数据结构​，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树中有一个特殊的结点，称为根结点，根节点没有前驱结点。

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

•1.2 树形结构

树形结构有以下几点需要注意：
1、树形结构中，子树之间不能有交集，否则就不是树形结构；
2、除了根节点外，每个结点有且仅有一个双亲节点；
3、一棵N个节点的树有N-1条边。
严格来说，树不能有回路。

•1.3 树的相关术语

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的度为6。
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点。
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点。
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点—亲兄弟。
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4，堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点。
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先；自己也可以认为是自己的祖先和子孙。如：A是A的祖先亦是子孙
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
森林：由m（m>0）棵互不相交的树的集合称为森林；并查集。

• 2. 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法。

树的表示法一：指定树的度
代码展示：

//假定指定树的度#define N 5struct TreeNode{int data;struct TreeNode* subs[N];//指针数组};

文字分析：
这里是首先直接指定树的度。但是并不是每一个结点的度都是一样的，所以这种指定会浪费大量空间。

树的表示法二：不指定树的度
代码展示：

//不知道树的度#define N 5struct TreeNode{int data;SeqList sl;// 顺序表// SLDataType——>struct TreeNode*};

文字分析：
这里不知道树的度，因此这里就结合顺序表，相当于每一个结点里面都有一个顺序表存在，顺序表中数据类型为struct TreeNode*类型。

树的表示法三：孩子兄弟表示法
存储树最优秀的结构：左孩子右兄弟——孩子兄弟表示法
代码展示：

typedef int DataType;struct Node{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域}

结构图解分析：
存储图解分析：

• 3. 树的应用

树的应用广泛，在不同的软件系统中树的基本操作集不尽相同。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可导致一个树结构。
如图例：（系统的目录用树结构实现）

• 知识点二：二叉树的相关概念

• 1. 二叉树的定义及结构

•1.1二叉树的概念

二叉树是一棵树，是结点的一个有限集合，该集合为空或者一个根节点和两棵别称为左子树和右子树的二叉树组成。

•1.2 二叉树的结构

如图二叉树结构：

由图可知：
二叉树不存在度大于2的节点；
二叉树中根节点的孩子节点有左右之分，不能颠倒次序，因此二叉树是有序树。

由此可知对于任意二叉树均是由以下几种情况组合而成：

• 2. 特殊二叉树

•2.1满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1 （是一个等比数列求和） ，则它就是满二叉树。
结构图解分析：

•2.1完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 满二叉树是一种特殊的完全二叉树。
结构图解分析：

• 3. 二叉树的性质

1、 若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2^i-1个节点。

2、若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h– 1。

3、对任何一棵二叉树, 如果度为0的其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n 0n_{0} n0​ ＝ n 2n_{2} n2​ ＋1。

4、若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log⁡2\log_{2} log2​ ⁽ⁿ⁺¹⁾。

5、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
1.若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点；
2.若2i+1=n，则无左孩子；
3.若2i+2=n，则无右孩子。

性质五图解分析：

• 4. 二叉树相关习题

例题一：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）A 不存在这样的二叉树B 200C 198D 199

解析：
利用 n 0n_{0} n0​ ＝ n 2n_{2} n2​ ＋1。该题中叶子节点 n 0n_{0} n0​个数为199 + 1 = 200。故选B。

例题二：

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）A nB n+1C n-1D n/2

解析：
由题意知： n 0n_{0} n0​ + n 1n_{1} n1​+ n 2n_{2} n2​ = 2n，利用 n 0n_{0} n0​ ＝ n 2n_{2} n2​ ＋1； n 1n_{1} n1​ = 1；联立可得：叶子节点 n 0n_{0} n0​个数为n。

例题三：

3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（B）A 11B 10C 8D 12

解析：
满二叉树是特殊的完全二叉树。最多节点数：2^h– 1；最少节点数：2^h-1。因此，将其放入到该题中可得：这棵树的高度h为10。

例题四：

5.一个具有767个节点的完全二叉树，其叶子节点个数为（B）A 383B 384C 385D 386

解析：
由题意知： n 0n_{0} n0​ + n 1n_{1} n1​+ n 2n_{2} n2​ = 767；利用 n 0n_{0} n0​ ＝ n 2n_{2} n2​ ＋1； n 1n_{1} n1​ = 0；联立可得：叶子节点 n 0n_{0} n0​个数为384。

•vince 结语

树和二叉树的相关概念和结构的介绍和学习到这里就结束啦~但是数据结构的学习之路远没有结束哈！这是非线性结构的开端，后面还有大力输出学习非线性结构。但是在这里，希望大家能够将前面的线性结构回顾复习，使整个纯C数据结构学习是连贯的，这样更加利于我们的学习和理解以及继续拓展。

如果各位大佬们觉得有一定帮助的话，就来个赞和收藏吧，如有不足之处也请批评指正。

代码不负有心人，98加满，向前冲啊

以上代码均可运行，所用编译环境为 vs2019 ,运行时注意加上编译头文件#define _CRT_SECURE_NO_WARNINGS 1