一，树
树是一种分层结构。
树结构之所以在算法理论与实际应用中始终都扮演着最关键的角色，并且有着不计其数的变种，其实并不足为怪⎯⎯层次化的概念几乎蕴含于所有事物之中，乃是它们的本质属性之一。从文件系统、Internet 的域名系统、数据库系统到人类社会系统，层次结构无所不在。
** 节点的深度 **——从树根通往任一节点的路径长度，恰好等于该节点的深度。
树中的元素也称作节点（Node）。此外，按照如下规则，树中的每个节点v都被赋予了一个特殊的指标——深度，记作depth(v)：
- 每个节点的深度都是一个非负整数；
- 深度为0 的节点有且仅有一个，称作树根（Root）；
- 对于深度为k (k≥1)的每个节点u，都有且仅有一个深度为k-1 的节点v 与之对应，称作u 的父亲（Parent）或父节点。
树的深度与高度——树中所有节点的最大深度，称作树的深度或高度
任一节点的孩子数目，称作它的“度”（Degree）
一个节点是叶子，当且仅当它的度数为零。
树中节点的数目，总是等于边数加一
它告诉我们：就渐进复杂度而言，树中边的总数与节点的总数相当。正是基于这一事实，在对涉及树结构的有关算法做复杂度分析时，我们可以用节点的数目来度量树结构本身的存储空间复杂度。
树中任何两个节点之间都存在唯一的一条路径
{ (p, l), (l, f), (f, b), (b, a), (a, d), (d, h), (h, n) }构成了一条联接于节点p和n之间长度为7 的路径。
二叉树——每个节点均不超过2 度的有序树，称作二叉树（Binary tree）。
二叉树相关结论
- 在二叉树中，深度为k 的节点不超过2k 个
- 高度为h 的二叉树最多包含2h+1-1 个节点
- 由n 个节点构成的二叉树，高度至少为⎣log2n⎦。
- 在二叉树中，叶子总是比2 度节点多一个。
真二叉树——不含1 度节点的二叉树，称作真二叉树（Proper binary tree），否则称作非真二叉树（Improper binary tree）。
满二叉树——若二叉树T 中所有叶子的深度完全相同，则称之为满二叉树（Full binary tree），如下图为高度为3的满二叉树
完全二叉树——若在一棵满二叉树中，从最右侧起将相邻的若干匹叶子节点摘除掉，则得到的二叉树称作完全二叉树（Complete binary tree）。
二，树抽象数据类型及其实现
1，树的模型——“父亲-长子-弟弟”模型
根据树的定义，每个节点的所有后代均构成了一棵子树，故从数据类型的角度来看，树、子树以及树节点都是等同的。这里，将它们统一为一个类：Tree。
节点的结构：
树的结构：
2，树ADT
| 操作方法 | 功能描述 |
|---|---|
| getElement() | 返回存放于当前节点处的对象 输入：无 输出：对象 |
| setElement(e) | 将对象e 存入当前节点，并返回其中此前所存的内容 输入：一个对象 输出：对象 |
| getParent() | 返回当前节点的父节点 输入：无 输出：树节点 |
| getFirstChild() | 返回当前节点的长子 输入：无 输出：树节点 |
| getNextSibling() | 返回当前节点的最大弟弟 输入：无 输出：树节点 |
3，基于链表实现树
接口：
package dsa.Tree;
/*
* 树ADT接口
*/
public interface Tree {
// 返回当前节点中存放的对象
public Object getElem();
// 将对象obj存入当前节点，并返回此前的内容
public Object setElem(Object obj);
// 返回当前节点的父节点
public TreeLinkedList getParent();
// 返回当前节点的长子
public TreeLinkedList getFirstChild();
// 返回当前节点的最大弟弟
public TreeLinkedList getNextSibling();
// 返回当前节点后代元素的数目，即以当前节点为根的子树的规模
public int getSize();
// 返回当前节点的高度
public int getHeight();
// 返回当前节点的深度
public int getDepth();
}
基于链表实现树结构
package dsa.Tree;
/*
* 基于链表实现树结构
*/
public class TreeLinkedList implements Tree {
private Object element;// 树根节点
private TreeLinkedList parent, firstChild, nextSibling;// 父亲、长子及最大的弟弟
// （单节点树）构造方法
public TreeLinkedList() {
this(null, null, null, null);
}
// 构造方法
public TreeLinkedList(Object e, TreeLinkedList p, TreeLinkedList c,
TreeLinkedList s) {
element = e;
parent = p;
firstChild = c;
nextSibling = s;
}
/*---------- Tree接口中各方法的实现 ----------*/
// 返回当前节点中存放的对象
public Object getElem() {
return element;
}
// 将对象obj存入当前节点，并返回此前的内容
public Object setElem(Object obj) {
Object bak = element;
element = obj;
return bak;
}
// 返回当前节点的父节点；对于根节点，返回null
public TreeLinkedList getParent() {
return parent;
}
// 返回当前节点的长子；若没有孩子，则返回null
public TreeLinkedList getFirstChild() {
return firstChild;
}
// 返回当前节点的最大弟弟；若没有弟弟，则返回null
public TreeLinkedList getNextSibling() {
return nextSibling;
}
// 返回当前节点后代元素的数目，即以当前节点为根的子树的规模
public int getSize() {
int size = 1;// 当前节点也是自己的后代
TreeLinkedList subtree = firstChild;// 从长子开始
while (null != subtree) {// 依次
size += subtree.getSize();// 累加
subtree = subtree.getNextSibling();// 所有孩子的后代数目
}
return size;// 即可得到当前节点的后代总数
}
// 返回当前节点的高度
public int getHeight() {
int height = -1;
TreeLinkedList subtree = firstChild;// 从长子开始
while (null != subtree) {// 依次
height = Math.max(height, subtree.getHeight());// 在所有孩子中取最大高度
subtree = subtree.getNextSibling();
}
return height + 1;// 即可得到当前节点的高度
}
// 返回当前节点的深度
public int getDepth() {
int depth = 0;
TreeLinkedList p = parent;// 从父亲开始
while (null != p) {// 依次
depth++;
p = p.getParent();// 访问各个真祖先
}
return depth;// 真祖先的数目，即为当前节点的深度
}
}
三，树的遍历
所谓树的遍历（Traversal），就是按照某种次序访问树中的节点，且每个节点恰好访问一次。也就是说，按照被访问的次序，可以得到由树中所有节点排成的一个序列。
深度优先遍历（Depth-first Traversal）：
前序遍历、中序遍历、后序遍历都属于深度优先遍历
1，前序遍历（Preoder traversal）——中>左>右
2，中序遍历（Inorder traversal）——左>中>右
中中序遍历只有对二叉树才有意义
3，后序遍历（Postorder traversal）——左>右>中
广度优先遍历（Breadth-first traversal）
层次遍历属于广度优先遍历
1，层次遍历（Traversal by level）
