数据结构——二叉树

此篇文章与大家分享数据结构二叉树专题
如果有不足的或者错误的请您指出!

1.树形结构

1.1概念

树是一种非线性的数据结构,是由n(n >= 0)个有限节点形成的一个就有层次关系的集合,把它叫做树是因为它看起来像一棵倒挂的数,也就是说他的根是朝上的,叶子是朝下的

树具有以下特点:
(1)树有一个特殊的节点,叫做根节点,根节点是没有前驱节点的

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

在树形结构里面,子树之间时不能有交集的,否则就不是树形结构
即除了根节点以外,其余节点有且只有一个父亲节点

(3)一棵N个节点的树有N-1条边

1.2关于树的常见概念

节点的度:一个节点中含有子树的个数称为该节点的度,如上图A的度为6

树的度:一棵树中,所有节点度中最大的一个,就是树的度,如上图,树的度为6
叶子结点或终端节点:度为0的节点就是叶子节点 / 终端节点,如上图B,C,H,I…等节点
双亲节点或父节点:若一个节点含有子节点,那么这个节点称为该子节点的父节点,如上图,A是B的父节点

孩子节点或子节点:一个节点含有的子树的根节点,称为该节点的子节点,如上图,B是A的子节点

根节点:一棵树中,没有双亲节点的节点就是根节点,如上图的A

节点的层次:从根节点开始定义,根节点为第一层,根节点的子节点为第二层,以此类推

树的高度或深度:表示树中节点的最大层次.如上图,树的层次为4

树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等节点为分支结点

兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>=0）棵互不相交的树组成的集合称为森林

1.3树的表示形式

树结构针对线性表就比较复杂了,要存起来就比较麻烦了,实际中树有很多表示方法,如双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法等等
这里我们就简单了解一下最常用的孩子兄弟表示法

class Node {
   int val;//节点中存放数值
   Node firstChild;//第一个孩子引用
   Node nextBrother;//下一个孩子兄弟引用
}

1.4树的应用

文件系统管理(目录和文件)

2.二叉树

2.1概念

一棵二叉树是节点的一个有限集合,该集合:
(1)或者为空
(2)或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成的

从上图可以看出：

1. 二叉树不存在度大于2的结点，即每个节点的度小于等于2
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
3. 对于任意的二叉树都是由以下几种情况复合而成的
   

2.2两种特殊下的二叉树

2.2.1满二叉树

一棵二叉树,如果每一层的节点数都达到最大值,则这颗树就是满二叉树.也就是说,如果一棵二叉树的层数为n,且节点的个数总是为 2 ^ k - 1,则它就是满二叉树

2.2.2完全二叉树

完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

如果出现哪一层中两个非空节点间隔一个空节点，那一定不是完全二叉树

2.3二叉树的性质

• 若根节点的层数为1,则一棵非空二叉树的第I层上最多有 2 ^ (i-1)个节点
• 若规定根节点的深度为1,则深度为K的二叉树的最大节点个数为2 ^ K - 1
• 若一棵二叉树中,度为0的节点数量为n0,度为2的节点数量为n2,则有n2 = n0 + 1,即度为2的节点数量比度为0的节点数量少一个
• 具有n个节点的完全二叉树的深度为 log2(n+1) (以2为底的对数向上取整)
• 对于具有n个节点的完全二叉树,如果按照从小到大的顺序对所有节点从0到i开始编号,则对于所有的节点有:
• 若i > 0,双亲节点为 (i - 1) / 2;i = 0,那么该节点为根节点,无双亲节点
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子

即已知孩子节点下标为i，则父亲节点的下标为(i - 1) / 2; 已知父亲节点的下标为i，则左孩子节点的下标为2 i + 1, 右孩子节点下标为 2 i+ 2；

2.4 二叉树的存储

二叉树的存储结构分为 顺序结构 和 类似链表的链式结构存储
我们在这里讲的是链式结构
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方法有二叉和三叉表示方式

// 孩子表示法
class Node {
  int val; // 数据域
  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
  int val; // 数据域
  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  Node parent; // 当前节点的根节点
}

我们这里是采用孩子表示法来构建二叉树的

2.4二叉树的基本操作

2.4.1以穷举的操作,手动创建一棵二叉树出来

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

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

    
    //以穷举的方式创建一棵二叉树
    public TreeNode 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');
        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;
    }
}

上述代码并不是真正的创建二叉树,只是简单创建, 方便我们后续操作

2.4.2二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按

照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

• NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。

• LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。

• LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。

• 层序遍历:设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

我们在上面创建的二叉树为:

那么我们接下来就通过代码的方式来对二叉树进行遍历:

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

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


    //以穷举的方式创建一棵二叉树
    public TreeNode 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');
        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 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 + " ");
    }
}

此时我们验证一下:

答案就是我们所预期的

2.4.3二叉树的其余操作

    //得到节点的个数

    private static int nodeSize = 0;
    public int size(TreeNode root){
        sizeCount(root);
        return nodeSize;
    }
    private void sizeCount(TreeNode root) {
        if(root == null) {
            return;
        }
        nodeSize++;
        sizeCount(root.left);
        sizeCount(root.right);
    }

    //得到叶子节点的个位(子问题思想)
    public int nodeSize(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftCount = nodeSize(root.left);
        int rigtCount = nodeSize(root.right);
        return leftCount + rigtCount + 1;
    }

    //得到叶子节点的个数
    private static int leafSize = 0;
    public int getLeafSize(TreeNode root) {
        getleaf(root);
        return leafSize;
    }

    private void getleaf(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getleaf(root.left);
        getleaf(root.right);
    }

    //得到叶子节点的各个数(子问题思想)
    public int getLesfNodeSize(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        int leftSize = getLesfNodeSize(root.left);
        int rightSize = getLesfNodeSize(root.right);
        return leftSize + rightSize;
    }

    //root的第k层有多少个节点
    public int floorKCount(TreeNode root, int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return floorKCount(root.left, k-1) + floorKCount(root.right, k-1);
    }

    //获得二叉树的高度
    public int getHight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHight = getHight(root.left);
        int rightHight = getHight(root.right);
        return Math.max(leftHight,rightHight) + 1;
    }

    //判断是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if(cur != null){
                queue.poll();
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null){
                return false;
            }
        }
        return true;
    }