Java：简单二叉树的实现以及前序，中序，后序遍…

2018-08-17 09:39:52来源：博客园阅读 ()

参考：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());
    }
}