【数据结构与算法】详解二叉树以及模拟实现二叉树

前言:

二叉树在学习数据结构中是一种很重要的类型,也是学习数据结构中比较困难的一种结构,但是在平时用的也是非常多,因此二叉树尤为重要.
本篇文章中会涉及到大量的递归代码,如果一些地方不太理解,可以尝试画图梳理代码执行流程
关于文章中的二叉树源码→点击即可跳转 需要的可以去看一看

1.二叉树的定义

二叉树binary tree是指树中节点的度不大于2的有序树它是一种最简单且最重要的树。二叉树的递归定义为二叉树是一棵空树或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树左子树和右子树又同样都是二叉树

2.二叉树的相关术语

①节点包含一个数据元素及若干指向子树分支的信息 。
②节点的度一个节点拥有子树的数目称为节点的度 。
③叶子节点也称为终端节点没有子树的节点或者度为零的节点。
④分支节点也称为非终端节点度不为零的节点称为非终端节点 。
⑤树的度树中所有节点的度的最大值。
⑥节点的层次从根节点开始假设根节点为第1层根节点的子节点为第2层依此类推如果某一个节点位于第L层则其子节点位于第L+1层。
⑦树的深度也称为树的高度树中所有节点的层次最大值称为树的深度。
⑧有序树如果树中各棵子树的次序是有先后次序则称该树为有序树。
⑨无序树如果树中各棵子树的次序没有先后次序则称该树为无序树。
⑩森林由mm≥0棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除则该树就变成了一片森林森林中的树由原来根节点的各棵子树构成

3.二叉树的性质

性质1二叉树的第i层上至多有2i-1i≥1个节点 。
性质2深度为h的二叉树中至多含有2h-1个节点。
性质3若在任意一棵二叉树中有n0个叶子节点有n2个度为2的节点则必有n0=n2+1。
性质4具有n个节点的满二叉树深为log2n+1。
性质5若对一棵有n个节点的完全二叉树进行顺序编号1≤i≤n那么对于编号为ii≥1的节点
当i=1时该节点为根它无双亲节点 。
当i>1时该节点的双亲节点的编号为i/2 。
若2i≤n则有编号为2i的左节点否则没有左节点 。
若2i+1≤n则有编号为2i+1的右节点否则没有右节点 。

4.特殊的二叉树

1、满二叉树如果一棵二叉树只有度为0的节点和度为2的节点并且度为0的节点在同一层上则这棵二叉树为满二叉树。
2、完全二叉树深度为k有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时称为完全二叉树 。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

5.二叉树的遍历

二叉树的遍历主要有前序遍历,中序遍历,后序遍历以及层序遍历,前面三种遍历主要是采用递归的方式进行遍历的,如果看不懂,建议画图梳理一下代码执行流程

前序遍历

        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);
        }

后序遍历

        void postOrder(TreeNode root) {
            if(root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }

层序遍历

    public 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);
            }

        }
    }

6.获取树中节点的个数

方法1:遍历思想

    public static int nodeSize = 0;// 记录二叉树的结点个数

    public void size(TreeNode root) {
        if(root == null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }

方法2:子问题的思想

    public int size2(TreeNode root) {
        if(root == null){
            return 0;
        }
        // 难点 -> 画图 在叶子结点时 会返回1 根是最后加上的
        return size2(root.left)+size2(root.right)+1;
    }

7.获取叶子节点的个数

叶子结点的左子树和右子树都为null,因此只要看哪些结点符合条件的就可以了

方法1:遍历思想

    public static int leafSize = 0;

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

方法2:子问题的思想

    public int getLeafNodeCount2(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

8.获取第K层节点的个数

    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        if(k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        k--;
        return getKLevelNodeCount(root.left,k) + getKLevelNodeCount(root.right,k);
    }

9.获取二叉树的高度

    public int getHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

10.检测值为value的元素是否存在

这里实现的时候返回值设置的是TreeNode,如果不喜欢可以换成boolean

    public TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode treeNode1 = find(root.left,val);
        if(treeNode1 != null){
            return treeNode1;
        }
        TreeNode treeNode2 = find(root.right,val);
        if(treeNode2 != null){
            return treeNode2;
        }
        return null;
    }

11.判断一棵树是不是完全二叉树

判断是不是完全二叉树,这里使用的是队列做的.也涉及到分层遍历的思想,将每层的结点以及最后一层结点的孩子结点存下来,然后对第一次出现null时后的数据开始进行判断.如果是完全二叉树,那么最后一次遍历的数据都是null,如果不是完全二叉树,那么就是结点和null并存的情况,而且一定是在结点前有个null

    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode ret = queue.poll();
            if (ret != null){
                return false;
            }
        }
        return true;
    }