前言

在介绍完数据结构的顺序表之后，接下来着手开始树的介绍树的相关内容；而因为篇幅，本次只会牵扯到树的基本概念以及二叉树的相关介绍，代码则基本不涉及！

1.树💬

1.1树的概念💬

树是一种非线性的数据结构，它是由n个(n>=0)有限结点组成的一个具有层次关系的集合。

如图所示：

这就是一个树，因为倒着看就如同树一般，因此形如这种数据结构就被称为树！

• 树中存在一个根节点，就是图中的A，它没有前驱节点
• 除根节点外，其他节点会形成一系列子树，每棵子树有且只有一个前驱，存在多个或0个后继

因此，如上图所示，A为根节点，无前驱，绿色、蓝色、紫色为3棵子树，当然子树的划分并不只有这些，我是以A为根节点进行划分的，向下还是可以划分其他小规模的子树的。

而树的结构中是不能存在交集的，否则就不是树形结构

这种结构是错误的！

需要注意的是：

1. 子树是不相交的
2. 除了根节点之外，每个节点有且只有一个父节点
3. 一个N个结点的树有N-1条边

1.2树的结构💬

• 根节点：无前驱的结点
• 节点的度：一个节点含有子树的个数；例如，A的节点的度是6；
• 叶节点：度为0的结点或者可以说成无子树的结点又或是0个后继的结点；如图中的H、I 、Q、K、L、M、N；
• 非终端结点或分支节点：度不为0的结点；
• 双亲结点：如果一个结点含有子节点，那么它就是这个子节点的双亲节点或者可以说成父节点；如图中的A是B的父节点；
• 兄弟结点：拥有相同父节点的结点被称为兄弟结点；
• 树的度：一棵树中，最大结点的度就是树的度；上图所示树的度就是6；
• 结点的层次：根结点的层次为1，以此类推；
• 树的高度（深度）：结点的最大层次；图中，该树的深度就是4；
• 堂兄弟结点：父节点在同一层，如H 、I；
• 结点的祖先：也就是整个树的根节点；
• 子孙：以某结点为根的子树中任一节点都被称为该节点的子孙。

以上就是数结构中各个位置的含义，而黄色标记的就是较为重要的，在之后的编程中或许会出现。

1.3树的表示💬

1️⃣

typedef struct TreeNode
{
   struct TreeNode* leftchild;
   struct TreeNode* rightchild;
   DataType data;
}TreeNode;
1
2
3
4
5
6

其结构可以这样表示出来：

与链表很类似，利用结构体指针去指向下一个结构体或者说是下一个树的结点，当然这只是一种表示方法；

2️⃣

typedef struct TreeNode
{
   struct TreeNode* child;
   struct TreeNode* brother;
   DataType data;
}TreeNode;
1
2
3
4
5
6

这也是一种表示方法，当然树的表示方法有很多，我认为第一种是最好的，便于理解，且操作简单，在下面的操作中也大都会使用第一种方式进行编码；

2.二叉树💬

在有了前面内容的铺垫，理解二叉树就更为简单。

大自然给出我们的二叉树：

2.1二叉树的概念💬

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

• 要么为空

• 要么由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

概念总是看的人想吐，接下来看一个实际结构就可以很快了解到二叉树了：

从上图可以看出：

• 二叉树并不存在度大于2的结点，也就是只存在度为2、1、0的结点；
• 二叉树的子树有左右之分，次序是不可以颠倒的，因此二叉树为有序树。

2.2两种特殊的二叉树💬

2.2.1满二叉树💬

一个二叉树，每一层的结点数都达到最大值，则这个二叉树是满二叉树。

每一层都被结点填满，没有空隙，像这样的树就被称为满二叉树；满二叉树的总结点数为(2^i-1)，这个会在下面进行推导。

2.2.2完全二叉树💬

完全二叉树：完全二叉树是由满二叉树引申出来的一种效率很高的数据结构；而完全二叉树其前k-1层是满的，第k层从左到右连续，当第k层结点满时，此时完全二叉树也就是一个满二叉树。

其实在接下来介绍的结构堆，就是一棵完全二叉树，会利用完全二叉树的各种性质从而实现堆排序以及解决TopK问题。

2.3二叉树的性质💬

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

• 对于任意一棵二叉树，度为0的结点N，度为2的结点M，则有N=M+1；
• 若规定根节点的二叉树的层数为1，则具有n个结点的满二叉树的深度h=log₂(n+1)

这一性质对应于性质2，最多结点也就意味着是一个满二叉树，所以对其进行数学变换就可以得到满二叉树的高度！

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

（1）若左孩子的编号为i，则其父节点的下标为2i+1;
（2）若右孩子的编号为i，则其父节点的下标为2i+2；
（3）（孩子结点下标-1）/ 2 = 父节点下标

上述三点很重要！！！在堆排序中会进行应用！！！

Ending

本次博客就结束了，关于二叉树的基础内容就这么多，其较为重要的我大都也进行了标识，后续会进行二叉树的编写以及堆的编写。

就这样吧🙋‍♂️🙋‍♂️🙋‍♂️