树的定义

1. 什么是树

树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。

在任意一颗非空树中：
(1) 有且仅有一个特定的称为根（Root）的结点。
(2) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、.....、Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)

下图就符合树的定义：

其中根结点A有两个子树：

对于树的定义还需要强调两点：

• n>0时根结点是唯一的，不可能存在多个根结点
• m>0时，子树的个数没有限制，但它们一定是互不相交的。下面的图明显不符合互不交互的原则，所以不是树:

2. 结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。

度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。

树的度是树内各结点的度的最大值。

如图所示，因为这棵树结点的度的最大值是结点D的度，为3,所以树的度也为3：

结点的子树的根称为该结点的孩子（Child）,相应地，该结点称为孩子的双亲（Parent）。

同一个双亲的孩子之间互称兄弟（Sibling）。

结点的祖先是从根到该结点所经分支上的所有结点。

反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

如图：对于H来说，D、B、A都是它的祖先，B的子孙有D、G、H、I。

3. 树的其他相关概念

结点的层次从根开始定义起，根为第一层，根的孩子为第二层，以此类推。树的深度（Depth）或高度是树中结点的最大层次。如下图，当前树的深度为4：

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林(Forest)是m (m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林

线性结构	树结构
第一个数据元素：无前驱	根结点：无双亲，唯一
最后一个数据元素：无后继	叶结点：无孩子，可以多个
中间元素：一个前驱一个后继	中间节点：一个双亲多个孩子

树的存储结构

树中的某个结点的孩子可以有多个，所以仅仅使用简单的顺序结构或者链式结构是不能完全表示一整棵树的。

不过充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。我们这里要介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

1. 双亲表示法

以双亲作为索引的关键词的一种存储方式。每个结点只有一个双亲，所以选择顺序存储占主要，以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点位置的指针域。

package com.hukai.demo.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 双亲表示法
 * 
 * @author hukai
 */
public class PTree<E> {

	/**
	 * 默认数组的长度
	 */
	private static final int DEFAULT_SIZE = 16;

	/**
	 * 定义一个数组用于保存树中的节点
	 */
	private Node<E>[] elementData;

	/**
	 * 节点总数
	 */
	private int nodeNums = 0;

	/**
	 * 树的最大结点数
	 */
	private int treeSize;

	public PTree(E data) {
		this(data, DEFAULT_SIZE);
	}

	@SuppressWarnings("unchecked")
	public PTree(E data, int treeSize) {
		this.elementData = new Node[treeSize];
		this.treeSize = treeSize;
		elementData[0] = new Node<E>(data, -1);
		nodeNums++;
	}

	/**
	 * 为指定节点添加子节点
	 * 
	 * @param data
	 * @param parent
	 */
	public void addNode(E data, Node<E> parent) {
		for (int i = 0; i < treeSize; i++) {
			// 找到数组中第一个为null的元素，该元素保存新节点
			if (elementData[i] == null) {
				// 创建新节点，并用指定的数组元素保存它
				elementData[i] = new Node<E>(data, position(parent));
				nodeNums++;
				return;
			}
		}
		throw new RuntimeException("该树已满，无法添加新节点");
	}

	// 返回指定节点（非根结点）的父节点
	public Node<E> parent(Node<E> node) {
		// 每个节点的parent记录了其父节点的位置
		return elementData[node.parent];
	}

	// 返回指定节点（非叶子节点）的所有子节点
	public List<Node<E>> children(Node<E> parent) {
		List<Node<E>> list = new ArrayList<Node<E>>();
		for (int i = 0; i < treeSize; i++) {
			// 如果当前节点的父节点的位置等于parent节点的位置
			if (elementData[i] != null && elementData[i].parent == position(parent)) {
				list.add(elementData[i]);
			}
		}
		return list;
	}

	/**
	 * 返回指定结点的索引
	 * 
	 * @return
	 */
	public int position(Node<E> node) {
		for (int i = 0; i < treeSize; i++) {
			// 找到指定节点
			if (elementData[i] == node)
				return i;
		}
		return -1;
	}

	/**
	 * 返回根结点
	 * 
	 * @return
	 */
	public Node<E> root() {
		return elementData[0];
	}

	/**
	 * 结点结构
	 */
	private static class Node<E> {
		E data;
		int parent;

		public Node() {
		}

		public Node(E data) {
			this.data = data;
		}

		Node(E data, int parent) {
			this.data = data;
			this.parent = parent;
		}
	}
}

有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，如图：

优点：parent指针域指向数组下标，所以找双亲结点的时间复杂度为O(1),向上一直找到根节点也快

缺点：由上向下找就十分慢，若要找结点的孩子或者兄弟，要遍历整个树

怎么改进一下呢？

如果我们很关注结点的孩子，可以増加一个结点最左边孩子的域，不妨叫它长子域。这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1.如图：

缺点：这样消耗了大量的空间，是不必要的。

我们尽可能使用较小的空间，所以我们一般只添加一个长子域，可以获取到有0个或1个孩子结点，甚至两个子树都可以获取，但是对于较多的孩子我们若是非得使用顺序存储，就得增加多个孩子的指针域。

另外一个问题场景，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系。则可以増加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1：

总结：存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。

2. 孩子表示法

换种思路，既然双亲表示法获取某结点的所有孩子有点麻烦，我们索性让每个结点记住他所有的孩子。但是由于一个结点拥有的孩子个数是一个不确定的值，虽然最多只有树的度那么多，但是大多数结点的孩子个数并没有那么多，如果用数组来存放所有孩子，对于大多数结点来说太浪费空间了。Java内置的LinkedList是个不错的选择。

把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

package com.hukai.demo.tree;

import java.util.LinkedList;
import java.util.List;

/**
 * 孩子表示法
 * @author hukai
 *
 */
public class ChildrenTree<T>{
	
	// 树的容量，能容纳的最大结点数
    private int treeCapacity;
    // 树的结点数目
    private int nodesNum;
    // 存放树的所有结点
    private Node<T>[] nodes;
    
    public ChildrenTree(int treeCapacity) {
        this.treeCapacity = treeCapacity;
        nodes = new Node[treeCapacity];
    }

    public ChildrenTree() {
        treeCapacity = 128;
        nodes = new Node[treeCapacity];
    }
    
    public void addChild(T data, Node<T> parent) {
        if (nodesNum < treeCapacity) {
            // 新的结点放入数组中第一个空闲位置
            nodes[nodesNum] = new Node<>(data);
            // 父结点添加其孩子
            parent.children.add(nodesNum);
            nodesNum++;
        } else {
            throw new RuntimeException("树已满，无法再添加结点！");
        }
    }
	
	/**
	 * 内部结点类
	 * @author hukai
	 */
	public static class Node<T> {
		private T data;
        private List<Integer> children;
        
        public Node(T data) {
            this.data = data;
            this.children = new LinkedList<>();
        }
        
        public Node(T data, int[] children) {
            this.data = data;
            this.children = new LinkedList<>();
            for (int child : children) {
                this.children.add(child);
            }
        }
        
        public T getData() {
            return data;
        }
	}

}

优化：这种方式获取某结点父结点的方法需要遍历所有结点，如果要改进，可以将双亲表示法融合进去，增加一个parent域就行。也就是说，Node类改成如下就行，这种实现可以称为双亲孩子表示法。

public static class Node<T> {
    private int parent;
    private T data;
    private List<Integer> children;
}

3. 孩子兄弟表示法

刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢？当然，对于树这样的层级结构来说，只研究结点的兄弟 是不行的，我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。

基于这种思想，可以用具有两个指针域（一个指向当前结点的孩子，一个指向其兄弟）的链表实现。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右兄弟所在的链结点的存储地址。其结点结构为:

整个结构就是一条有两个走向的错综复杂的链表，垂直走向是深入到结点的子子孙孙；水平走向就是查找它的兄弟姐妹。这种结构也能直观反映树的结构的，上图其实就是下面这棵树。

若是想让获取父结点变得方便些，也可以多设置一个parent域，见孩子表示法的优化。