目录
一、树的定义与基本概念
基本概念：树是一种非线性的数据结构，它由n（n>=0）个有限结点组成一个有层次关系的集合。树有一个特殊结点是根结点，他没有前驱结点，可以理解成所有结点都是由这个结点延展出去的。除了这个根结点后面的子结点都是互不相交的集合（也就是只有一个途径才能知道这个子结点一棵树有n个结点，就有n-1条边），只有这样才能保持是树这个结构。
基本术语
树的表示一半使用的是孩子兄弟表示法
struct TreeNode
{
struct TreeNode* child;//下面的孩子
struct TreeNode* brother;//右边兄弟
int data;//数据
};孩子兄弟表示法示意图
二、常见的树结构
1.二叉树
二叉树是结点的一个有限集合，该集合由一个根结点加上两颗一个为左子树一个为右子树的二叉树组成或者为空。
1.1满二叉树
满二叉树就是每层的结点数都达到最大值（每层结点都为2），一个二叉树的层数为k，那么结点总数通过等比求和可得2^k-1。缺点就是过于完美。
1.2完全二叉树
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引进的。对于深度/高度为k的，有n个结点，编号结点从1到n的结点于这二叉树和满二叉树一一对应就称为完全二叉树。
1.2.1堆数据结构
1.3二叉树数据结构
1.4二叉树性质与特点
二叉树特点：1.不存在度大于2的结点2.二叉树子树有左右之分，必须从左子树开始。
二叉树性质 1.根据满二叉树可得根结点的层数为1，则第i层中最多结点个数为2^（i-1）
2.根结点层数为1，深度/高度为h则总结点最多为2^h -1（等比求和）。
3.若根结点层数为1，总结点个数为n，则可知深度h=log2 （n+1）二叉树存储结构一种是顺序结构，一种是链式结构，一般数组的顺序结构适用于完全二叉树，不是完全二叉树会有空间浪费。
二叉树性质：对于具有n个结点的完全二叉树，如果按照从上到下从左到右顺序从0开始为根结点，对于序列为i的节点：1.i＞0，i位置节点的双亲序列为（i-1）/2；i＝0，为根结点无双亲结点。2.若2i+1＜n，则左孩子的序列为2i+1，2i+2＜n。右孩子的序列为2i+2。
链式二叉树对任何一棵2叉树，如果度为零其叶子节点的个数为n0，度为二的分支节点个数为n2，则有n0=n2+1，通过规律三叉树也可知道n0 =2*n3+n2+1;可知n0 = (i-1)ni+....n2+0*n1+1;通过推理得
1.5包含关系
三、树的遍历方式
层序遍历（非递归利用队列数据结构）详细可去看二叉树那一博客链式二叉树数据结构（递归）_递归创建二叉树-CSDN博客
前中序遍历（递归）
遍历规则
按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前访问顺序为：根结点、左⼦树、右⼦树
2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）访问顺序为：左⼦树、根结点、右⼦树
3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后访问顺序为：左⼦树、右⼦树、根结点
一般遇到选择题知中序和两个中其中一个遍历顺序，可以得到层序遍历，对待这种题目就是通过前或者后序遍历得到根节点，然后左右子树的都是不断寻找对应的父结点，然后不断用一个遍历假设去，然后再用另一个遍历来验证。
四、树的存储结构
二叉树存储结构一种是顺序结构，一种是链式结构。对于完全二叉树一般都是以顺序结构数组存储，而对于非完全二叉树就算用的指针链式结构来存储数据。当然也不能说限定死他们存储结构，例如完全二叉树也是可以用指针链式结构存储的，但是链式结构需要为每个节点存储额外的指针（左孩子、右孩子），相比顺序存储（数组）直接通过下标计算父子关系，空间利用率较低。例如，存储n个节点的完全二叉树，链式结构需要至少2n个指针（假设无父指针），而数组仅需n个连续空间。其次非完全二叉树也是可以使用数组这个顺序结构的，只不过使用数组会导致数组空间的浪费。所以完全二叉树使用顺序结构和非完全二叉树使用链式结构都是考虑实际过程中使用（从性能考虑），而具体问题具体分析对于需要使用顺序结构的非完全结构等也会看实际需求。