【数据结构】--- 深入剖析二叉树（上篇）--- 初识树和二叉树

Welcome to 9ilk's Code World

(๑•́ ₃ •̀๑) 个人主页: 9ilk

(๑•́ ₃ •̀๑) 文章专栏：数据结构之旅

🏠 初识树

📒 树的概念

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

正如现实生活中的树一样，我们的树数据结构也有一个根结点，根节点没有前驱结点
树是递归定义的，根节点下有多个分支也就是多个子树，多个子树下又有多个子树
对于一颗树可以拆解成根和n颗子树，同样，子树也可以按照相同方式拆分，直到不可拆分

⚠️ 1.子树不能有交集

2.除了根结点外，每个结点只能有一个父亲

3.一颗N个结点的树有N-1条边

以下的都是子树有交集的，不能叫做树

4.树中不能有环，有环就是图了

为了方便我们深入了解树，我们来普及一些树中的专有名词 ~

📒 树中的专有名词

孩子结点或子结点：某一个结点含有的子树的根结点，如上图中的B,C,D..都是A的子结点
双亲结点：若一个节点含有子节点，则这个节点称为其子节点的父节点，，如上图中的A都是B,C,D..的双亲结点
兄弟结点：顾名思义，就是有同个双亲结点的子节点，如上图的D,E是兄弟，I,J是兄弟。
堂兄弟结点：双亲在同一层的节点互为堂兄弟，如上图的I和K是堂兄弟，注意堂兄弟结点的双亲结点不同
结点的祖先：从根到该节点所经分支上的所有节点，如上图A是所有结点祖先，E是IJQP祖先。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙.如上图所有结点都是A的子孙，IJQP是E的子孙。
结点的度：一个节含有的子树的个数称为该节点的度。
叶子结点或终端结点：度为0的结点，也就是没有子树，如上图的P,Q。
分支结点或非终端结点：度大于0的结点，如上图的D,H,F...
树的度：认为最大的节点的度称为树的度。
结点的层次：从根开始定义起，根为第1层（以根为第一层方便区分空树和非空树），根的子节点为第2层，如上图的E层次是2
树的高度或深度：树中节点的最大层次，如上图树的深度是4
森林：由m（m>0）棵互不相交的树的集合称为森林。（互不相交不仅指没有交集，还有归属关系）

📒 树的表示方法

线性表表示

struct TreeNode
{
    int val;
    struct TreeNode** subA;
    int size;
    int capacity;
}

双亲表示法孩子表示法

这两种较为复杂，博主就不演示了，本人推荐看这位博主文章树的表示

左孩子右兄弟

struct TreeNode
{
   struct TreeNode* leftchild;
   struct TreeNode* rightbrother;
   int data;
}

🏠 初识二叉树

📒 何为二叉树

一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

⚠️ 1.二叉树的结点的度一定是大与等于0且小于等于2的

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
3.二叉树可以是空树或只有根结点

📒 完全二叉树 vs 满二叉树

满二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k - 1 ，则它就是满二叉树

完全二叉树

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

⚠️

1.满二叉树是特殊的完全二叉树

2.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

3.完全二叉树要求最后一层结点从左到右连续

📒 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1 .

推导过程如下图

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

推导：设树的高度为h，则n = 2^(h) - 1; 因此n+1 = 2^h ---> h = log(n+1);

对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1.

推导：假设该二叉树有n个结点，则该二叉树有n-1条边。由于结点个数n=不同度结点个数之和，即n = n0 + n2 + n1;又由于度为2的结点有两条边，度为1的结点有1条边，故可以得到等式关系 n0 + n2 + n1 - 1 = n2 x 2 + n1 x 1;整理可得n0 = n2 + 1.

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

若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

📒 二叉树的存储结构

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

由图中我们可以得知，非完全二叉树采用顺序存储会造成空间的浪费。

结论：数组存储只适合完全二叉树和满二叉树

那有什么存储结构表示非完全二叉树而不造成空间的浪费呢？

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。

二叉链

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
  struct BinTreeNode* _pLeft; // 指向当前节点左孩子
  struct BinTreeNode* _pRight; // 指向当前节点右孩子
  BTDataType _data; // 当前节点值域
}

三叉链

// 三叉链
typedef int BTDataType;
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}