Java实现二叉树排序

布满荆棘的人生 2022-06-09 06:50 167阅读 0赞

这是我以前写的一个关于二叉树排序的Java实现，对以后面试应该会有用，先保存起来。  
二叉树原形：  
![这里写图片描述][Image 1]

先定义节点类，data为该节点的数据，lchild和rchild分别为该节点的左右分支：

package com.lin.tree;
    /** 
     * @author 作者 林尤庆
     * @version 创建时间：2016-8-11 下午02:46:52 
     * 类说明 :
     */
    public class Node {
    	
    	private char data;
    	private Node lchild;
    	private Node rchild;
    	
    	public Node() {
    		
    	}
    
    	public char getData() {
    		return data;
    	}
    
    	public void setData(char data) {
    		this.data = data;
    	}
    
    	public Node getLchild() {
    		return lchild;
    	}
    
    	public void setLchild(Node lchild) {
    		this.lchild = lchild;
    	}
    
    	public Node getRchild() {
    		return rchild;
    	}
    
    	public void setRchild(Node rchild) {
    		this.rchild = rchild;
    	}
    
    	public Node(char data, Node lchild, Node rchild) {
    		super();
    		this.data = data;
    		this.lchild = lchild;
    		this.rchild = rchild;
    	}
    
    	@Override
    	public String toString() {
    		return " " + getData() ;
    	}
    	
    	
    }

Tree类：

package com.lin.tree;
    /** 
     * @author 作者 林尤庆
     * @version 创建时间：2016-8-11 下午02:50:03 
     * 类说明 :
     */
    public class Tree {
    	
    	public Node createTree(String exp){
    		Node[] nodes=new Node[3];
    		Node b,p=null;
    		int top=-1,k=0,j=0;
    		char[] exps=exp.toCharArray();
    		char data=exps[j];
    		b=null;
    		while(j<exps.length-1){
    			switch (data) {
    			case '(':
    				top++;
    				nodes[top]=p;
    				k=1;
    				break;
    			case ')':
    				top--;
    				break;
    			case ',':
    				k=2;
    				break;
    			default:
    				p=new Node(data, null, null);
    				if(b==null){
    					b=p;
    				}else{
    					switch (k) {
    					case 1:
    						nodes[top].setLchild(p);
    						break;
    					case 2:
    						nodes[top].setRchild(p);
    						break;
    					}
    				}
    			}
    			j++;
    			data=exps[j];
    		}
    		return b;
    	}
    	
    	/**
    	 * pre order recursive
    	 *@author: 林尤庆
    	 *@date：2016-8-11
    	 *@param 
    	 *@param 
    	 */
    	public void PreOrder(Node node){
    		if(node==null){
    			return;
    		}else{
    			System.out.print(node.getData()+" ");
    			PreOrder(node.getLchild());
    			PreOrder(node.getRchild());
    		}
    	}
    	
    	/**
    	 *in order recursive
    	 *@author: 林尤庆
    	 *@date：2016-8-11
    	 *@param 
    	 *@param 
    	 */
    	public void InOrder(Node node){
    		if(node==null){
    			return;
    		}else{
    			InOrder(node.getLchild());
    			System.out.print(node.getData()+" ");
    			InOrder(node.getRchild());
    		}
    	}
    	
    	/**
    	 *post order recursive 
    	 *@author: 林尤庆
    	 *@date：2016-8-11
    	 *@param 
    	 *@param 
    	 */
    	public void PostOrder(Node node){
    		if(node==null){
    			return;
    		}else{
    			PostOrder(node.getLchild());
    			PostOrder(node.getRchild());
    			System.out.print(node.getData()+" ");
    		}
    	}
    	
    	
    }

测试类：

package com.lin.tree;
    /** 
     * @author 作者 林尤庆
     * @version 创建时间：2016-8-11 下午03:14:18 
     * 类说明 :
     */
    public class Test {
    
    	public static void main(String[] args) {
    		String str="A(B(D(,G)),C(E,F))";
    		Tree tree=new Tree();
    		Node node=tree.createTree(str);
    		System.out.println("先序：");
    		tree.PreOrder(node);
    		System.out.println();
    		System.out.println("中序：");
    		tree.InOrder(node);
    		System.out.println();
    		System.out.println("后序：");
    		tree.PostOrder(node);
    	}
    }

测试结果：

先序：
    A B D G C E F 
    中序：
    D G B A E C F 
    后序：
    G D B E F C A

[Image 1]: