1.树的基本概念

1.1 概念

下面是一个树的例子，下面以这个树介绍基本概念。

A节点是根节点,A节点和F节点由一条边连接；F节点是A节点的儿子，并且是K,L,M节点的父亲。没有儿子节点的节点叫做树叶(例如B,C,H等)，具有相同父亲的节点称为兄弟(例如K,L,M)。
对于n1,n2,...nk的序列，对于任何1<=i<=k，ni都是ni+1的父亲节点，这样的序列称为从n1到nk的路径。路径的长等于这条路径上边的个数。对任意节点ni，它的深度就是从根到ni的唯一的路径的长。对任意节点ni，它的高就是从ni到一片树叶的最长路径的长。例如，上图中E的深度为1，高度为2。如果存在一条从 n1到n2的路径，那么n1称为n2的祖先，n2称为n1的后裔，如果n1不等于n2，称为真祖先和真后裔。

1.2 实现：

由于树的每个节点的儿子节点的个数不定，所以实现树时，将树的每个节点的所有儿子都放在树节点的链表中。

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

firstChild指向节点的第一个儿子节点，nextSibling指向节点的下一个兄弟节点。
树的一个广泛应用是Unix文件目录模拟。树的遍历一般有2种主要方式，先序遍历是先处理数节点，再处理该节点的孩子节点。后续遍历是先处理该节点的孩子节点，再处理该节点。

2. 二叉树

二叉树是一种树，每个节点的孩子节点不能超过二个。因为二叉树的每个节点至多只有2个孩子节点，所以可以使用下边的数据结构来表示。

class TreeNode {
    Object element;
    TreeNode left;
    TreeNode right;
}