一、树
子结点:和父结点相对，一个结点的后继结点。
父结点:和子结点相对，一个结点的前驱结点。
根结点:没有父结点的结点。
叶子结点:没有子结点的结点。
祖先:从根结点到当前结点路径上的所有点（除了自己) 。
兄弟:具有同一个父结点的所有结点，互为兄弟结点。
结点的度:一个结点的子结点的数量。
树的度:树中每个结点最多可以拥有的子结点的数量。
结点层次（结点深度）:根结点看成是第1层，子结点的层数是其父结点的层数加1。有的时候结点的深度有可能从0开始。
树的高度（树的深度）:树中所有结点的层次的最大值。
堂兄弟:属于同一个层次的所有结点，父结点不同，互为堂兄弟。
子树:以树中某一结点为根结点的所有子结点构成的树。空树是任意树的子树。
空树:没有结点的树。
森林:多个不同的树在一起共同构成森林。
注:树的定义同样可以用于二叉树。
二、二叉树
树型数据结构中，最常用的是二叉树。
树是由结点和结点之间相连的边组成的数据结构。二叉树是对于每个结点，最多有两个子结点。
左边的结点叫做左孩子，右边的结点叫做**右孩子**。以左孩子为根结点的子树叫做原树的左子树，以右孩子为根结点的子树叫做原树的右子树林*。
除了根节点之外，每个结点都有且只有一个父结点。
递归定义
1．空结点，单个结点是一个二叉树2.二叉树的左右子树也是一个二叉树
二叉树的5种形态
1．空二叉树（一个结点都没有)2．只有根结点的二叉树
3．只有左子树的二叉树4．只有右子树的二叉树
5．左右子树均不为空的二叉树
三、性质
性质1
二叉树的第i层最多有2^{i-1}个结点
根结点定义为第1层，一个结点的子结点的层数加1
性质2
二叉树的前i层最多共有2^i-1个结点
深度(二叉树的最大层数）为i的二叉树最多共有2^i-1个结点
性质3
1．结点的度:一个结点的子结点的数量如果一个二叉树，共有n个结点,度为0的结点（叶子结点）数量是n0，度为1的结点数量是n1，度为2的结点数量是n2。n0=n2+1
2．树的度:树中所有结点的度的最大值
满二叉树
如果一个二叉树，每层结点数都是这层的最大值，这个树就是一个满二叉树。
完全二叉树
如果一个二叉树从上往下，每层从左往右，依次编号为，1、2、3、… … 。
如果每个结点的编号和满二叉树中对应位置的结点的编号完全一样，那么这个树是一个完全二叉树*。
**如果一个二叉树，除了最后一层以外，是一个满二叉树。最后一层结点是从最左边往右依次长满。是一个完全二叉树。
性质4
n个结点的完全二叉树的深度是$\lfloor{log_2n}\rfloor+1$
性质5
对于一个n个结点的完全二叉树，从上往下，从左往右依次编号为1到n。对于任意一个结点i，如果其有左孩子，则左孩子编号是2i
对于任意一个结点i，如果其有右孩子，则右孩子编号是2i+1对子任意一个结点i，如果其有父结点，则艾结点编号是i/2
对于完全二叉树，可以使用数组存储。
四、二叉树的遍历
中序遍历:左子树-根-右子树
后序遍历:左子树-右子树-根
按照上述三种遍历方式:
先序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
如果已知先序遍历、中序遍历,求后序遍历
先序遍历可以确定根结点，再根据根结点，在中序遍历中确定对于当前根结点的左子树和右子树，递归求解还原二叉树。根据后序遍历的特点:左子树-右子树-根
对于当前树的根是最后输出
先递归求左子树，再递归求右子树，最后递归输出根
不能通过先序遍历+后序遍历确定唯一的二叉树
