---

一、树的基本概念

 1.树：n>=0个结点的有限集，n=0空树；在非空树中有且仅有一个根节点，除根结点外每个结点有且仅有一个交点；一颗n个结点的树有n-1条边。

 2.结点的度（Degree ）：结点子树的个数。

 3.树的度：树的所有节点中最大的度数。

 4.叶结点(leaf):度为零的结点。

 5.父结点（Parent）：所有子树结点都是其子树的根节点的父节点。

 6.子结点（Child）：A是B的父结点，则B是A的子结点，也称孩结点。

 7.兄弟节点（Sibling）：具有同一父结点的各个结点彼此是兄弟结点。

 8.路径和路径长度：距根结点边的个数。

 9.祖先结点（Ancestor）：延根到某一路径上的所有结点都是这个结点的祖先节点；

 10.子孙结点（Descendant）：某一结点的子树的所有结点都是这个结点的子孙。

 11.结点的层次（Level）：根结点在第一层，其他任意结点都是父结点层数加一。、

 12.树的深度（Depth）：树所有结点中最大层次是这棵树的深度。

注：

     1.n>0根结点唯一；

     2.m>0子数没有限制，但子树不相交。

二、二叉树

 1.二叉树的定义及其特征

  （1）定义：每个节点至多有两个子树，二叉树的子树有左右之分，次序不可以颠倒；n(n>=0)结点的有限集，n=0空二叉树，由一个根节点和两个互不相交的被称为根的左右子树组成

  （2）二叉树和度为二的有序树的区别：度为二的树至少有三个节点，二叉树可以为空；度为二的有序树的孩子结点的左右次序是相对另一孩子节点而言的，若只有一个孩子节点，无需分左右，二叉树左右孩子是确定的。

  （3）特殊二叉树

   a.满二叉树：高度为h，含2^h-1结点称为满二叉树；除叶子节点树外其余结点的度为2，自上而下，自左至右编号编号为i的结点双亲为i/2，左孩子2i，右孩子2i...