树的基本概念

什么是树？

一棵树是一些节点的集合。这个集合可以是空集，若非空，则一棵树由一个称作根(root)的节点r以及0个或n个非空的树T1，T2，…，Tn组成，我们把T1，T2，Tn称为根(root)的子树，这些子树中每一棵的根都被来自根r的一条边(edge)所连接。

树的一种实现

实现树的一种方法可以是在每一个节点数据外还要有一些链指向它的子节点。如上图所示根有Tn个子节点，我们就要有Tn个链指向它。然而，我们刚开始是不知道每个节点的儿子数的，而且每个节点的儿子数不一样。因此在数据结构中建立到各子节点之间的链接的不可行的。
解决方法：我们让第一个子节点链上第二个子节点，第二个子节点链上第三个子节点…，我们把它们称为兄弟链。还有一个孩子链，链上它的第一个孩子。

class TreeNode
{
	Object element;
	TreeNode firstChild;
	TreeNode nextSibling;
}

树的一些名词

已下图的树为例

节点

• 树叶：没有儿子的节点。上图中的树叶是B、F、G、I、J和K。
• 兄弟：相同父亲的节点。上图中B、C、D和E是兄弟，G和H是兄弟，I、J和K是兄弟。
• 祖父和孙子：用类似于兄弟的方法可以定义祖父和孙子的关系。
• 深度：节点T的深度为从根到T的唯一路径的长。
• 高：节点T的高是从T到一片树叶的最长路径的长。因此所有的树叶的高都是0。
• 度：分支的数目。一个节点只有一个分叉就是1度，两个分叉就是2度的子树。

整棵树

• 一棵树的高：等于它的根的高。
• 一棵树的深度：等于它的最深的树叶的深度。也就是树最下面的节点的深度，也就等于这棵树的高。
• 一棵树的度：取树中所有节点的度的最大值。
  

树的遍历

• 先序遍历：先处理节点在先序遍历儿子节点。
• 后序遍历：先后序遍历儿子节点在处理节点。
  还是以棵树为例
  
  先序遍历：ABCFDGHLEIJK
  后序遍历：BFCGLHDIJKEA