二叉树【Java】

树

什么是树结构

树作为一种一对多的数据结构，是由n（n>0）个结点组成的有限集合；n=0是一棵空数，空数也可以看做是一棵树；

树的相关概念

下面的结构就是一棵具体的树：

对于这样一棵树而言：

• 树的结点：树的每个元素称为树的一个结点，每个结点都可以作为一棵树的根来引出下一棵子树；
• 结点的度：一个结点含有的子树的个数；例如上图中，结点A的度为2，结点C的度为1；
• 树的度：一棵树中，所有结点的最大值称为树的度；上图中树的度为2；
• 叶子结点（终端结点）：一棵树中，度为0的结点称为叶子结点；上图中D、E、F都是叶子结点；
• 双亲结点（父节点）和孩子结点（子节点）：例如上图中，A是B的父节点，B和C是A的子节点；
• 根结点：一棵树中，没有双亲结点的结点为树的根结点；上图树的根节点为A；
• 结点的层次：从根结点开始为第一层，根节点的子节点为第二层，以此类推；
• 树的高度：树中结点的最大层次；上图中树的高度为3；
• 深度：深度是相对结点的，即根节点到某个结点的距离；对于整棵树来说，树的高度和深度是相等的；

树的存储结构

树的存储结构是一种不同于顺序存储和链式存储的结构，主要有下面的几种存储方式：

• 双亲表示法：用一组连续的空间来存储树的结点，为每个结点设置一个指示器来标明该结点的双亲结点；

• 孩子表示法：由于树中的结点往往不止有一个子节点，我们可以为每个结点设置多个指针域，标明该结点的孩子结点；

• 孩子兄弟表示法：为每个结点设置2个指针域，一个是该结点第一个孩子的指向，第二个是该结点的下一个兄弟结点；

其实，在实际的程序设计过程中，树的存储结构有许多种方式，而我们一般使用较多的就是孩子兄弟表示法；

二叉树

二叉树的概念

二叉树是n个结点的有限集合，该集合由一个根节点和2棵互不相交的称为根节点的左子树和右子树的二叉树组成；

几种特殊的二叉树

• 满二叉树：二叉树的所有分支结点都具有左右子树，并且所有的叶子结点都在同一层；
• 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点的位置完全相同，这就是一棵完全二叉树；

二叉树的性质

• 每个结点最多有2棵子树，因此二叉树中不存在度大于2的结点；
• 二叉树的左右子树不可以颠倒，因此二叉树是有序树；
• 设二叉树的根结点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1） (i>0)个结点；

• 设根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k-1 (k>=0)个;

• 具有n个结点的完全二叉树的深度k为 log(n+1) (底数为2)向上取整；

• 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1；

• 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
  若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点；
  若2i+1<n，左孩子序号：2i+1，否则无左孩子；
  若2i+2<n，右孩子序号：2i+2，否则无右孩子；

二叉树的基本操作

二叉树的基本操作主要就是对通过对二叉树遍历再进行相关的操作，这里对二叉树的所有操作都基于这样一棵二叉树：

import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public char val;    //当前结点存储的值
        public TreeNode left;       //左孩子
        public TreeNode right;      //右孩子

        public TreeNode(char val){
            this.val=val;
        }
    }
/**
 * 手动创建一棵二叉树
 * 返回二叉树的根结点
 * */
    public TreeNode CreateBinaryTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        TreeNode I=new TreeNode('I');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.right=F;
        D.left=G;
        D.right=H;
        E.right=I;

        return A;

    }
/**
 * 前序遍历（根-左-右）
 * */
    void preOrder(TreeNode root){
        if (root==null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 中序遍历（左-根-右）
     * */
    void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**
     * 后序遍历（左-右-根）
     * */
    void postOrder(TreeNode root){
        if (root==null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 层序遍历(从根结点开始，从左到右逐层遍历)
     *
     * */
    void  levelOrder(TreeNode root){

        if(root==null){
            return ;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left!=null){
                queue.offer(cur.left);
            }
           if (cur.right!=null){
               queue.offer(cur.right);
           }


        }
    }




    /**
     * 获取树中节点的个数
     * 由于递归的特殊性，计数器必须在递归函数之外，否则每次递归计数器都会置0；
     * */
    int count=0;
    int size(TreeNode root){

        if (root==null){
            return 0;
        }
        size(root.left);
        count++;
        size(root.right);
        return count;
    }


    //

    /**
     * 获取叶子节点的个数
     * 遍历二叉树，当结点的左右孩子都为空时，为叶子结点，计数器加1；
     * */
    int getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }

        if (root.left==null&&root.right==null){
            count++;
        }
        getLeafNodeCount(root.left);

         getLeafNodeCount(root.right);


        return count;
    }



    /**
     *  获取第K层节点的个数
     *
     * */
    int getKLevelNodeCount(TreeNode root,int k){
        if (root==null) return 0;
        if (k==1) return 1;
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);

    }

    /**
     * 获取二叉树的高度
     * 即左右数高度的最大值+1；
     * */
    int getHeight(TreeNode root){
        if (root==null) return 0;
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }


    /**
     * 检测值为value的元素是否存在
     *
     * */
    TreeNode find(TreeNode root, int val){
        if (root==null) return null;
        if (root.val==val) return root;
        TreeNode ret=find(root.left,val);
        if (ret!=null){
            return ret;
        }
         ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;


    }
    
   
}

over！