树的定义：

1. n（n>=0）个结点的有限集，n=0时是空树，n!=0时是非空树。

• 有且仅有一个称为根的结点。
• 除根节点以外的其余几点分为m(m>0)个互不相交的有限集，每一个集合也是一棵树，称之为根的子树。

• 树的机构定义是一个递归定义，即在树的定义中用到了树的定义。

  
  树的结构示意图

树中结点数等于所有结点度数的和加1. （树的一个特点）

树的基本术语

• 结点：树中的独立单元。
• 结点的度：结点拥有孩子的子树的数量。例如A的度为6。
• 树的度：指树内结点度的最大值。上图树的度为6。
• 叶子：度为0的结点，或者终端结点，也就是说无孩子的结点。
• 非终端结点：内部结点且度不为0的结点。
• 双亲和孩子：结点子树的根成为该该结点的孩子。该结点成为孩子的双亲。E的孩子I,J,IJ的双亲E。
• 兄弟：同一双亲互称兄弟。I和J兄弟。
• 祖先：从根到该结点，所经分支的所有结点。P的祖先A、E、J。
• 子孙：以某一结点为根，它的子树中的任意结点都是该结点的子孙。如E的子孙为IJPQ;
• 层次：从根开始，根第一层，跟的孩子第二层。
• 堂兄弟：不同双亲，确在同一层的结点成为堂兄弟。
• 树的深度：树中结点的最大层次成为树的深度和高度，上图中树的深度为4。
• 有序树和无序树：树中结点的各子树从左到右是有序的，不能互换，该树就是有序树，否则无序树。
• 森林：是m>=0棵互不相交的树的集合。

二叉树

特点

• 二叉树每个结点最多两个子树
• 二叉树的子树有左右之分，次序不能颠倒。

二叉树示意图

二叉树中5个重要性质

• 1. 在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。
• 2. 深度为k的二叉树最多有2^k-1个结点
• 3. 对任何一个二叉树T,如果终端节点树为n,度为2的节点数为m,则n=m+1
• 4. 具有n个结点的完全二叉树的深度为int_UP（log(2，ｎ+1)。
• 5. 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：
     （1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）;
     （2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；
     （3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；
     （4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；
     （5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；
     （6）结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。

二叉树性质摘自中文网可点击此处跳转

满二叉树：深度为k且含有2^k-1个结点的二叉树，上图即为二叉树。
完全二叉树：深度为k，有n个结点的二叉树，并且每一个结点都与深度为k的满二叉树的编号1-n的结点一一对应。
满二叉树的特点：

• 叶子结点 只可能在层次最大的两层出现。(比如深度为6，叶子结点会出现在5,6层)。
• 对任一结点，右分支子孙最大层次为l，左分支的子孙最大为l或者l+1.