java 多叉树的遍历

接上一篇，昨天一朋友问我java中怎么实现多叉树的遍历，想了半天都没想出来，写了二叉的遍历之后，发现多叉也一样的，而且java提供的容器类很方便，比c语言里处理指针方便多了。
我手工构造了一颗多叉树。然后再递归遍历。类似于中序遍历吧。
树的节点类:

package TestTwo;

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

//多叉树的节点
public class ManyTreeNode {
	
	//节点的内容
	private NodeBean  data ;
	//节点列表
	private List<ManyTreeNode> childList;
	
	//构造函数
	public ManyTreeNode(){
		data = new NodeBean();
		childList = new ArrayList<ManyTreeNode>();
	}
	
	//构造函数 可以指定key的值
	public ManyTreeNode(int key){
		data = new NodeBean();
		data.setKey(key);
		childList = new ArrayList<ManyTreeNode>();
	}
		
}

多叉树类：

package TestTwo;

//多叉树
public class ManyNodeTree {
	
	//树根
	private ManyTreeNode root;
	
	//构造函数
	public ManyNodeTree(){
		root = new ManyTreeNode();
		root.getData().setNodeName("root");
	}
	
	//构造函数
	public ManyNodeTree(int key){
		root = new ManyTreeNode();
		root.getData().setKey(key);
		root.getData().setNodeName("root");
	}
	
	
	//遍历多叉树
	public String iteratorTree(ManyTreeNode treeNode){
		
		StringBuilder sb = new StringBuilder();
		
		if (treeNode != null) {
			
			if ("root".equals(treeNode.getData().getNodeName())) {
				sb.append(treeNode.getData().getKey() + ",");
			}
			
			for (ManyTreeNode index : treeNode.getChildList()) {
				
				sb.append(index.getData().getKey() + ",");
				
				if (index.getChildList() != null && index.getChildList().size() > 0 ) {
					
					sb.append(iteratorTree(index));
					
				}
			}
		}
		
		return sb.toString();
	}
	
	
	//构造多叉树
	public static ManyNodeTree createTree(){
		
		//用构造函数指定根节点的值
		ManyNodeTree tree = new ManyNodeTree(60);
		
		//第一层的节点
		ManyTreeNode node1 = new ManyTreeNode(40);
		ManyTreeNode node2 = new ManyTreeNode(50);
		ManyTreeNode node3 = new ManyTreeNode(30);
		
		tree.getRoot().getChildList().add(0, node1);
		tree.getRoot().getChildList().add(1, node2);
		tree.getRoot().getChildList().add(2, node3);
		
		//第二层的节点
		ManyTreeNode node21 = new ManyTreeNode(85);
		ManyTreeNode node22 = new ManyTreeNode(70);
		ManyTreeNode node23 = new ManyTreeNode(15);
		ManyTreeNode node24 = new ManyTreeNode(102);
		ManyTreeNode node25 = new ManyTreeNode(83);
		ManyTreeNode node26 = new ManyTreeNode(9);
		
		tree.getRoot().getChildList().get(0).getChildList().add(0,node21);
		tree.getRoot().getChildList().get(0).getChildList().add(1,node22);
		tree.getRoot().getChildList().get(0).getChildList().add(2,node23);
		
		tree.getRoot().getChildList().get(1).getChildList().add(0,node24);
		tree.getRoot().getChildList().get(1).getChildList().add(1,node25);
		
		tree.getRoot().getChildList().get(2).getChildList().add(0,node26);
		
		//第二层的节点
		ManyTreeNode node31 = new ManyTreeNode(15);
		ManyTreeNode node32 = new ManyTreeNode(20);
		ManyTreeNode node33 = new ManyTreeNode(100);
		ManyTreeNode node44 = new ManyTreeNode(60);
		
		tree.getRoot().getChildList().get(0).getChildList().get(0).getChildList().add(0,node31);
		tree.getRoot().getChildList().get(0).getChildList().get(0).getChildList().add(1,node32);
		tree.getRoot().getChildList().get(0).getChildList().get(0).getChildList().add(2,node33);
		
		tree.getRoot().getChildList().get(0).getChildList().get(2).getChildList().add(0,node44);
		
		return tree;
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ManyNodeTree testTree = ManyNodeTree.createTree();
		String result = testTree.iteratorTree(testTree.getRoot());
		System.out.println(result);
	}

}

NodeBean类

public class NodeBean {
	
	private int key;
	private String nodeName;

	public String getNodeName() {
		return nodeName;
	}

	public void setNodeName(String nodeName) {
		this.nodeName = nodeName;
	}

	public int getKey() {
		return key;
	}

	public void setKey(int key) {
		this.key = key;
	}
}

省略了get，set方法。
图传上去不怎么清楚。
遍历的结果：60,40,85,15,20,100,70,15,60,50,102,83,30,9,

评论

4 楼 elan1986 2012-01-17  

很不错，谢谢了！

3 楼 guanque 2010-11-16  

能把多叉树遍历的完整代码发一下吗

2 楼 guanque 2010-11-16  

能把get和set方法也提供出来吗

1 楼 yangguo 2010-07-27  

不错，这个应该是先序遍历。