Java版的树

用java实现的树，

先定义一个树的接口，暂时只有两个基本方法，

package com.woxiaoe.collection.tree;

/**
 * 书接口
 * @author 小e
 *
 * 2010-4-8 下午08:04:09
 */
public interface Tree<T> extends Iterable<T>  {
	
	/**
	 * 深度
	 * @return
	 */
	public int depth();
	
	/**
	 * 叶子节点数
	 * @return
	 */
	public int leafCount();

}

 接着定义一个树节点针对二叉树

package com.woxiaoe.collection.tree;
/**
 * 树节点
 * @author 小e
 *
 * 2010-4-8 下午08:06:04
 */
public class Tnode<T>{
	
	private Tnode<T> left;
	private Tnode<T> right;
	private T value;
	
	public Tnode(T value) {
		this.value = value;
	}
	public Tnode(T value, Tnode<T> left, Tnode<T> right){
		this.value = value;
		this.left = left;
		this.right = right;
	}
	
	public Tnode<T> getLeft() {
		return left;
	}
	public void setLeft(Tnode<T> left) {
		this.left = left;
	}
	public Tnode<T> getRight() {
		return right;
	}
	public void setRight(Tnode<T> right) {
		this.right = right;
	}
	public T getValue() {
		return value;
	}
	public void setValue(T value) {
		this.value = value;
	}
}

 

二叉树

package com.woxiaoe.collection.tree;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * 二叉树
 * @author 小e
 *
 * 2010-4-8 下午08:04:53
 */
public class BinaryTree<T> implements Tree<T> {
	private Tnode<T> root;//根结点
	
	public BinaryTree() {
		root = null;
	}
	
	public BinaryTree(Tnode<T> root){
		this.root = root;
	}
	public Tnode<T> getRoot() {
		return root;
	}

	public void setRoot(Tnode<T> root) {
		this.root = root;
	}

	@Override
	public int depth() {
		return depth(root);
	}

	@Override
	public int leafCount() {
		return leafCount(root);
	}
	private int depth(Tnode<T> node) {
		if(node == null){
			return -1;
		}
		int leftHeight = depth(node.getLeft());
		int rightHeight = depth(node.getRight());
		return 1 + (leftHeight > rightHeight?leftHeight:rightHeight);
	}
	private int leafCount(Tnode<T> node){
		if(node.getLeft() == null && node.getLeft() == null){
			return 1;
		}
		return leafCount(node.getLeft()) + leafCount(node.getRight());
		
	}

	@Override
	public Iterator<T> iterator() {
		return new InorderIterator();
	}
	
	private class InorderIterator implements Iterator<T>{
		private Stack<Tnode<T>> s ;
		Tnode<T> curr;
		public InorderIterator() {
			s = new Stack<Tnode<T>>();
			curr = getFarLeft(root);
		}
		@Override
		public boolean hasNext() {
			return curr != null;
		}

		@Override
		public T next() {
			if(curr == null){
				throw new NoSuchElementException("没有节点");
			}
			T value = curr.getValue();
			if(curr.getRight() != null){
				curr = getFarLeft(curr.getRight());
			}else if(!s.isEmpty()){
				curr = s.pop();
			}else{
				curr = null;
			}
			
			return value;
		}

		@Override
		public void remove() {
			throw new RuntimeException("不支持该方法");
		}
		/**
		 * 得到右子树最远的有节点
		 * @return
		 */
		private Tnode<T> getFarLeft(Tnode<T> node){
			if(node == null){
				return null;
			}
			
			while(node.getLeft() != null){
				s.push(node);
				node = node.getLeft();
			}
			
			return node;
		}
		
	}
}

 

以下为测试代码

package com.woxiaoe.collection.tree;

import java.util.Iterator;

import junit.framework.TestCase;

public class TreeTest extends TestCase {
	BinaryTree tree = new BinaryTree();
	@Override
	protected void setUp() throws Exception {
		Tnode<String> root = new Tnode<String>("root");
		Tnode<String> a = new Tnode<String>("a");
		Tnode<String> b = new Tnode<String>("b");
		Tnode<String> c = new Tnode<String>("c");
		Tnode<String> d = new Tnode<String>("d");
		
		a.setLeft(b);
		a.setRight(c);
		
		root.setLeft(a);
		root.setRight(d);
		
		tree.setRoot(root);
	}
	public void testTree(){
		
		
		System.out.println("tree height:" + tree.depth());
		System.out.println("leaf node:" + tree.leafCount());
		
		System.out.println("先序排列");
		NLR(tree.getRoot());
		
		System.out.println("中序排列");
		LNR(tree.getRoot());
		
		System.out.println("后序排列");
		LRN(tree.getRoot());

		System.out.println("测试遍历");
		
		for (Iterator iterator = tree.iterator(); iterator.hasNext();) {
			String nodeValue = (String) iterator.next();
			System.out.print(nodeValue + " ");
		}
		
	}
	/**
	 * 先序排列
	 * @param node
	 */
	public void NLR(Tnode node){
		if(node == null){
			return;
		}
		visit(node);
		NLR(node.getLeft());
		NLR(node.getRight());
	}
	/**
	 * 中序排列
	 * @param node
	 */
	public void LNR(Tnode node){
		if(node == null){
			return;
		}
		LNR(node.getLeft());
		visit(node);
		LNR(node.getRight());
	}
	/**
	 * 后序排列
	 * @param node
	 */
	public void LRN(Tnode node){
		if(node == null){
			return;
		}
		LRN(node.getLeft());
		LRN(node.getRight());
		visit(node);
	}
	public void visit(Tnode node){
		System.out.println(node.getValue());
	}
	@SuppressWarnings("unchecked")
	public void testIterator(){
		for (Iterator iterator = tree.iterator(); iterator.hasNext();) {
			String str = (String) iterator.next();
			System.out.print(str + " ");
		}
	}
}

 Output

tree height:2

leaf node:3

先序排列

root

a

b

c

d

中序排列

b

a

c

root

d

后序排列

b

c

a

d

root

测试遍历

b a c root d b a c root d