二叉树

二叉树概述以及java实现二叉树前中后序遍历

1 树的基本术语有：

若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

结点的度：结点拥有的子树的数目

叶子结点：度为0的结点

分支结点：度不为0的结点

树的度：树中结点的最大的度

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1

树的高度：树中结点的最大层次

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

2 完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

==面试题：如果一个完全二叉树的结点总数为768个，求叶子结点的个数。由二叉树的性质知：n0=n2+1，将之带入768=n0+n1+n2中得：768=n1+2n2+1，因为完全二叉树度为1的结点个数要么为0，要么为1，那么就把n1=0或者1都代入公式中，很容易发现n1=1才符合条件。所以算出来n2=383，所以叶子结点个数n0=n2+1=384==

总结规律：如果一棵完全二叉树的结点总数为n，那么叶子结点等于n/2（当n为偶数时）或者(n+1)/2（当n为奇数时）

java代码实现

要求：将一个数组中的数以二叉树的存储结构存储，并遍历打印。

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

public class bintree {
    public bintree left;
    public bintree right;
    public bintree root;
    //    数据域
    private Object data;
    //    存节点
    public List<bintree> datas;

    public bintree(bintree left, bintree right, Object data){
        this.left=left;
        this.right=right;
        this.data=data;
    }
    //    将初始的左右孩子值为空
    public bintree(Object data){
        this(null,null,data);
    }

    public bintree() {

    }

    public void creat(Object[] objs){
        datas=new ArrayList<bintree>();
        //        将一个数组的值依次转换为Node节点
        for(Object o:objs){
            datas.add(new bintree(o));
        }
//        第一个数为根节点
        root=datas.get(0);
        System.out.println("----->"+datas.get(0).data);
//        建立二叉树
        for (int i = 0; i <objs.length/2; i++) {
//            左孩子
            datas.get(i).left=datas.get(i*2+1);
            System.out.println("----->"+datas.get(i*2+1).data);
//            右孩子
            if(i*2+2<datas.size()){//避免偶数的时候 下标越界
                datas.get(i).right=datas.get(i*2+2);
                System.out.println("----->"+datas.get(i*2+2).data);
            }
        }
    }
    //先序遍历
    public void preorder(bintree root){
        if(root!=null){
            System.out.println(root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }
    //中序遍历
    public void inorder(bintree root){
        if(root!=null){
            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
    }
    //    后序遍历
    public void afterorder(bintree root){
        if(root!=null){
            System.out.println(root.data);
            afterorder(root.left);
            afterorder(root.right);
        }
    }
    public static void main(String[] args) {
        bintree bintree=new bintree();
        Object []a={2,4,5,7,1,6,12,32,51,22};
        bintree.creat(a);
        bintree.preorder(bintree.root);
        System.out.println("-------------------------------------");
        bintree.inorder(bintree.root);
    }
}