数据结构(六)-二叉树

二叉树的特点是每个节点最多有两个分支，即二叉树中不存在度大于2的结点。

二叉树的遍历

• 先序遍历(根-左-右)
• 中序遍历(左-根-右)
• 后续遍历(左-右-根)

package com.lq.bintree;

import java.util.ArrayList;
import java.util.List;

public class BinTree {  
    private BinTree leftChild;   //左孩子结点
    private BinTree rightChild;  //右孩子结点  
    private BinTree root;        //根节点结点  
    private Object data;        //数据域  
    private List<BinTree> datas;//存储所有的节点  
    public BinTree(BinTree leftChild, BinTree rightChild, Object data) {  
        super();  
        this.leftChild = leftChild;  
        this.rightChild = rightChild;  
        this.data = data;  
    }  
    public BinTree(Object data) {  
        this(null, null, data);  
    }  
    public BinTree() {  
        super();  
    }  
      
    public void createTree(Object[] objs){  
        datas=new ArrayList<BinTree>();  
        for (Object object : objs) {  
            datas.add(new BinTree(object));  
        }  
        root=datas.get(0);//将第一个作为根节点  
        for (int i = 0; i < objs.length/2; i++) {  
            datas.get(i).leftChild=datas.get(i*2+1);  
            if(i*2+2<datas.size()){//避免偶数的时候 下标越界  
                datas.get(i).rightChild=datas.get(i*2+2);  
            }  
        }  
    }  
    //先序遍历(递归)  
    public void preorder(BinTree root){  
        if(root!=null){  
            visit(root.getData());  
            preorder(root.leftChild);  
            preorder(root.rightChild);  
        }  
          
    }  
    //中序遍历(递归)  
    public void inorder(BinTree root){  
        if(root!=null){  
            inorder(root.leftChild);  
            visit(root.getData());  
            inorder(root.rightChild);  
        }  
          
    }  
    //后序遍历(递归)  
    public void afterorder(BinTree root){  
        if(root!=null){  
            afterorder(root.leftChild);  
            afterorder(root.rightChild);  
            visit(root.getData());  
        }  
          
    }  
    private void visit(Object obj) {  
        System.out.print(obj+" ");  
    }  
    public Object getData() {  
        return data;  
    }  
    public BinTree getRoot() {  
        return root;  
    }  
      
}  

测试

package com.lq.bintree;

public class TestTree {
     public static void main(String[] args) {  
            BinTree binTree=new BinTree();  
            Object[] objs={0,1,2,3,4,5,6,7};  
//          Object[] objs={"a","b","c","d","e","f","g","h","i","j","k","l"}; 
            binTree.createTree(objs);  
          binTree.preorder(binTree.getRoot()); //先序遍历  
//        binTree.inorder(binTree.getRoot()); //中序遍历  
//          binTree.afterorder(binTree.getRoot()); //后序遍历  
        }  

}

先序遍历的结果为:0 1 3 7 4 2 5 6

中序遍历的结果为:7 3 1 4 0 5 2 6

后序遍历的结果为:7 3 4 1 5 6 2 0