Java：簡單二叉樹的實現以及前序，中序，後序遍歷

參考：https://blog.csdn.net/android_heng/article/details/76599302

二叉樹建立包括：根節點，左孩子，右孩子，data

定義如下：

BinTree root;
BinTree lChild;
BinTree rChild;
Object data;
List<BinTree> datas;

建立二叉樹的方法：

public void CreateTree(Object[] objs){
		datas = new ArrayList<BinTree>();
		for(Object obj : objs){
			datas.add(new BinTree(obj));
		}
		root = datas.get(0);
		for(int i=0;i<datas.size()/2;i++){
			datas.get(i).lChild = datas.get(2*i+1);
			if((2*i+2)<datas.size()){
				datas.get(i).rChild = datas.get(2*i+2);
			}
		}
	}

二叉樹的遍歷:

1:先序遍歷(DLR)

  1):訪問根節點;

  2):按先序遍歷訪問左子樹

  3):按先序遍歷訪問右子樹

//前序遍歷
	public void preOrder(BinTree root){
		if(root!=null){
			visit(root.getdata());
			preOrder(root.getlchild());
			preOrder(root.getrchild());
		}
	}

2:中序遍歷(LRD)

 1):按中序遍歷左子樹

 2):訪問根節點

 3):按中序遍歷訪問右子樹

//中序遍歷
public void inOrder(BinTree root){
	if(root!=null){
		inOrder(root.getlchild());
		visit(root.getdata());
		inOrder(root.getrchild());
	}
}

3:後序遍歷

 1):按後序遍歷訪問左子樹

 2):按後序遍歷訪問右子樹

 3):訪問根節點

//後序遍歷
public void afterOrder(BinTree root){
	if(root!=null){
		afterOrder(root.lChild);
		afterOrder(root.rChild);
		visit(root.getdata());
	}
}

二叉樹建立以及遍歷完整代碼如下：

class BinTree{
    BinTree root;
    BinTree lChild;
    BinTree rChild;
    Object data;
    List<BinTree> datas;
    
    public BinTree(BinTree lChild,BinTree rChild,Object data){
        super();
        this.lChild = lChild;
        this.rChild = rChild;
        this.data = data;
    }
　　//先將data給到節點，並將節點的左右子樹設置為空，後面再分配左右子樹
    public BinTree(Object data){
        this(null,null,data);
    }
    public BinTree(){
        super();
    }
    
    public Object getdata(){
        return this.data;
    }
    public BinTree getlchild(){
        return this.lChild;
    }
    public BinTree getrchild(){
        return this.rChild;
    }
    //建立二叉樹
    public void CreateTree(Object[] objs){
        datas = new ArrayList<BinTree>();
        for(Object obj : objs){
            datas.add(new BinTree(obj));
        }
        root = datas.get(0);
        for(int i=0;i<datas.size()/2;i++){
            datas.get(i).lChild = datas.get(2*i+1);
            if((2*i+2)<datas.size()){
                datas.get(i).rChild = datas.get(2*i+2);
            }
        }
    }
    //前序遍歷
    public void preOrder(BinTree root){
        if(root!=null){
            visit(root.getdata());
            preOrder(root.getlchild());
            preOrder(root.getrchild());
        }
    }
    //中序遍歷
    public void inOrder(BinTree root){
        if(root!=null){
            inOrder(root.getlchild());
            visit(root.getdata());
            inOrder(root.getrchild());
        }
    }
    //後序遍歷
    public void afterOrder(BinTree root){
        if(root!=null){
            afterOrder(root.lChild);
            afterOrder(root.rChild);
            visit(root.getdata());
        }
    }
    
    public void visit(Object obj){
        System.out.print(obj+" ");
    }
    public BinTree getroot(){
        return this.root;
    }
}

測試代碼：

public class BinaryTree {
    public static void main(String[] args){
        BinTree binTree = new BinTree();
        Object[] num = {34,56,2,56,8745,33,76,445};
        binTree.CreateTree(num);
        System.out.print("前序遍歷：");
        binTree.preOrder(binTree.getroot());
        System.out.print("\n"+"中序遍歷：");
        binTree.inOrder(binTree.getroot());
        System.out.print("\n"+"後序遍歷：");
        binTree.afterOrder(binTree.getroot());
    }
}

結果：