treetest.java.bak

一份自己实现的一些java的数据结构

import java.util.*;
/**
 * 二叉树结构设计
 * 以整型为例来设计，如有必要可以更改
 */
class TreeNode {
    
    TreeNode left;//做指针
    TreeNode right;//有指针
    int keyWord;//关键码
    
    public TreeNode(TreeNode left,TreeNode right,int keyWord){
        this.keyWord = keyWord;
        this.left = left;
        this.right = right;    
    }    
    
    public TreeNode(int keyWord){
        this.keyWord = keyWord;
        this.left = null;
        this.right = null;    
    }
    
    public void setLeft(TreeNode left){
        this.left = left;    
    }
    
    public void setRight(TreeNode right){
        this.right = right;    
    }
}

/**
 * 对于二叉树中，构造，查找，遍历操作的实现
 */
public class TreeTest {
    /**
     * 构造一颗二叉树
     * @param count 一个整型的一纬数组
     */
    public TreeNode createTree(int[] count){
        TreeNode tree = null;
        TreeNode q = null;
        for(int i=0;i<count.length;i++){
            if(tree == null)
                tree = q = new TreeNode(count[i]);        
            else{
     			q = tree;
     			while(q.keyWord != count[i]){
     				if(count[i] > q.keyWord){
     					if(q.right != null)	
     						q = q.right;
     					else
     						q.setRight(new TreeNode(count[i]));	
     				}else{
     					if(q.left != null)
     						q = q.left;
     					else
     						q.setLeft(new TreeNode(count[i]));	
     				}	
     			}    
            }
        }//end for
        return tree;
    }
    /**
     * 二叉树的中序遍历
     */
    public void search(TreeNode node){
    	if(node == null){
    		System.out.println("this tree is null,please create first");
    		return;	
    	}
    	System.out.println(node.keyWord);
    	if(node.left != null)
    		search(node.left);
    	if(node.right != null)
    		search(node.right);	
    }//end function search
    /**
     * 二叉树的前序遍历
     */ 
    public void searchLeft(TreeNode node){
    	if(node == null){
    		System.out.println("this tree is null,please create first");
    		return;	    			
    	}
    	if(node.left != null)
    		searchLeft(node.left);
    	System.out.println(node.keyWord);
    	if(node.right != null)
    		searchLeft(node.right);	
    }
     /**
      * 二叉树的后序遍历
      */ 
    public void searchRight(TreeNode node){
    	if(node == null){
    		System.out.println("this tree is null,please create first");
    		return;	    			
    	}
    	if(node.right != null)
    		searchRight(node.right);	
    	System.out.println(node.keyWord);
    	if(node.left != null)
    		searchRight(node.left);	
    }
     /**
      * 二叉树的查找
      */ 
    public int find(TreeNode node,int count){
    	while(node != null){
    		int find = node.keyWord;//这样避免空指针异常
    		if(find == count){
    			return count;	
    		}
    		if(find > count){
    			node = node.left;	
    		}
    		if(find < count){
    			node = node.right;	
    		}	
    	}
    	return -1;		
    }
    
    public static void main(String[] args){
        TreeTest test = new TreeTest();
        int[] ag = {2,1,4,6,3,8,7};
        TreeNode node = test.createTree(ag);
        test.search(node);
        
        System.out.println("search left");
        test.searchLeft(node);
        System.out.println("search right");
        test.searchRight(node);
        
        //find the count
        int count = test.find(node,0);
        if(count != -1)
        	System.out.println("find the count is : " + count);
        else{
        	System.out.println("can not find the count");	
        }
    }
}