接下来博主会持续更新JavaSE、Java数据结构、MySQL、JavaEE、微服务、Redis等等内容的知识点整理。后续我也会精心制作算法解析、项目经验系列内容，内容绝对干货。相信这些文章能够成为我和大家的“葵花宝典”，喜欢的话就关注一下吧！敬请期待！

树型结构

概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。它具有以下的特点：

1. 有一个特殊的结点，称为根结点，根结点没有前驱结点。
2. 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继节点。
3. 树是递归定义的。

树与非树？

• 子树之间是不能够有任何相交的，否则就不是树结构。
• 除了根结点外，每个结点有且仅有一个父结点；
• 一棵有N个结点的树就有N-1条边。

树的一些重要概念

1. 结点的度 ： 一个结点含有子树的个数称为该结点的度；

2. 树的度 ： 一棵树中，所有结点度的最大值称为树的度；

3. 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

4. 树的高度或深度：树中结点的最大层次；

树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表
示方式，如： 双亲表示法 ，孩子表示法、孩子双亲表示法、 孩子兄弟表示法等等。

其中最常用的孩子兄弟表示法：

class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}

二叉树

概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。

注：二叉树中节点的度>=0，且<=2

两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。

• 也就是说，一棵深度为k，且含有(2^k) -1 (2的k次方减1)个结点的二叉树就是满二叉树（可以推导出满二叉树的前n层的节点总数＋1=最后一层的节点数）。
• 简要讲它的概念就是每一层上的结点数都达到最大值，外观上是一个标准的三角形。

满二叉树有一个非常规则的特性：从第一层到最后一层，每层的节点数构成一个首项为1、公比为2的等比数列 。

2. 完全二叉树: 完全二叉树是效率很高的数据结构。深度为k，有n个结点的二叉树，当且仅当其每一个结点都与同深度满二叉树中编号1~n的结点一一对应，那么此二叉树就是完全二叉树。

• 通俗讲就是一颗二叉树的节点生长，从上到下一层一层地生长。每一层又按从左到右依次生长，不得越过此顺序生长。这样得来的二叉树就是完全二叉树。

要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质（重在理解其原理）

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)（2的(i-1次方)）(i>0)个结点。
2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(2^k)-1(k>=0)。
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的结点个数为n2,则有n0 ＝ n2 ＋ 1
4. 具有 n个结点的完全二叉树的深度k为log₂(n+1)上取整。
5. 对于具有 n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有 ：

• 若i>0 ， 双亲序号： (i-1)/2；
• 若i=0 ， i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号为2i+1，否则无左孩子
• 若2i+2<n，右孩子序号为2i+2，否则
  无右孩子

二叉树的一些基本操作及其代码实现

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

public class binaryTree {
    public static class treeNode{
        public char val;
        public treeNode left;
        public treeNode right;

        public treeNode(char val) {
            this.val = val;
        }
    }

    public treeNode root;


    public void creatTree(){
        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');

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

    }

    //前序遍历
    public void preOrder(treeNode root){
        if(root==null) return;
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(treeNode root){
        if(root==null) return;
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(treeNode root){
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }


    //获取树的节点总个数
    public int size(treeNode root){
        if(root==null) return 0;
        int size=size(root.left)+size(root.right)+1;
        return size;
    }

    //获取叶子节点的总个数
    public int getLeafNodeNum(treeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }

        return getLeafNodeNum(root.left)+
                getLeafNodeNum(root.right);
    }

    //获取树的高度
    public int getHight(treeNode root){
        if (root == null) return 0;
        int hight=Math.max(getHight(root.left),getHight(root.right));
        return hight+1;
    }

    //获取第k层节点的个数
    public int KthNodeNum(treeNode root,int k,int hight){
        if(k>hight||k<=0){
            System.out.println("查询的层数有误....");
            return -1;
        }

        if(root==null) return 0;
        if(k==1) return 1;

        return KthNodeNum(root.left,k-1,hight)+
                KthNodeNum(root.right,k-1,hight);
    }

    //检测值为指定字符的节点是否存在，若存在则返回其所在节点
    public treeNode find(treeNode root,char ch){
        if (root == null) return null;

        if(root.val==ch){
            return root;
        }
        treeNode left =find(root.left,ch);
        treeNode right=find(root.right,ch);

        if(left!=null){
            return left;
        }else{
            return right;
        }
    }

    //层序遍历
    public void levelOrder(treeNode root){
        Queue<treeNode> que=new LinkedList<treeNode>();
        que.offer(root);
        while (!que.isEmpty()){
           treeNode cur=que.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                que.offer(cur.left);
            }
            if(cur.right!=null){
                que.offer(cur.right);
            }
        }
        System.out.println();
    }


    //判断一棵二叉树是不是一棵完全二叉树
    public boolean isCompleteTree(treeNode root){
        if (root == null) {
            return true;
        }
        Queue<treeNode> que=new LinkedList<>();
        que.offer(root);
        //按照层序遍历的逻辑遍历二叉树
        while(!que.isEmpty()){
            treeNode node=que.poll();
            if(node==null){//一旦发现队列中有了空树就跳出循环，去检查队列中剩下节点情况
                break;
            }

            que.offer(node.left);
            que.offer(node.right);

        }
        //这个时候检查队列中剩下节点中是否有非空节点
        int size= que.size();
        while (size!=0){
            treeNode node=que.poll();
            if(node!=null){//还有非空节点，就说明不是完全二叉树
                return false;
            }
            size--;
        }
        return true;//队列剩下的节点没有非空节点
    }




}

二叉树精选算法题解析

1. Java算法题解析（6）——二叉树专题基础篇

2. Java算法题解析（7）——二叉树专题初阶篇

3. Java算法题解析（8）——二叉树专题进阶篇及解题方法总结

觉得文章对你有帮助的话就点个赞，收藏起来这份免费的资料吧！也欢迎大家在评论区讨论技术、经验