Java基础复习笔记07数据结构-树的概述

1.       树的概念

如果线性表、栈、队列是线性结构（一维结构）的话，那么树就代表着一种非线性的、复杂的二维结构，何为线性结构、何为二维结构？就是1对1的一条直线，每个元素都是这条线上的节点、节点之间只知道1VS1的、前后关系。而二维结构就是一个面，1对N的一个面，这个面上的每一个元素都对应着多个此面上其他的元素。树就是指N个有父子关系的节点的有限集合。树仅仅只能有一个根节点。除了根节点，其他没有子节点的节点叫做叶子节点。树的遍历是最考究程序员算法的，因为后面的算法很多用到了一些概念，那先将树的有关概念解释一下。

节点的度：节点拥有的子树的个数

树的度：树中所有节点的度的最大值

节点的层次：从根节点开始算起，根的层次为1，其余节点层次为父节点层次+1。

树的深度：树中节点的最大层次值称为树的深度。

2.       树的基本操作：

树的操作有以下：为指定节点增加子节点、判断树是否为空、返回树的根节点、返回指定节点的父节点、返回指定节点的所有子节点集合、返回指定节点的第i个子节点、返回树的深度、返回指定节点的深度、返回指定节点的索引位置。

3.       树的使用场景

树形结构使用场景非常之多，抛开编程语言不说，就看身边的例子。大家windows的资源管理器、开发web系统的树形菜单、负载均衡的内核算法可以使用哈夫曼树来辅助实现、将要排序的数据用排序二叉树存储，查找的效率很快。

4.       树的记父节点实现

书上管其叫做父节点表示法，这个名称我觉得很容易让人产生不解，所以笔者管它叫做记父节点实现更好一些。它的算法的原理就是利用一个节点对象，该节点对象不仅记录了该节点的数据，还记录了此节点的父节点的位置。那么我们访问这个节点的时候，实际上父节点也能间接的获取到了。其实我们在做很多数据库设计的时候，遇到一个树形菜单基本上都是采用这种记父方式来实现的。其实很多的看似二维的结构，数据库记录，都可以提取出相应的一种图形化的模型。就像UML的类图关系就完全可以转化成关系型结构化数据库表模型，而数据库表结构也能提取出相应的领域模型一样。

主键	数据	父节点主键
0	根菜单	-1
1	子菜单1	0
2	子菜单2	0
3	子菜单11	1

上面的二维表结构可以描绘成以下结构

 算法如下：

package dateStructer.tree;

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

public class TreeParent<E> {

	/**
	 * 节点结构
	 */
	public class Node<T> {

		// 真正的数据域
		private E date;

		// 记录父节点的索引位置
		private int parentIndex;

		public Node() {

		}

		public Node(E date, int parentIndex) {
			this.date = date;
			this.parentIndex = parentIndex;
		}

		@Override
		public boolean equals(Object obj) {

			if (((Node) obj).date == this.date
					&& ((Node) obj).parentIndex == this.parentIndex)
				return true;

			return false;
		}

		@Override
		public int hashCode() {
			return super.hashCode();
		}

		@Override
		public String toString() {
			return (String) date;
		}
		
		

	}

	// 默认数组大小
	private final int DefSize = 150;

	// 记录节点个数
	private int nodeSize;

	// 父节点对象
	private Node<E>[] nodes;

	public TreeParent() {
		nodes = new Node[DefSize];
	}

	public TreeParent(E e) {
		nodes = new Node[DefSize];
		nodeSize++;
		nodes[0] = new Node(e, -1);
	}

	/**
	 * 为指定节点增加子节点
	 * 
	 * @param e
	 * @param parentNode
	 * @return
	 */
	public boolean addNodeByParent(E e, Node<E> parentNode) {
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] == null) {
				int parentNodeIndex = getNodeIndex(parentNode);
				nodes[i] = new Node<E>(e, parentNodeIndex);
				nodeSize++;
				return true;
			}
		}
		return false;
	}

	/**
	 * 根据node获得索引
	 * 
	 * @param node
	 * @return
	 */
	public int getNodeIndex(Node<E> node) {
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].equals(node)) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 判断是否是空树
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return nodeSize == 0;
	}

	/**
	 * 返回树的根节点
	 * 
	 * @return
	 */
	public Node<E> getRootNode() {

		if (nodeSize == 0) {
			return null;
		}
		return nodes[0];
	}

	/**
	 * 根据子节点返回父节点对象
	 * 
	 * @param chileNode
	 * @return
	 */
	public Node<E> getParentNodeByChildNode(Node<E> chileNode) {
		for (int i = 0; i < nodeSize; i++) {
			
			if(chileNode == null){
				return null;
			}
			
			if (i == chileNode.parentIndex) {
				return nodes[i];
			}
		}
		return null;
	}

	/**
	 * 根据父节点返回子节点对象集合
	 * 
	 * @param chileNode
	 * @return
	 */
	public Node<E> getParentNodeByChildNode(Node<E> chileNode) {
		if (chileNode == null) {
			return null;
		}
		return nodes[chileNode.parentIndex];
	}
	/**
	 * 返回指定节点的第index个子节点,第1个代表第一个
	 * 
	 * @param parentNode
	 * @param index
	 * @return
	 */
	public Node<E> getIndexChildByParentNode(Node<E> parentNode, int index) {

		if (index == 0) {
			throw new RuntimeException("没有第0个子节点，从1开始");
		}

		int childCount = 0;

		int parentIndex = getNodeIndex(parentNode);
		for (int i = 0; i < nodeSize; i++) {
			if (nodes[i].parentIndex == parentIndex) {
				++childCount;
				if (childCount == index) {
					return nodes[i];
				}
			}
		}
		return null;
	}

	/**
	 * 返回节点的深度
	 * 
	 * @return
	 */
	public int returnNodeDeep(Node<E> node) {
		if (node == getRootNode()) {
			return 1;
		} else {
			Node<E> parentNode = getParentNodeByChildNode(node);
			if(parentNode != null){
				return returnNodeDeep(parentNode) + 1;
			}
			return 0;
		}
	}

	/**
	 * 返回树的深度
	 * 
	 * @return
	 */
	public int returnTreeDeep() {
		int max = 0;
		for (int i = 0; i < nodeSize; i++) {
			int nodeDeep = returnNodeDeep(nodes[i]);
			if (max < nodeDeep) {
				max = nodeDeep;
			}
		}
		return max;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < nodeSize; i++) {

			str.append("[" + nodes[i].date + "],");

		}

		if (nodeSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 测试代码

public static void main(String[] args) {
	TreeParent<String> tree = new TreeParent<String>("根菜单");
	TreeParent<String>.Node<String> root = tree.getRootNode();
	tree.addNodeByParent("子菜单1", root);
	tree.addNodeByParent("子菜单2", root);
	TreeParent<String>.Node<String> node1 = tree.getIndexChildByParentNode(root, 1);
	tree.addNodeByParent("子菜单11", node1);
	System.out.println("树的数据："+tree);
	System.out.println("节点的深度："+tree.returnNodeDeep(node1));
	System.out.println("节点的深度："+tree.returnNodeDeep(root));
	TreeParent<String>.Node<String> node11 = tree.getIndexChildByParentNode(node1, 1);
	System.out.println("节点的深度："+tree.returnNodeDeep(node11));
	System.out.println("树的深度："+tree.returnTreeDeep());
}

 测试效果如下

树的数据：[[根菜单],[子菜单1],[子菜单2],[子菜单11]]
节点的深度：2
节点的深度：1
节点的深度：3
树的深度：3

 记父节点是让树的节点记住自己节点的父节点索引位置，可以根据索引查找父节点，查找某个节点的父节点自然是手到擒来了，但是查找某个节点的子节点就略显笨拙，得遍历整个树的存储数组。

5.       树的记子节点实现

与记父节点不同的是，记子节点实现是Node节点记录的是自己子节点的信息，之后利用第一个子节点记录第二个子节点信息、利用第二个子节点记录第三个字节点信息，以此类推。也就是说子节点对象就是记录父节点的子节点信息的。第n个节点记录了第n+1个子节点的信息。代码如下

package dateStructer.tree;

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

public class TreeChildren<E> {

	/**
	 * 记录子节点对象
	 * 
	 * @author liuyan
	 */
	class SonNode<E> {
		E data;
		int index;
		SonNode<E> sonNode;

		public SonNode(E data, int index, SonNode sonNode) {
			this.data = data;
			this.index = index;
			this.sonNode = sonNode;
		}

		@Override
		public String toString() {
			return (String) data;
		}
		
		public Node<E> paseNode(){
			return new Node<E>(data,index);
		}
	}

	/**
	 * 实际应用的Node对象
	 * 
	 * @author liuyan
	 */
	class Node<E> {
		E data;
		int index;
		SonNode firstSonNode;

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

		public Node(E data, int index, SonNode sonNode) {
			this.data = data;
			this.index = index;
			this.firstSonNode = sonNode;
		}

		@Override
		public boolean equals(Object obj) {

			if (((Node) obj).data == this.data
					&& ((Node) obj).index == this.index)
				return true;

			return false;
		}

		@Override
		public int hashCode() {
			return super.hashCode();
		}

		@Override
		public String toString() {
			return (String) data;
		}
	}

	// 默认数组大小
	private final int DefSize = 150;

	// 记录节点个数
	private int nodeSize;

	// 父节点对象
	private Node<E>[] nodes;

	public TreeChildren() {
		nodes = new Node[DefSize];
	}

	public TreeChildren(E e) {
		nodes = new Node[DefSize];
		nodeSize++;
		nodes[0] = new Node(e, 0);
	}

	/**
	 * 为指定节点增加子节点
	 * 
	 * @param e
	 * @param parentNode
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public boolean addNodeByParent(E e, Node<E> parentNode) {
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] == null) {

				SonNode sonNode = new SonNode(e, i, null);

				SonNode lastSonNode = getLastSonNodeByParent(parentNode);

				if (lastSonNode == null) {
					parentNode.firstSonNode = sonNode;
				} else {
					lastSonNode.sonNode = sonNode;
				}
				nodes[i] = sonNode.paseNode();
				nodeSize++;
				return true;
			}
		}
		return false;
	}

	/**
	 * 由SonNode到普通Node的转化
	 * @param sonNode
	 * @return
	 */
	public Node<E> paseNode(SonNode<E> sonNode) {
		for (int i = 0; i < nodeSize; i++) {
			if (nodes[i] != null && nodes[i].data == sonNode.data
					&& nodes[i].index == sonNode.index) {
				return nodes[i];
			}
		}
		return null;
	}

	/**
	 * 获得一个父节点的最后子节点对象
	 * 
	 * @param parentNode
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public SonNode getLastSonNodeByParent(Node<E> parentNode) {

		if (parentNode.firstSonNode == null) {
			return null;
		}

		SonNode sonNodeNow = parentNode.firstSonNode;
		while (sonNodeNow.sonNode != null) {
			sonNodeNow = sonNodeNow.sonNode;
		}
		return sonNodeNow;
	}

	/**
	 * 根据node获得索引
	 * 
	 * @param node
	 * @return
	 */
	public int getNodeIndex(Node<E> node) {
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].equals(node)) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 判断是否是空树
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return nodeSize == 0;
	}

	/**
	 * 返回树的根节点
	 * 
	 * @return
	 */
	public Node<E> getRootNode() {

		if (nodeSize == 0) {
			return null;
		}
		return nodes[0];
	}

	/**
	 * 根据子节点返回父节点对象
	 * 
	 * @param chileNode
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public Node<E> getParentNodeByChildNode(Node<E> chileNode) {

		for (int i = 0; i < nodes.length; i++) {

			if (nodes[i] != null && nodes[i].firstSonNode != null) {

				SonNode<E> sonNode = nodes[i].firstSonNode;

				while (sonNode != null) {
					if (sonNode.data == chileNode.data
							&& sonNode.index == chileNode.index) {

						return nodes[i];

					}
					sonNode = sonNode.sonNode;
				}

			}

		}
		return null;

	}

	/**
	 * 根据父节点返回父子节点对象集合
	 * 
	 * @param chileNode
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public List<SonNode<E>> getChildsNodeByParentNode(Node<E> parentNode) {
		if (parentNode == null) {
			return null;
		}

		SonNode<E> sonNodeNow = parentNode.firstSonNode;
		List<SonNode<E>> list = new ArrayList<SonNode<E>>();
		while (sonNodeNow.sonNode != null) {
			list.add(sonNodeNow);
			sonNodeNow = sonNodeNow.sonNode;
		}
		return list;
	}

	/**
	 * 返回指定节点的第index个子节点,第1个代表第一个
	 * 
	 * @param parentNode
	 * @param index
	 * @return
	 */
	public SonNode<E> getIndexChildByParentNode(Node<E> parentNode, int index) {

		if (index == 0) {
			throw new RuntimeException("没有第0个子节点，从1开始");
		}

		if (parentNode.firstSonNode == null) {
			return null;
		}

		int childCount = 0;

		SonNode<E> sonNode = parentNode.firstSonNode;

		while (sonNode != null) {
			childCount++;
			if (index == childCount) {
				return sonNode;
			}
			sonNode = sonNode.sonNode;
		}

		return null;
	}

	/**
	 * 返回节点的深度
	 * 
	 * @return
	 */
	public int returnNodeDeep(Node<E> node) {
		if (node == getRootNode()) {
			return 1;
		} else {
			Node<E> parentNode = getParentNodeByChildNode(node);
			if (parentNode != null) {
				return returnNodeDeep(parentNode) + 1;
			}
			return 0;
		}
	}

	/**
	 * 返回树的深度
	 * 
	 * @return
	 */
	public int returnTreeDeep() {
		int max = 0;
		for (int i = 0; i < nodeSize; i++) {
			int nodeDeep = returnNodeDeep(nodes[i]);
			if (max < nodeDeep) {
				max = nodeDeep;
			}
		}
		return max;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < nodeSize; i++) {

			str.append("[" + nodes[i].data + "],");

		}

		if (nodeSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 这个构想是找到某个节点的子节点比较容易，但是找到某个节点的父节点就相对麻烦一些了。所以使用记子节点还是记父节点，各有利弊。不同场合不同使用。

6.       总结

这次总结了一般树的一般组建内核，下次将对特殊的树二叉树进行学习。一般在程序里面使用树结构进行模型构建使用最多的还是记父节点方式，无论是Java还是JS特效树，都是采用此方式进行树构建的比较多，而记子节点方式相对于记父节点来说思维很不一样。如果一个菜单数据十分巨大，那么一个记子树形菜单所消耗的资源将是巨大的。对不起，因为笔者在本片复习小结中生了一场病。所以学习笔记有些松散，下不为例。祝大家多多锻炼、注意身体。身体真是本钱！身体差却是吃亏啊。