用java实现二叉排序树

Love The Way You Lie 2021-09-15 00:32 248阅读 0赞

二叉排序树又叫二叉查找树。它或者是一棵空树，或者是具有下列性质：

> 1）、如果左子树不为空，那么左子树所有节点的值均小于它的根节点的值。
> 
> 2）、如果右子树不为空，那么右子树所有节点的值均大于它的根节点的值
> 
> 3）、左、右子树也分别是二叉排序树。
> 
>   
>

下面是二叉排序树的实现代码：该 算法实现了二叉树的构建、插入节点和对树的遍历。

//实现二叉排序树
    public class BinarySortTree {
    	public static void main(String[] args) {
    		BinaryTree biTree=new BinaryTree();
    		int[] data={2,8,7,4,9,3,1,6,7,5};
    		biTree.buildTree(data);
    		System.out.println("二叉树的中序遍历:");
    		biTree.inOrder();
    		System.out.println();
    		System.out.println("二叉树的先序遍历:");
    		biTree.preOrder();
    		System.out.println();
    		System.out.println("二叉树的后序遍历:");
    		biTree.postOrder();
    		System.out.println();
    	}
    
    }
    class Node{
    	public int data;
    	public Node left;
    	public Node right;
    	public Node(int val){
    		this.data=val;
    		this.left=null;
    		this.right=null;
    	}
    }
    
    class BinaryTree{
    	private Node root;
    	public BinaryTree(){
    		root=null;
    	}
    	//将data插入到二叉排序树中
    	public void insert(int data){
    		Node newNode=new Node(data);
    		if(root==null){
    			root=newNode;
    		}else{
    			Node current=root;
    			Node parent;
    			while(true){//寻找插入的位置
    				parent=current;
    				if(data<current.data){
    					current=current.left;
    					if(current==null){
    						parent.left=newNode;
    						return;
    					}
    				}else{
    					current=current.right;
    					if(current==null){
    						parent.right=newNode;
    						return;
    					}
    				}
    			}
    		}
    	}
    	
    	//将数值输入构建二叉树
    	public void buildTree(int[] data){
    		for(int i=0;i<data.length;i++){
    			insert(data[i]);
    		}
    	}
    	
    	//中序遍历方法递归实现
    	public void inOrder(Node localRoot){
    		if(localRoot!=null){
    			inOrder(localRoot.left);
    			System.out.print(localRoot.data+" ");
    			inOrder(localRoot.right);
    		}
    	}
    	public void inOrder(){
    		this.inOrder(this.root);
    	}
    	
    	//先序遍历方法递归实现
    	public void preOrder(Node localRoot){
    		if(localRoot!=null){
    			System.out.print(localRoot.data+" ");
    			preOrder(localRoot.left);
    			preOrder(localRoot.right);
    		}
    	}
    	public void preOrder(){
    		this.inOrder(this.root);
    	}
    	
    	//后序遍历方法递归实现
    	public void postOrder(Node localRoot){
    		if(localRoot!=null){
    			postOrder(localRoot.left);
    			postOrder(localRoot.right);
    			System.out.print(localRoot.data+" ");
    		}
    	}
    	public void postOrder(){
    		this.postOrder(this.root);
    	}
    }

运行结果为：

> 二叉树的中序遍历:
> 
> 1 2 3 4 5 6 7 7 8 9 
> 
> 二叉树的先序遍历:
> 
> 1 2 3 4 5 6 7 7 8 9 
> 
> 二叉树的后序遍历:
> 
> 1 3 5 6 4 7 7 9 8 2