本文共 3374 字，大约阅读时间需要 11 分钟。

上接前篇

4.3 树的基本算法

4.3.1 getSize()⎯⎯统计（子）树的规模

• 一棵树的规模，等于根节点下所有子树规模之和再加一，也等于根节点的后代总数。

该算法首先通过 firstChild 引用找出根节点的长子，并沿着 nextSibling 引用顺次找到其余的孩子，递归地统计出各子树的规模。最后，只要将所有子树的规模累加起来，再计入

4.3.2 getHeight()⎯⎯计算节点的高度

• 若 u 是 v 的孩子，则 height(v) ≥ height(u) + 1；
• height(v) = 1 + max height(u);

因此，算法 getHeight(v)也是首先通过 firstChild 引用找出根节点的长子，并沿着 nextSibling引用顺次找到其余的孩子，递归地计算出各子树的高度。最后，只要找出所有子树的最大高度，再计入根节点本身，就得到了根节点的高度（即树高）;getHeight(v)算法的运行时间也是 O(n)，

4.3.3 getDepth()⎯⎯计算节点的深度

• 若 u 是 v 的孩子，则 depth(u) = depth(v) + 1。
  算法 getDepth(v)将从 v 的父亲开始，沿着 parent 指针不断上移，直到深度为 0 的树根。
  由于该算法只需访问 v 的所有真祖先，而且在每个节点只需 O(1)时间，故其复杂度为O(depth(v))。

4.3.4 前序、后序遍历

最基本的树遍历算法⎯⎯前序遍历（ Preoder trave rsal）和后

算法： PreorderTraversal(v)输入：树节点v输出： v所有后代的前序遍历序列{
    	if (null != v) {
    		首先访问并输出v;		for (u = v.getFirstChild(); null != u; u = u.getNextSibling()) //依次		PreorderTraversal(u);//前序遍历v的各棵子树	}}

算法： PostorderTraversal(v)输入：树节点v输出： v所有后代的后序遍历序列{
    	if (null != v) {
    		for (u = v.getFirstChild(); null != u; u = u.getNextSibling()) //依次		PostorderTraversal(u);//后序遍历v的各棵子树		当所有后代都访问过后，最后才访问并输出节点v;	}}

4.3.5 层次遍历

在这种遍历中，各节点被访问的次序取决于它们各自的深度，其策略可以总结为“深度小的节点优先访问”。

算法： LevelorderTraversal(v)输入：树节点v输出： v所有后代的层次遍历序列{
    	if (null != v) {
    		创建一个队列Q;		Q.enqueue(v);//根节点入队		while (!Q.isEmpty()) {
    //在队列重新变空之前			u = Q.dequeue();//取出队列的首节点u			访问并输出u;			for (w = u.getFirstChild(); null != w; w = w.nextSibling())//依次将u的			Q.enqueue(w);//每个孩子w加至队列中		} //while	} //if}

4.3.6 树迭代器

/*** 基于列表实现的树迭代器*/public class IteratorTree implements Iterator {
    	private List list;//列表	private Position nextPosition;//当前（下一个）元素的位置	//默认构造方法    public IteratorTree() {
     list = null; }	//前序遍历	public void elementsPreorderIterator(TreeLinkedList T) {
    		if (null == T) return;//递归基		list.insertLast(T);//首先输出当前节点		TreeLinkedList subtree = T.getFirstChild();//从当前节点的长子开始		while (null != subtree) {
    //依次对当前节点的各个孩子			this.elementsPreorderIterator(subtree);//做前序遍历			subtree = subtree.getNextSibling();		}	}	//后序遍历	public void elementsPostorderIterator(TreeLinkedList T) {
    		if (null == T) return;//递归基		TreeLinkedList subtree = T.getFirstChild();//从当前节点的长子开始		while (null != subtree) {
    //依次对当前节点的各个孩子			this.elementsPostorderIterator(subtree);//做后序遍历			subtree = subtree.getNextSibling();		}		list.insertLast(T);//当所有后代都访问过后，最后才访问当前节点	}	//层次遍历	public void levelTraversalIterator(TreeLinkedList T) {
    		if (null == T) return;		Queue_List Q = new Queue_List();//空队		Q.enqueue(T);//根节点入队		while (!Q.isEmpty()) {
    //在队列重新变空之前		TreeLinkedList tree = (TreeLinkedList) (Q.dequeue());//取出队列首节点		list.insertLast(tree);//将新出队的节点接入迭代器中		TreeLinkedList subtree = tree.getFirstChild();//从tree的第一个孩子起			while (null != subtree) {
    //依次找出所有孩子，并			Q.enqueue(subtree);//将其加至队列中			subtree = subtree.getNextSibling();			}		}	}	//检查迭代器中是否还有剩余的元素	public boolean hasNext() {
     return (null != nextPosition); }	//返回迭代器中的下一元素	public Object getNext() throws ExceptionNoSuchElement {
    		if (!hasNext()) throw new ExceptionNoSuchElement("No next position");		Position currentPosition = nextPosition;		if (currentPosition == list.last())//若已到达尾元素，则		nextPosition = null;//不再有下一元素		else//否则		nextPosition = list.getNext(currentPosition);//转向下一元素		return currentPosition.getElem();	}}

树的前序、后序及层次遍历，均可在 O(n)时间内完成，其中 n 为树本身的规模。

来源于:Java数据结构,邓俊辉