目录
1.树的概念和结构
1.1 树的概念
1.2 树的相关概念
1.3 树的表示
2. 二叉树的概念与结构
2.1 概念
2.2 特殊二叉树
2.3 二叉树的性质
2.4 二叉树的存储结构
第一种：顺序存储结构
第二种：链式存储结构
1.树的概念和结构
1.1 树的概念
树是一种非线性的数据结构，它是由n(n>0)个有限结点组成一个具有层次关系的集合，把它称为树是因为它看起来像一棵倒挂的树，根在上，枝叶在下。
1、根节点是一个没有前驱结点的特殊结点；
2、除根节点外，其叶结点被分为M（M>0）个互不相交的集合T1，T2，T3...Tm，其中每一个集合Ti（1<=i<=m）又是一棵结构与树类型相似的子树，每棵树的根节点有且仅有一个前驱，可以有0个或多个后继；
3、树是递归定义的：任何一棵树都是由根和N棵子树构成的(N≥0)；
4、对于任意一棵树，其子树是不相交的；
1.2 树的相关概念
（1）结点的度：一个结点含有的子树的个数，如A结点的度为6；
（2）叶结点或终端结点：度为0的结点，如H、I、P、Q、K、L、M、N；
（3）非终端结点或分支结点：度不为0的结点，如：D、E、F、G、J；
（4）双亲结点或父节点：含有子结点的结点，称该结点为其子结点的父结点，如A是B的父结点；
（5）孩子结点或子结点：一个结点含有的子树的根节点称为该结点的子结点，如B是A的子结点；
（6）兄弟结点：具有相同父结点的结点，如B和C是兄弟结点；
（7）树的度：一棵树中最大的结点的度称为树的度，如上图树的度为6；
（8）结点的层次：从根开始定义，根为第一层，根的子结点为第二层，以此类推；
（9）树的高度或深度：树中结点的最大层次，如上图树的高度或深度为4；
（空树高度为0，只有一个结点的树高度为1）
（10）堂兄弟结点：双亲在同一层的结点称为堂兄弟，如H和I互为堂兄弟结点；
（11）结点的祖先：从根到该结点所经分支上的所有结点，如A是所有结点的祖先；
（12）子孙：以某节点为根的子树中任一结点都成为该结点的子孙，如所有节点都是A的子孙；
（13）森林：由m（m>0）棵互不相交的树的集合称为森林；
1.3 树的表示
树的存储相较于线性表要复杂得多，既要存储结点的值，也要存储结点与结点之间的关系；
树有很多种表达方式，如双亲表示法、孩子表示法、孩子双亲表示法。
表达树最常用的结构是左孩子右兄弟表示法。
代码表示如下：
typedef int DataType;
struct TreeNode
{struct TreeNode* firstchild; //指向第一个孩子结点struct TreeNode* pnextbrother; //指向下一个兄弟结点DataType data; //结点中的数据域
};
//注意此处的兄弟指的是亲兄弟而非堂兄弟，即此处指向的兄弟有相同的祖先2. 二叉树的概念与结构
2.1 概念
1、一个二叉树的结点是一个有限集合，该集合：
① 或者为空 ② 有一个根节点加上两个别称为左子树和右子树的二叉树组成；
2、特点：
（1）不存在度大于2的结点；
（2）二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树；
3、任意一种二叉树都是由以下五种情况复合而成：
①空树 ②只有根节点 ③只存在左子树 ④只存在右子树 ⑤左右子树均存在；
2.2 特殊二叉树
（1）满二叉树
每层节点数都是最大值的二叉树，即满足层数为k，第k层有2^(k-1)个结点，k=0、1、2...结点总数是2^k-1的二叉树就是完全二叉树。
（2）完全二叉树
对于深度为k的二叉树，前k-1层的结点都是满的，最后一层不满但满足存在的结点是从左向右是连续的。
2.3 二叉树的性质
（1）若规定根结点层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点；
（2）若规定根结点层数为1，则深度为h的二叉树的最大结点数是2^k-1；
（3）对任何一个二叉树，如果度为0的结点个数为n0，度为2的分支节点个数为n2，则有n0=n2+1;
（4）若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)（以2为底)；
2.4 二叉树的存储结构
二叉树的存储结构有顺序存储结构和链式存储结构两种；
第一种：顺序存储结构
1、一般使用数组存储只适合表示完全二叉树或满二叉树，若是一般二叉树会存在很多空间浪费；
在现实使用中，只有完全二叉树才会使用数组来存储；
2、二叉树的顺序存储在物理上是一个数组，在逻辑上是一个二叉树。
3、同时顺序存储可以根据下标计算结点父子关系：
知父求子：leftchild=parent*2+1，leftchild=parent*2+2;
知子求父：(parent-1)/2;
第二种：链式存储结构
二叉树的链式存储结构是指用链来指示元素的逻辑关系，通常方法是链表结点由三个域组成：
数据域、左指针域、右指针域，左右指针分别指向左孩子和右孩子的链结点。
二叉树的链式存储有两种结构：二叉链和三叉链：
