樹的遍歷
之前的工作都沒有接觸到樹，也就很少研究它。幸運(yùn)地的是，在目前的工作中多次遇到樹型結(jié)構(gòu)的數(shù)據(jù)，那么訪問樹節(jié)點(diǎn)中的數(shù)據(jù)就是必然的了，而且還需要按照指定規(guī)則對節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行額外處理。經(jīng)過學(xué)習(xí)之后，對與樹相關(guān)的基本算法有了一些認(rèn)知，就計(jì)劃寫幾篇小文。其實(shí)這樣的文章早已是汗牛充棟，而我只是把它當(dāng)作我的學(xué)習(xí)總結(jié)罷了，以加深記憶與理解，如能對其他朋友有所助益，則更感愉悅了 :-) (2009.04.03最后更新)
這次先從最基礎(chǔ)的開始--樹的遍歷。本文使用了兩種極常用的方法來遍歷樹中的所有節(jié)點(diǎn)--遞歸；迭代，但它們實(shí)現(xiàn)的都是深度優(yōu)先(Depth-First)算法。
1. 樹節(jié)點(diǎn)與數(shù)據(jù)
先定義樹節(jié)點(diǎn)及數(shù)據(jù)(用戶對象)，并創(chuàng)建測試用的數(shù)據(jù)。
TreeNode是樹節(jié)點(diǎn)的定義。
/**
* 樹節(jié)點(diǎn)的定義。
*/
public interface TreeNode {
/**
* 獲取指定下標(biāo)處的子節(jié)點(diǎn)。
*
* @param index
* 下標(biāo)。
* @return 子節(jié)點(diǎn)。
*/
public TreeNode getChildAt(int index);
/**
* 返回指定子節(jié)點(diǎn)的下標(biāo)。
*
* @param index
* 下標(biāo)。
* @return 子節(jié)點(diǎn)。
*/
public int getChildIndex(TreeNode index);
/**
* 獲取子節(jié)點(diǎn)的數(shù)量。
*
* @return 子節(jié)點(diǎn)的數(shù)量。
*/
public int getChildCount();
/**
* 返回父節(jié)點(diǎn)。
*
* @return 父節(jié)點(diǎn)。
*/
public TreeNode getParent();
/**
* 設(shè)置父節(jié)點(diǎn)。注：此處不需要改變父節(jié)點(diǎn)中的子節(jié)點(diǎn)元素。
*
* @param parent
* 父節(jié)點(diǎn)。
*/
public void setParent(TreeNode parent);
/**
* 獲取所有的子節(jié)點(diǎn)。
*
* @return 子節(jié)點(diǎn)的集合。
*/
public List<?> getChildren();
/**
* 是否為葉節(jié)點(diǎn)。
*
* @return 是葉節(jié)點(diǎn)，返回true；否則，返回false。
*/
public boolean isLeaf();
}
GenericTreeNode是一個(gè)通用的樹節(jié)點(diǎn)實(shí)現(xiàn)。
public class GenericTreeNode<T> implements TreeNode {
private T userObject = null;
private TreeNode parent = null;
private List<GenericTreeNode<T>> children = new ArrayList<GenericTreeNode<T>>();
public GenericTreeNode(T userObject) {
this.userObject = userObject;
}
public GenericTreeNode() {
this(null);
}
/**
* 添加子節(jié)點(diǎn)。
*
* @param child
*/
public void addChild(GenericTreeNode<T> child) {
children.add(child);
child.setParent(this);
}
/**
* 刪除指定的子節(jié)點(diǎn)。
*
* @param child
* 子節(jié)點(diǎn)。
*/
public void removeChild(TreeNode child) {
removeChildAt(getChildIndex(child));
}
/**
* 刪除指定下標(biāo)處的子節(jié)點(diǎn)。
*
* @param index
* 下標(biāo)。
*/
public void removeChildAt(int index) {
TreeNode child = getChildAt(index);
children.remove(index);
child.setParent(null);
}
public TreeNode getChildAt(int index) {
return children.get(index);
}
public int getChildCount() {
return children.size();
}
public int getChildIndex(TreeNode child) {
return children.indexOf(child);
}
public List<GenericTreeNode<T>> getChildren() {
return Collections.unmodifiableList(children);
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getParent() {
return parent;
}
/**
* 是否為根節(jié)點(diǎn)。
*
* @return 是根節(jié)點(diǎn)，返回true；否則，返回false。
*/
public boolean isRoot() {
return getParent() == null;
}
public boolean isLeaf() {
return getChildCount() == 0;
}
/**
* 判斷指定的節(jié)點(diǎn)是否為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。
*
* @param node
* 節(jié)點(diǎn)。
* @return 是當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，返回true；否則，返回false。
*/
public boolean isChild(TreeNode node) {
boolean result;
if (node == null) {
result = false;
} else {
if (getChildCount() == 0) {
result = false;
} else {
result = (node.getParent() == this);
}
}
return result;
}
public T getUserObject() {
return userObject;
}
public void setUserObject(T userObject) {
this.userObject = userObject;
}
@Override
public String toString() {
return userObject == null ? "" : userObject.toString();
}
}
UserObject是節(jié)點(diǎn)上的用戶對象，相當(dāng)于是數(shù)據(jù)。
public class UserObject {
private String name = null;
private Integer value = Integer.valueOf(0);
public UserObject() {
}
public UserObject(String code, Integer value) {
this.name = code;
this.value = value;
}
public String getName() {
return name;
}
public void setName(String code) {
this.name = code;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append("[name=").append(name).append(", value=").append(value).append("]");
return result.toString();
}
}
TreeUtils是用于創(chuàng)建樹的工具類。
public class TreeUtils {
public static GenericTreeNode<UserObject> buildTree() {
GenericTreeNode<UserObject> root = new GenericTreeNode<UserObject>();
root.setUserObject(new UserObject("ROOT", Integer.valueOf(0)));
GenericTreeNode<UserObject> node1 = new GenericTreeNode<UserObject>();
node1.setUserObject(new UserObject("1", Integer.valueOf(0)));
GenericTreeNode<UserObject> node2 = new GenericTreeNode<UserObject>();
node2.setUserObject(new UserObject("2", Integer.valueOf(0)));
GenericTreeNode<UserObject> node3 = new GenericTreeNode<UserObject>();
node3.setUserObject(new UserObject("3", Integer.valueOf(5)));
root.addChild(node1);
root.addChild(node2);
root.addChild(node3);
GenericTreeNode<UserObject> node11 = new GenericTreeNode<UserObject>();
node11.setUserObject(new UserObject("11", Integer.valueOf(0)));
GenericTreeNode<UserObject> node21 = new GenericTreeNode<UserObject>();
node21.setUserObject(new UserObject("21", Integer.valueOf(0)));
node1.addChild(node11);
node2.addChild(node21);
GenericTreeNode<UserObject> node111 = new GenericTreeNode<UserObject>();
node111.setUserObject(new UserObject("111", Integer.valueOf(3)));
GenericTreeNode<UserObject> node112 = new GenericTreeNode<UserObject>();
node112.setUserObject(new UserObject("112", Integer.valueOf(9)));
GenericTreeNode<UserObject> node211 = new GenericTreeNode<UserObject>();
node211.setUserObject(new UserObject("211", Integer.valueOf(6)));
GenericTreeNode<UserObject> node212 = new GenericTreeNode<UserObject>();
node212.setUserObject(new UserObject("212", Integer.valueOf(3)));
node11.addChild(node111);
node11.addChild(node112);
node21.addChild(node211);
node21.addChild(node212);
return root;
}
}
2. 遞歸法
使用遞歸法的最大好處就是--簡單，但一般地，我們都認(rèn)為遞歸的效率不高。
private static void recursiveTravel(GenericTreeNode<UserObject> node) {
travelNode(node); // 訪問節(jié)點(diǎn)，僅僅只是打印該節(jié)點(diǎn)罷了。
List<GenericTreeNode<UserObject>> children = node.getChildren();
for (int i = 0; i < children.size(); i++) {
recursiveTravel(children.get(i)); // 遞歸地訪問當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)。
}
}
大家肯定知道，系統(tǒng)在執(zhí)行遞歸方法(對于其它方法也是如此)時(shí)是使用運(yùn)行時(shí)棧。對方法的每一次調(diào)用，在棧中都會(huì)創(chuàng)建一份此次調(diào)用的活動(dòng)記錄--包括方法的參數(shù)，局部變量，返回地址，動(dòng)態(tài)鏈接庫，返回值等。
既然系統(tǒng)能夠隱式地使用棧去執(zhí)行遞歸方法，那么我們就可以顯式地使用棧來執(zhí)行上述遞歸程序，這也是將遞歸程序轉(zhuǎn)化為迭代程序的常用思想。下面的iterativeTravel方法就運(yùn)用了這一思想。
3. 迭代法
private static void iterativeTravel(GenericTreeNode<UserObject> node) {
Stack<GenericTreeNode<UserObject>> nodes = new Stack<GenericTreeNode<UserObject>>();
nodes.push(node); // 將當(dāng)前節(jié)點(diǎn)壓入棧中。
while (!nodes.isEmpty()) {
GenericTreeNode<UserObject> bufNode = nodes.pop(); // 從棧中取出一個(gè)節(jié)點(diǎn)。
travelNode(bufNode); // 訪問節(jié)點(diǎn)。
if (!bufNode.isLeaf()) { // 如果該節(jié)點(diǎn)為分枝節(jié)點(diǎn)，則將它的子節(jié)點(diǎn)全部加入棧中。
nodes.addAll(bufNode.getChildren());
}
}
}
與遞歸法相比，迭代法的代碼略多了幾行，但仍然很簡單。
4. 小結(jié)
由于上述兩種方法均(隱式或顯式地)使用了運(yùn)行棧，所以此處的迭代法并不能提高整個(gè)程序的效率。相反地，由于在應(yīng)用程序中顯式地使用棧(java.util.Stack)，iterativeTravel方法的效率可能反而更低。但iterativeTravel的最大好處是，能夠有效地避免運(yùn)行時(shí)棧溢出(java.lang.StackOverflowError)。
如果樹的層次不太深，每層的子節(jié)點(diǎn)數(shù)不太多，那么使用遞歸法應(yīng)該是沒有問題的。畢竟，簡潔地程序會(huì)提供更多的好處。