【Java】二叉树：数据海洋中灯塔式结构探秘（上）

个人主页 🌹：喜欢做梦

二叉树中有一个树，我们可以猜到他和树有关，那我们先了解一下什么是树，在来了解一下二叉树

一🍝、树型结构

1🍨.什么是树型结构？

树是一种非线性的数据结构，它是由n（n>=0）个有限节点（结点）和边组成的层次结构的集合。有一个特定的节点为根节点，其余节点通过边连接形成的分支，每个节点可以有零个或多个子节点。把它叫做树是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。

什么是线性结构？什么是非线性结构？

线性结构：数据元素呈现一对一的线性关系，除第一个和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后继；

非线性结构：数据元素之间的关系不是简单的一对一，一个元素可能有多个前驱或后继，或者两者都有。

树的定义是递归的；
除根节点外的每一个结点都能引出一颗子树；
树型结构中，子树之间不能有交集，否则就不是树型结构；
除了跟节点之外，每个节点有且只有一个父节点；
一个N个节点的树有N-1条边，因为根节点的上方没有边；

2🍩.什么是非树型结构？

非树：节点间的连通性复杂，可能存在多个路径连接统一对节点，也肯存在孤立节点，即与其他节点无连接。

3🍪.树型结构的基本性质

结点的度：一个结点含有子树的个数称为该结点的度；如上图，A的度为3，C的度为2；
树的度：一颗树中，所有结点度的最大值称为结点的度；如上图，树的度为4；
叶子结点或终端结点：度为0的节点称为叶结点；如上图，E、F、G、P等结点为叶节点；
孩子结点或子结点：一个结点含有子树的根结点称为该结点的子结点即只有根节点的结点才是子节点；如上图，B是A的孩子结点；
双亲结点或父亲结点：若一个结点含有子结点，则这个树称为该结点的父结点；如图上A是B的父节点；
根结点：一个树没有双亲的结点；如上图，A；
结点的层次：从根开始定义，根为第一层，根的子结点为第二层，一次类推；
树的高度或深度：树中结点的最大层次；如上图，树的高度为4；
以下只需了解的概念：
非终端结点或分支结点：除根结点外，度不为0的结点；如上图：B、C、D、H为分支节点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点；
堂兄弟结点：不具有同一个父结点，但双亲在同一层的结点互为堂兄弟；如上图，G和H；
结点的祖先：从根到该结点所经分支的所有结点；如上图，A就是所有结点的祖先；
子孙：以某结点为根的子树中的任一节点，都称为该结点的子孙。如上图，所有结点都是A的子孙；
森林：有m（m>=0）课互不相交的树组成的集合称为森林；

4🍨.树的表现形式（了解）

树的表现形式有很多种，如双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里简单了解一下其中最常见的方法就是孩子兄弟表示法：

class Node{
    public int value;//数据
    public Node firstChild;//第一个孩子
    public Node nextBrother;//下一个兄弟
}

二🍝、二叉树

1🍑.什么是二叉树？

二叉树：二叉树是每个结点最多有两科子树的树的结构，其两个子树通常称为左子树和右子树。

二叉树的递归定义：

或者是一颗空树；
或者是一颗由一根结点和两课互不相交的分别称为左子树和右子树所组成的非空数，左子树和右子树又同样是二叉树；

特点：

度的限制：结点的度最大为2；
有序性：左右子树由顺序，即使某节点只有一颗子树，也要区分左右子树；

性质：

若规定的根节点层数为1，这一棵非空二叉树的第i层上最多有 $2^{i-1}$ （i>.0）个节点；
若规定只有根节点的二叉树的深度为1，则深度为k的二叉树的最大节点数是 $2^{k}-1$ （k>=0）;
对于任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0=n2+1；

2🍑.二叉树的类型

1.满二叉树

满二叉树：每一层的结点树都达到最大，除最后一层外每个节点都有两个节点。

特点：

节点度数：除最后一层的叶子节点外，其他层的每一个的节点都有两个节点，即度都为2；
叶子节点：所有的叶子节点都在同一层，且叶子节点的数量为 $2^{k-1}$ ，k为数的高度；
节点总数：节点总数是 $2^{k}-1$ ；

2.完美二叉树

完美二叉树：除最后一层外，其余层节点数都达到最大，最后一层节点从左到右依次按顺序排列，可通过数组的高效和访问，完美二叉树是满二叉树的一种。

特点：

节点度数：除了底层的叶子节点外，其余所有节点都有两个子节点，即度数均为2；
叶子节点分布：所有叶子节点都在同一层，这使得树的结构呈现出完美的形态；
具有n个节点的完全二叉树的深度k为 $\log_{2}$ (n+1)上取整进1；
节点数量：对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，这对于序号为i的节点有：

若i>0,双亲序号：（i-1）/2;i=0,i为根节点的编号，无双亲节点；
若2i+1<n,左孩子序号:2i+1,否则无左孩子；
若2i+1<n,右孩子序号：2i+2，否则无右孩子；

3🍪.二叉树的创建

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 createTree(){
        //创建节点
        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');
        //连接节点
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        return A;
    }
}

4.二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中的每个节点，且每个节点仅被访问一次。

二叉树的遍历方式主要有前序遍历、中序遍历、后序遍历；

前序遍历

前序遍历：遍历顺序是先访问根的的节点—>左子树—>右子树，也就是根、左、右；

前序遍历代码：

// 前序遍历
    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;
        }
        //遍历左子树
        preOrder(root.left);
        System.out.print(root.val+ " ");
        //遍历右子树
        preOrder(root.right);
    }

顺序：左子树--根节点--右子树；
根结点的打印位置：中间；

后序遍历

后序遍历：遍历顺序是先访问左子树—>右子树—>根的的节点，也就是左、根、右；

    // 后序遍历
    public void postOrder(TreeNode root){
        //判断是否有节点,没有返回
        if(root == null){
            return;
        }
        //遍历左子树
        preOrder(root.left);
        //遍历右子树
        preOrder(root.right);
        System.out.print(root.val+ " ");
    }
}

后序遍历的过程与前面的也是同理，就不画图过多解释了。

顺序：左子树--右子树--根节点；
根结点的打印位置：最后一个；

三者之间的区别：

	前序遍历	中序遍历	后序遍历
访问顺序	根、左、右	左、根、右	左、右、根
根节点访问位置	第一个	中间	最后一个
应用场景	二叉树结构、将表达式树转换为前缀表达式	用于输出有序序列，还能辅助将表达式树转换为中缀表达式	二叉树的高度、节点数，以及释放二叉树内存