Java数据结构第十二期：走进二叉树的奇妙世界(一)

专栏：数据结构(Java版)

个人主页：手握风云

一、树型结构

1.1. 树的定义

1.2. 树的基本概念

1.3. 树的表示形式

二、二叉树

2.1. 概念

2.2. 两种特殊的二叉树

2.3. 二叉树的性质

2.4. 二叉树的存储

三、二叉树的基本操作

一、树型结构

1.1. 树的定义

树是⼀种⾮线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：

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

注意，在树型结构中，子树与子树之间不能有交集，否则就不是树型结构。

1.2. 树的基本概念

结点的度：⼀个结点含有⼦树的个数称为该结点的度；如上图，A的度为2

树的度：⼀棵树中，所有结点度的最⼤值称为树的度；如上图，树的度为3

叶子结点或终端结点：度为0的结点称为叶结点；如上图，G、H、I、J都是叶结点

父结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图，A是B的父节点

子结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图，B是A的子结点

根结点：⼀棵树中，没有父结点的结点；如上图，A

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

树的高度或深度：树中结点的最大层次；如上图，树的高度是4

1.3. 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就⽐较麻烦了，实际中树有很多种表示⽅式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这⾥就简单的了解其中最常用的孩子兄弟表示法。

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

二、二叉树

2.1. 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的⼆叉树组成。

从上图中可以看出：⼆叉树不存在度⼤于2的结点；⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树。

注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的。

2.2. 两种特殊的二叉树

满二叉树：如果一棵二叉树的层数为K，且结点总数是 $2^{k}-1$ ，则它就是满⼆叉树。
完全二叉树：完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点一一对应。满二叉树是一种特殊的完全二叉树。

2.3. 二叉树的性质

若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有(i>0)个结点
若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数是(k>=0)
对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1
具有n个结点的完全⼆叉树的深度k为上取整

2.4. 二叉树的存储

二叉树的存储方式分为：顺序结构和类似于链式的结构。我们这里主要介绍链式存储。⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。

//孩子表示法
class Node{
    int val;//数据域
    Node left;//左孩子引用
    Node right;//右孩子引用
}

//孩子双亲表示法
class Node{
    int val;
    Node left;
    Node right;
    Node parent;//当前节点的根节点
}

三、二叉树的基本操作

我们可以自己创建一个二叉树，我们可以参照之前创建链表、栈、队列的方式来手动创建二叉树。

public class BinaryTree {
    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');
        TreeNode H = new TreeNode('H');

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

        return A;
    }
}

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.CreateTree();//因为是静态内部类
        System.out.println("========");
    }
}

我们在打印这一行大一个断点进行调试。先走完A结点，再通过递归的方法，去遍历左孩子结点B和右孩子结点C，以此类推，再去遍历B的左孩子结点E和右孩子结点F。