“人生如梦，一樽还酹江月”
猛戳订阅🍁🍁 👉 纯C详解数据结构专栏 👈 🍁🍁
这里是目录
普通树的概念
树由 根 和 n 棵子树组成，树是非线性数据结构。树是递归定义的，这点很重要。
树的特点
1.树的子树是不相交的。
2.除了根节点外，每个结点有且仅有一个父节点。
3.一棵N个节点的树有N-1条边。
树的术语
以下加粗的为重点
树的度：一棵树中，最大的节点的度称为树的度
节点的层次：从根开始定义起，根为第一层，根的子节点为第二层。
数的高度或深度：树中节点的最大层次。
节点的度：一个节点含有的子树的个数成为该节点的度。
叶节点或终端节点：度为0的节点称为叶节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
兄弟节点：具有相同父节点点节点称为兄弟节点。亲兄弟才是兄弟节点。
堂兄弟节点：双亲在同一层的节点护卫堂兄弟。
节点的祖先：从根到该节点所经分支上的所有节点。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：有m（m > 0）棵互不相交的数的集合称为森林。
普通树的表示
来看看先辈们创造的优秀智慧。
存储树最优秀的结构：孩子兄弟表示法。
即：一个节点有多少个孩子都无所谓。父亲指向第一个孩子，剩下的孩子，用孩子的兄弟指针连接起来。
typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };
二叉树概念
二叉树是我们要研究的重点。
二叉树：一棵二叉树是结点的一个有限集合。
该集合有两种情况。
1.为空树
2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成
二叉树的特点：
1.二叉树的度最大为2，即最多只有两颗子树。
2.二叉树的子树有有左右之分，次序不能颠倒，因此二叉树是有序树。
注意：因为二叉树是递归定义的。
对于任意的二叉树都是由以下几种情况复合而成的
二叉树的性质
二叉树的性质是建立在两种特殊的二叉树上研究的。
1.满二叉树：每一层的结点数都达到了最大值。
2.完全二叉树：前k-1层都是满的，最后一层不满，但是最后一层从左往右是连续的。
性质1：若规定根节点的层数为1，则一棵非空二叉树的第h层上最多有 2h-1个结点.
性质2：若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2h-1 .
解释：根据等比数列前n项的和来看，n层相加得到2h-1 。
性质3：对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1
性质4：若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(n+1).
解释：这是对2h-1 = n公式的转换。
性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于下标为i的结点有以下解释：
1.i位置节点的双亲下标：(i-1)/2
2.左孩子下标：2i+1
3.右孩子下标：2i+2
如图。
数组二叉树
上一章的堆，已经叙述。
- 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
链式二叉树
学链式二叉树的什么内容？
普通二叉树增删查改没有价值，如果是为了单纯存放数据，不如用线性表。我们现在学习二叉树，1.是为了更好的控制他的结构，为后续学习复杂的搜索二叉树打基础
包括平衡搜索二叉树：AVL数、红黑树。学习搜索二叉树的意义在于可以用于搜索.
2.很多二叉树OJ算法题，都出在普通二叉树上。
二叉树的遍历
二叉树是递归实现的
思想：
- 当你看到一棵树就要有一个思想，要把树看成递归的，这点很重要。
- 任何一棵树都要分为根，左子树，右子树。并且左右子树到空才算结束。
- 递归就是大问题分成小问题，一直分解，直到不可分割后，就结束递归了。
前序遍历
也叫先根遍历，遍历方式是， 根，左子树，右子树，根可以直接遍历，左子树和右子树不可以直接遍历，左子树还会继续分为根， 左子树， 右子树。
1 2 3 null null null 4 5 null null 6 null null
中序遍历
也叫中根遍历，遍历方式是：左子树， 根， 右子树
null 3 null 2 null 1 null 5 null 4 null 6 null
后序遍历
遍历方式为：左子树， 右子树， 根
null null 3 null 2 null null 5 null null 6 4 1
层序遍历
最简单的遍历，就是一层一层的遍历。
1 2 4 3 5 6
