二叉検索ツリーの挿入アルゴリズム

2189 ワード

package com.pb.datastructure.find;

/**
 *           
 * @author Administrator
 */
public class BinarySortTree {
	private static BinarySortTree tree = new BinarySortTree();
	private Node root;//   
	public void add(int data){
		if(null==root){
			root=new Node(data,null,null);//       ,       
		}else{
			addTree(root,data);
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		createTree();//       
		System.out.println("    17");
		tree.add(17);
		tree.show();

	}
	/**
	 *     
	 * @param root
	 * @param data
	 */
	private void addTree(Node root,int data){
		if(root.data>data){
			if(root.left==null){
				root.left=new Node(data,null,null);//          ,        
			}else{
				addTree(root.left,data);
			}
		}else{
			if(root.right==null){
				root.right=new Node(data,null,null);//           ,        
			}else{
				addTree(root.right,data);
			}
		}
	}
	/**
	 *      
	 */
	public void show(){
		System.out.println("       :");
		showTree(root);
	}
	/**
	 *      
	 * @author Administrator
	 */
	public void showTree(Node node){
		if(node.left!=null){
			showTree(node.left);
		}
		System.out.println(node.data+" ");
		if(node.right!=null){
			showTree(node.right);
		}
	}
/**
 *        
 * @author Administrator
 *
 */
	public static void createTree(){
		tree.add(15);
		tree.add(12);
		tree.add(9);
		tree.add(14);
		tree.add(13);
		tree.add(19);
		tree.add(18);
		tree.add(22);
		tree.add(23);
		
	}
	class Node {
		int data;//        
		Node left;//        
		Node right;//        

		public Node(int data, Node left, Node right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}

}