1.树的定义
树是一种非线性的数据结构，是由有限个结点组成的具有层次关系的集合，形状看起来像一棵倒挂的树，因此叫做树。
树具有一个特殊的结点，叫做根节点，该结点没有前驱结点。除根节点外，其他结点有且仅有一个前驱结点，有零个或者多个后继结点。这些结点又被分为若干颗树，每棵树没有交集，每棵树又被分为根节点和子树。因此，树是递归定义的。
如下图，就是一棵树。
2.树的有关概念
有关概念用下图进行举例
结点的度：结点具有的子树的个数。图中A结点的度为6，B、C结点的度为0。
叶子结点：也称为终端结点，指的是度为0的结点。图中B、C、P、Q等就是叶子结点
树的度：最大的结点的度为树的度。图中树的度为6。
双亲结点：若这个结点有子树，那么这个结点为子节点的双亲结点。图中A为B的双亲结点。D为H的双亲结点。
孩子结点：结点的子树的根节点为该结点的孩子结点。图中C、D为A的孩子结点，J为E的孩子结点。
兄弟结点：具有相同的双亲结点互称为兄弟结点。图中D、E互为兄弟结点。
结点的层次：根节点为第一层，子树的根节点第二层，依次类推。P、Q层次为4
结点的深度或高度：最大的结点的层次。图中树的高度为4。
堂兄弟结点：同一层的结点互为堂兄弟结点。
森林：若干棵不相交的树的集合。
3.树的表示
树的表示有很多方法，如双亲表示法，孩子表示法，左孩子右兄弟表示法。
这里就介绍一种常用的左孩子右兄弟表示法。
方法的意思是，定义一个结构体类型，内有两个指针域，一个指针指向自己的第一个孩子结点，另一个指针指向自己的兄弟结点。
定义一个结构体类型
typedef int DataType;
struct Node
{
struct Node* firstChild; // 第一个孩子结点
struct Node* NextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
该树的存储结构如下图
如果该结点没有孩子或者兄弟，指针指向NULL；
4.二叉树的概念和结构
概念：每个结点的度都不大于2的树称为二叉树。
二叉树分为根、左子树和右子树；左、右子树又分为根、左子树和右子树，以此类推。
如图就是一棵二叉树。
此外任意二叉树都是有以下几种情况组合而成。
4.1特殊的二叉树
4.1.1完全二叉树
假如二叉树的高度为n，如果前n-1层的结点是满的，最后一层的结点从左到右是连续的，那么这种二叉树又称为完全二叉树。
下图就是一棵完全二叉树。前三层结点是满的，最后一层结点是连续的。
下图不是完全二叉树，因为第三层第一个结点没有左树。
此外，还需要知道一些二叉树的性质。
性质1：二叉树第n层的最大结点个数为2^(n-1)。
性质2：若二叉树的高度为n，那么该树最多有2^n-1个结点。
性质3：对于任意一棵二叉树，假设度为0的结点为n0，度为2的结点为n2，那么就有n0=n2+1；
性质4：对于完全二叉树，如果从上到下，从左到右依次对结点进行编号，根节点从0开始，那么假设结点的编号为n，则左孩子编号为2*n+1，右孩子编号为2*n+2;假设结点的编号为m，那么该结点的双亲结点编号为(m-1)/2。
关于性质3的证明。如下图
假设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2
只有一个结点时n0=1，n2=0。满足n0=n2+1。
当增加结点时，会增加一个度为0的结点和一个度为1的结点，同时减少一个度为0的结点，此时增加的结点在叶子结点上。这种情况不会影响n0和n2的值。
当增加的结点不在叶子结点上，那么只能在度为1的结点上，此时会减少一个度为1的结点，增加一个度为2的结点，同时也会增加一个度为0的结点。n0和n2都增加一个，等式不变。
4.1.2满二叉树
二叉树的每一层的结点个数都达到最大值时，该二叉树称为满二叉树。
当完全二叉树的最后一层的结点个数达到该层最大结点数时，又称为满二叉树。
所以满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
下图就是一课满二叉树。
5.二叉树的存储
5.1顺序存储
对于一棵普通二叉树，不适合使用顺序存储，因为会造成大量的空间浪费。顺序存储只适用于完全二叉树。
5.2链式存储
链式存储分为二叉链和三叉链。
二叉链：结构体内有两个指针变量，分别指向左孩子结点和右孩子结点。
结构体定义如下
typedef int BTDataType;
struct BinaryTreeNode
{
struct BinTreeNode* Left; // 指向当前节点的左孩子
struct BinTreeNode* Right; // 指向当前节点的右孩子
BTDataType data; // 当前节点值域
}
三叉链：结构体内有三个指针，分别指向左右孩子结点和双亲结点。
结构体定义如下
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}；
二叉树的存储，对于顺序存储会介绍一个叫做堆的数据结构。链式存储会介绍它的实现以及各个接口和题目。
关于树的部分知识就介绍到这里了。
