树的概念与结构：
1.1树的结构
树的结构是一种非线性的数据结构，它是由n（n>=0）个节点组成的一个有层次的关系集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说他是根朝上，而叶朝下。
有一个特殊的结点，称为根结点，根节点没有前驱结点
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
所以树是被递归定义的（一个问题可以分成几个子问题并且具有相同的解决办法）
（就像这样将根节点去掉，它就是多个树，它只有一个前驱，但是可以有多个后继）
注意：树的结构中，子树之间不能有交集，否则就不是树形结构
1.2树的相关概念
节点的度：一个节点含有的子树的个数称为这个节点的度；比如上图中A的度为6，D的度为1；
叶节点或者终端节点：度为0的节点叫做叶节点，就像上图中的BHIPQ...,就是每个枝端最后的一个节点
非终端节点或者分支节点：度不为0的节点，如上图中的DEFGJ
双亲节点或父节点：若一个节点含有子节点，那么这个节点就称为其子节点的父节点，如上图：A就是BCDEFG的父节点
D就是H的父节点
孩子节点或者子节点:一个节点含有子树的根节点叫该节点的子节点：如上图：BCD就是A的子节点
兄弟节点：具有相同父节点的节点就互相为兄弟节点；就像上图中：BCD是，IJ也是。
树的度：一颗树中，最大节点的度叫做树的度；如上图树的度是。
节点的层次：从根开始定义，根为第一层，根的节点是第二层......
树的高度或深度：树中节点的最大层次，如上图树的深度为4、
堂兄弟节点：双亲在同一层的节点互为堂兄弟；就像上图中的HI\HK；
节点的祖先：从根节点到该节点所经分支上所有的节点；如上图：A是所有节点的祖先
子孙：以某个节点为根的子树中任意的节点都称该节点的子孙。如上图：所有节点都是A子孙
森林：由 m（M>0）棵不相交的树的集合叫做森林。
1.3树的表示
树的表示法有：
1.孩子表示法：
就是每个节点保存值域与孩子的指针域。注意：有几个孩子就需要几个指针域，节点中的字段个数：要比树的度大一（要保存值域）
就像A就需要4个字段，三个孩子的指针域和一个值域
优势：找某个节点的孩子很方便
缺点：找双亲不是很方便
2.双亲表示法：
每个节点既要保存值域，也要保存双亲的位置，也就是每个节点需要两个字段
优势：找某个节点的双亲时比较方便
缺点：找某个节点的孩子不是很方便
3.孩子双亲表示法
孩子表示法+双亲表示法结合起来
每个节点既要保存值域，还要保存其双亲与孩子的地址
4.孩子兄弟表示法
每个节点既要保存第一个孩子的节点还要保存下一个兄弟的节点与节点中的数据域 typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };
二叉树的概念与结构
2.1概念
一棵二叉树是结点的一个有限集合，该集合:
1. 空
2. 由一个根节点以及加上两棵别称为左子树和右子树的二叉树组成
一个节点最多只有两个孩子，可以一个都没，或者只有一个节点
二叉树的左右子树也是一个二叉树，定义也是递归的，二叉树有左右之分的，二叉树是有序树。
注意：对于任意的二叉树都是由以下几种情况复合而成的：
满二叉树
每层的节点个数都是2^(i-1)
完全二叉树
假设二叉树的高度为h，前h-1层达到了最大值，第h层的节点是从左到右依次排列的
假设二叉树中有n个节点，如果该二叉树中前N个节点与高度相同的完全二叉树的前n个节点相同，那么就叫二叉树为完全二叉树
二叉树的性质
1.若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个节点
2.若规定根节点的层数为1，那么深度为h的二叉树的最大节点个数为2^-1（等比数列的前n项和）
3.对任意的一颗二叉树，如果度为0，其叶节点的个数为n0，度为二的分 支节点个数为n2，则有n0 = n2+1；通俗的说就是度为0的节点比度为2的节点个数多1个
n0 = 3;
n2 = 2;
n0 = n2+1;
这个方法是用总边数证明的
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2^(n+1）(ps： 是log以2
为底，n+1为对数)
完全二叉树计算出来可能是小数，需要向上取整,就是大于其最近的一个整数
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2，右孩子序号：2i+2，2i+2>=n否则无右孩子
好处：二叉树可以用数组来进行，完全二叉树用数组进行储存空间浪费较少
二叉树的存储结构
二叉树一般有两种存储结构，一种是顺序结构一种是链式结构，顺序结构更适合完全二叉树，否则会有大量的空间浪费，二叉树在物理上是一个数组，在逻辑上是一颗二叉树。
对于顺序结构：
对于链式结构来说：
使用链表来构建一颗树，在来链表的节点中保存数据域和左右指针域。链式结构又分为二叉链和三叉链。
二叉树的顺序结构：
普通二叉树不适合使用数组来储存，会造成大量的空间浪费，完全二叉树适合顺序结构进行储存。现实中我们通常使用堆来进行储存（注意，这里的堆和操作系统中的虚拟空间不是一个东西，一个是数据结构，一个是操作系统中管理内存的一段区域分段）
堆的概念与结构：
说明白点，堆就是从小到大或者从大到小的完全二叉树
所以，堆的性质就是，堆中的某个节点总是不大于或者不小于它的父节点，堆总是一个完全二叉树
小堆也叫小根堆，大堆也叫大根堆
