Javaのデータ構造(3)----強力なツリー


単純なソートツリー
package com.wz.util.tree;

import java.util.ArrayList;
import java.util.Iterator;

/**
 *      
 * 
 * @author NumbCoder
 * 
 */
//   
class BinaryNode {
	private int data;
	BinaryNode lChild;
	BinaryNode rChild;

	BinaryNode(int t) {
		setData(t);
		lChild = null;
		rChild = null;
	}

	//        
	public boolean isLeaf() {
		if (lChild == null && rChild == null)
			return true;
		else
			return false;
	}

	public void setData(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}
}

//  
public class BinaryTree {
	private BinaryNode root;

	BinaryTree(BinaryNode root) {
		this.root = root;
		root.lChild = null;
		root.rChild = null;
	}

	//            
	public void insert(BinaryNode n) {
		//     
		if (root == null)
			root = n;
		else {
			BinaryNode current = root;
			BinaryNode parentNode;
			boolean flag = true;
			while (flag) {
				parentNode = current;
				if (n.getData() > current.getData()) {
					//             
					current = current.rChild;
					if (current == null) {
						parentNode.rChild = n;
						flag = false;
					}
				} else if (n.getData() < current.getData()) {
					current = current.lChild;
					//             
					if (current == null) {
						parentNode.lChild = n;
						flag = false;
					}
				}
			}
		}
	}

	//          ArrayList             
	public void creatBinaryTree(BinaryNode root, ArrayList<BinaryNode> aList) {
		Iterator<BinaryNode> it = aList.iterator();
		while (it.hasNext()) {
			insert(it.next());
		}
	}

	//     
	public void preOrder(BinaryNode t) {
		if (t != null) {
			System.out.println(t.getData());
			preOrder(t.lChild);
			preOrder(t.rChild);
		}
	}

	//     
	public void inOrder(BinaryNode t) {
		if (t != null) {
			inOrder(t.lChild);
			System.out.println(t.getData());
			inOrder(t.rChild);
		}
	}

	//     
	public void postOrder(BinaryNode t) {
		if (t != null) {
			postOrder(t.lChild);
			postOrder(t.rChild);
			System.out.println(t.getData());
		}
	}

}

 汎用的なソートツリー(ソートされるため、ノードは比較可能である必要がありますが、具体的な比較ルールは自分で決めます)
package com.wz.util;

import java.util.ArrayList;
import java.util.Iterator;

/**
 *          
 * 
 * @author NumbCoder
 * 
 */

 
  class BinaryNode<T> implements Comparable<T>  {
	private T data;
	BinaryNode<T> lChild;
	BinaryNode<T> rChild;

	BinaryNode(T t) {
		setData(t);
		lChild = null;
		rChild = null;
	}

	/**
	 *   T            、     n     -1、0 1 
	 *       compareTo  
	 */
	@Override
	public int compareTo(T t) {
		
			return 0;
	}
	public void setData(T data) {
		this.data = data;
	}

	public T getData() {
		return data;
	}
//       
	public boolean isLeaf() {
		if (lChild == null && rChild == null)
			return true;
		else
			return false;
	}

	

	
}
// 
public class BinaryTree<T> {
	private BinaryNode<T> root;

	BinaryTree(BinaryNode<T> root) {
		this.root = root;
		root.lChild = null;
		root.rChild = null;
	}

	//            
	public void insert(BinaryNode<T> n) {
		//     
		if (root == null)
			root = n;
		else {
			BinaryNode<T> current = root;
			BinaryNode<T> parentNode;
			boolean flag = true;
			while (flag) {
				parentNode = current;
				if (n.compareTo(current.getData()) == 1) {
					//             
					current = current.rChild;
					if (current == null) {
						parentNode.rChild = n;
						flag = false;
					}
				} else if( n.compareTo(current.getData()) == -1){
					current = current.lChild;
					//             
					if (current == null) {
						parentNode.lChild = n;
						flag = false;
					}
				}
			}
		}
	}

	//          
	public void creatBinaryTree(BinaryNode<T> root,
			ArrayList<BinaryNode<T>> aList) {
		Iterator<BinaryNode<T>> it = aList.iterator();
		while (it.hasNext()) {
			insert(it.next());
		}
	}

	//     
	private void preOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			list.add(t.getData());
			preOrder(t.lChild, list);
			preOrder(t.rChild, list);
		}
	}

	public Iterator<T> itPreOrder() {
		ArrayList<T> list = new ArrayList<T>();
		preOrder(root, list);
		return list.iterator();
	}

	//     
	private void inOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			inOrder(t.lChild, list);
			list.add(t.getData());
			inOrder(t.rChild, list);
		}
	}

	public Iterator<T> itInOrder() {
		ArrayList<T> list = new ArrayList<T>();
		inOrder(root, list);
		return list.iterator();
	}

	//     
	private void postOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			postOrder(t.lChild, list);
			postOrder(t.rChild, list);
			list.add(t.getData());
		}
	}

	public Iterator<T> itPostOrder() {
		ArrayList<T> list = new ArrayList<T>();
		postOrder(root, list);
		return list.iterator();
	}
}