树的定义：
树是n个节点（n≥0）的有限集，n＝0称为空树。在任意一个非空树中，有且只有一个根节点，其余节点可以分为m个互不相交的有限集，并且每一个集合本身又是一棵树称为根的子树。
节点的分类：
节点拥有的子树数量称为节点的度。度为0的节点称为叶子结点，度不为0的节点称为分支节点，除根节点外的分支节点又称为内部节点。树的度是树内各个节点度的最大值。
节点的关系：
节点子树的根称为该节点的孩子，该节点称为孩子节点的双亲也叫父节点，拥有同一个父节点的孩子之间称为兄弟节点。节点的祖先便是从根到该节点分支上的所有节点。以某节点为根的
子树上的所有的点称为该节点的子孙。
森林的定义：
森林是m（m≥0）个互不相交的树的集合。
二叉树的定义：
二叉树(Binary Tree)是n(n≥0）个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
特殊的二叉树：1.斜树：树中每个节点仅有左子树或者仅有右子树。
2.满二叉树：所有分支节点均有左子树和右子树，且所有叶子节点均在同一层上。
3.完全二叉树：按层对该二叉树进行编号，若该二叉树所有的编号与满二叉树相同便可称为完全二叉树。
完全二叉树
完全二叉树的性质：
(1)叶子结点只能出现在最下两层。
(2)最下层的叶子一定集中在左部连续位置。
(3)倒数二层，若有叶子结点，一定都在右部连续位置。
(4)如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
(5)同样结点数的二叉树,完全二叉树的深度最小。
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
其实是根据根节点遍历前后来定义，先访问根节点则是前序遍历，在左右子树中间访问则是中序遍历，最后访问则是后序遍历。
1．前序遍历（根-左-右）
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
void PreOrder(Tree* x){
if(x==NULL)return;
cout<<x->data;
PreOrder(x->left);
PreOrder(x->right);
}
2.中序遍历（左-根-右）
void PreOrder(Tree* x){
if(x==NULL)return;
PreOrder(x->left);
cout<<x->data;
PreOrder(x->right);
}
3.后序遍历（左-右-根）
void PreOrder(Tree* x){
if(x==NULL)return;
PreOrder(x->left);
PreOrder(x->right);
cout<<x->data;
}
4.层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问,从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图6-8-5所示，遍历的顺序为:ABCDEFGHI。
推导遍历结果：
由前序遍历和中序遍历推导后序遍历。已知一个二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，求后序遍历。
由前序遍历可知根节点为A（前序遍历根在第一个），再到中序遍历中找到A，可知左子树为CB，右子树为EDF。如图
再到前序遍历中找到CB的一种排列为BC，由于B在第一个可知左子树的根节点为B，儿子节点为C。以此类推可知右子树的根节点为D，左右叶子分别为E，F。
类似的也可以由后序遍历和中序遍历推出前序遍历，只不过后序遍历的根节点为最后一个。
但是需要注意的是由前序遍历和后续遍历不能唯一确定一棵二叉树。
标签：PreOrder,结点,遍历,--,前序,笔记,二叉树,节点,408 From： https://www.cnblogs.com/redintoncforever/p/17029958.html