目录
树的基础知识
二叉树特点：
二叉树具有五种基本形态：
斜树
满二叉树
特点：
完全二叉树
特点：
二叉树性质
二叉树遍历方法
推导遍历结果
树的基础知识
- 结点拥有的子树数称为结点的度（Degree）。有几个分支度就是多少。
- 度为0的结点称为叶结点（Leaf）或终端结点。度不为0的结点称为非终端结点或分支结点。
- 分支结点也称为内部节点。（除根结点之外）。
- 树的度为树内各结点的度的最大值。
- 树中结点的最大层次称为树的深度（Depth）或高度。
- 如果将树中结点的各子树看成从左至右是有次序的，称为该树为有序树，否则称为无序树。
二叉树特点：
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。没有子树或者有一科子树都是可以的。
- 左子树和右子树是有顺序的。
- 即使树中某结点只有一颗子树，也要区分它是左子树还是右子树。
二叉树具有五种基本形态：
- 空二叉树。
- 只有一个根结点。
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
斜树
所有的结点都只有左子树的二叉树叫左斜树。（右斜树）
满二叉树
分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
特点：
- 叶子结点只能出现在最下一层。
- 飞叶子结点的度一定是2。
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点最多。
完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号的结点与同样深度的满二叉树中的编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
特点：
- 叶子结点只能出现在最下两层。
- 最下层的叶子一定集中在左部连续位置。
- 倒数二层，若有叶子结点，一定都在右部连续位置。
- 如果结点度为1，则该结点只有做孩子，即不存在只有右子树的情况。
- 同样节点数的二叉树，完全二叉树的深度最小。
二叉树性质
性质1：在二叉树的第i层上至多有
个结点（i>=1）。
性质2：深度为k的二叉树至多有
个结点（k>=1）。
性质3：对任何一棵二叉树T，如果其终端结点数为
，度为2的结点数为
，则
=
+1。
性质4：具有n个结点的完全二叉树的深度为（
）+1 （x）定义为不大于x的最大整数。
性质5：如果对一棵有n个结点的完全二叉树（其深度为（
）+1 ）的结点按层序编号（从第1层到第（
）+1 层，每层从左到右），对任一结点i（i<=n && i>=1）有：
- 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点不大于i/2的最大整数。
- 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
- 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树遍历方法
- 前序遍历
规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*二叉树的前序遍历算法*/
void preOrderTraverse(BiTree T)
{
if(T == NULL)
return;
printf("%d",T->data);
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
}
- 中序遍历
规则：若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
/*二叉树的中序遍历算法*/
void midOrderTraverse(BiTree T)
{
if(T == NULL)
return;
midOrderTraverse(T->lchild);
printf("%d",T->data);
midOrderTraverse(T->rchild);
}
- 后序遍历
规则：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
/*二叉树的后序遍历算法*/
void postOrderTraverse(BiTree T)
{
if(T == NULL)
return;
postOrderTraverse(T->lchild);
postOrderTraverse(T->rchild);
printf("%d",T->data);
}
- 层序遍历
规则：若树为空，则操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
推导遍历结果
思路：就是由两种遍历结果推到树的结构，然后根据树写出另一遍历的顺序。
已知前序和中序推导后续遍历顺序
已知中序和后序推导前序遍历顺序
方法：根据前序和后序判断根结点，再由中序遍历确定哪些是左子树，哪些是右子树。
注：已知前序遍历和中序遍历可以确定唯一一棵二叉树。
已知中序遍历和后序遍历可以确定唯一一棵二叉树。
但是已知前序和后序遍历不能确定唯一的二叉树。