Java基础 - 树的实现（一）父节点表示法

父节点表示法：
通过前面的介绍可以发现,树中除根节点之外的每个节点都有一个父节点。为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用来记录该节点的父节点。对于如下图所示的数，可以用一个表（数组）来保存它。

下表记录示范树

数组索引	data	parent
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1
5	F	3
6	G	3
7	H	4
8	I	4
9	J	4
10	K	6
...	...	...

由此可见，只要用一个数组节点来保存树里的每个节点，并让每个节点都记录它的父节点在数组中的索引位置即可。下面的程序实现了父节点表示法的树：

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

/**
 * @see 父节点表示法
 * @author wb
 *
 * @param <E>
 */
public class TreeParent <E> {
	public class Node <T>{
		T data;
		int parent;
		
		Node(){
		}
		Node(T data){
			this.data = data;
		}
		Node(T data, int parent){
			this(data);
			this.parent = parent;
		}
		public String toString(){
			return "TreeParent$Node[data = " + data + ", parent = " + parent + "]";
		}
	}
	
	private final int DEFAULT_TREE_SIZE = 100;
	private int treeSize = 0; //相当于容量吧
	//用来记录树中所有的节点
	private Node<E>[] nodes;
	//用来记录树中节点的个数
	private int nodeNums;
	
	/**
	 * 三种构造方法
	 */
	@SuppressWarnings("unchecked")
	public TreeParent(){
		treeSize = DEFAULT_TREE_SIZE;
		nodes = new Node[treeSize];
	}
	public TreeParent(E element){
		this();
		nodes[0] = new Node<E>(element, -1);
		nodeNums ++;
	}
	@SuppressWarnings("unchecked")
	public TreeParent(E element, int initSize){
		treeSize = initSize;
		nodes = new Node[treeSize];
		nodes[0] = new Node<E>(element, -1);
		nodeNums ++;
	}
	
	
	//判断树是否为空
	public boolean isEmpty(){
		return nodes[0] == null;
	}
	//返回根节点
	public Node<E> root(){
		return nodes[0];
	}
	
	/**
	 * 为指定节点添加子节点
	 * @param element : 数据元素
	 * @param parent  ： 某节点（要添加子节点的节点）
	 */
	public void addNode(E element, Node<?> parent){
		//找到nodes数组中第一个为null的位置并将新的节点添加到该位置
		for(int i = 0; i < treeSize; i ++){
			if(nodes[i] == null){
				Node<E> newNode = new Node<E>(element, pos(parent));
				nodes[i] = newNode;
				nodeNums ++;
				return;
			}
		}
		throw new RuntimeException("该树已满，无法添加新节点！");
	}
	
	/**
	 * 返回指定节点的父节点
	 * @param node	：	某指定节点
	 * @return		：	返回指定节点的父节点
	 */
	public Node<E> parent(Node<?> node){
		return nodes[node.parent];
	}

	/**
	 * 返回指定节点（非叶子节点）的所有子节点
	 * @param node	：指定节点（非叶子节点）
	 * @return		：所有子节点
	 */
	public List<Node<E>> childen(Node<?> node){
		List<Node<E>> list = new ArrayList<Node<E>>();
		int indexParen = pos(node);
		for(int i = 0; i < treeSize; i ++){
			if(nodes[i] != null && nodes[i].parent == indexParen){
				list.add(nodes[i]);
			}
		}
		return list;
	}
	
	/**
	 * @see :deep of this tree
	 * @return	：返回该树的深度
	 */
	public int deep(){
		int max = 0;
		for(int i = 0; i < treeSize && nodes[i] != null; i ++){
			//初始化本节点的层次
			int def = 1;
			//
			int pindex = nodes[i].parent;
			while(pindex != -1 && nodes[pindex] != null){
				//
				pindex = nodes[pindex].parent;
				def ++;
			}
			
			if(max < def){
				max = def;
			}
		}
		return max;
	}
	/**
	 * 根据指定节点返回在节点数组中的索引位置
	 * @param parent	:	指定节点
	 * @return			：	返回指定在节点数组中的索引位置
	 */
	public int pos(Node<?> parent) {
		for(int i = 0; i < treeSize; i ++){
			if(parent == nodes[i]){
				return i;
			}
		}
		return -1;
	}
}

从上面的程序可以看出，定义树节点时增加了一个parent域。该parent域用于保存该节点的父节点在数组中的位置索引，通过这种方法即可记录树中节点之间的父子关系。使用这种父节点表示法来存储树时，添加节点时将新节点的parent域的值设为其父节点在数组中的索引即可。下面是测试代码：

import java.util.List;

import com.yc.tree.TreeParent;

public class TreeParentTest {
	public static void main(String[] args) {
		TreeParent<String> tree = new TreeParent<String>("root");
		System.out.println("此时树的深度为： " + tree.deep());
		System.out.println();
		
		TreeParent<String>.Node<String> root = tree.root();
		tree.addNode("节点1", root);
		tree.addNode("节点2", root);
		System.out.println("此时树的深度为： " + tree.deep());
		System.out.println();
		
		List<TreeParent<String>.Node<String>> list = tree.childen(root);
		System.out.println( "根节点的第一个子节点为：" + list.get(0));
		//为根节点的第一个子节点添加子节点
		tree.addNode("节点3", list.get(0));
		System.out.println( "此时树的深度为： " + tree.deep());
	}
}

测试结果为：

通过上面的介绍可以发现，父节点表示法的特点是，每个节点都记录了它的父节点以至于可以快速的找到其父节点，但如果要去找每个节点的所有子节点就比较麻烦，程序要遍历整个节点数组（尽管遍历很快？？）。