数据结构-5.Java. 二叉树

本篇博客给大家带来的是二叉树的知识点, 其中包括面试经常会提问的真题 ArrayList 和 LinkedList 的区别 .

文章专栏: Java-数据结构

若有问题 评论区见

欢迎大家点赞 评论 收藏 分享

如果你不知道分享给谁,那就分享给薯条。

你们的支持是我不断创作的动力 .

1. 二叉树

1.1 二叉树的概念

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

1.2 两种特殊的二叉树

1. 满二叉树: 一颗二叉树, 如果每层的结点数都达到最大值, 则这颗二叉树就是满二叉树. 若满二叉树的层数为K, 那么其节点总数是 2^k - 1.

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

1.3二叉树的性质

1. 若规定 根结点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有 2^(i-1)  (i>0) 个结点. 2. 若规定只有 根结点的二叉树的深度为 1 ，则 深度为 K 的二叉树的最大结点数是 2^k  -  1 (k>=0). 3. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 ＝ n2 ＋ 1 4. 具有 n 个结点的完全二叉树的深度 k 为  log2(n+1)  上取整 5. 对于具有 n 个结点的完全二叉树 ，如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 ，则对于 序号为 i 的结点有 ： 若 i>0 ，将 i 看作孩子节点  双亲序号： (i-1)/2 ；  将 i 看作父亲节点 且 2i+1 根的右树。 LNR ：中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。 LRN ：后序遍历 (Postorder Traversal)—— 根的左子树 ---> 根的右子树 ---> 根节点。 下图是 前序遍历的递归过程,  中序遍历 和 后序遍历类似. 前序遍历结果： 1 2 3 4 5 6 中序遍历结果： 3 2 1 5 4 6 后序遍历结果： 3 1 5 6 4 1 以上图二叉树为例, 代码实现前中后序递归遍历. 注意:  根的左子树, 不只是根的左节点, 而是根左边的整颗子树. 右子树同理.  如上右图.  代码实现前分析(以前序遍历为例): 前序遍历的顺序为 根 左子树 右子树,  凡是递归必有一终止条件, 以上右图为例, 从根节点往左递 到 3 ,3的左子树为null, 则返回.  所以 终止条件为 root 等于null 则返回. 按照顺序: 先打印根节点, 再递归左子树, 后递归右子树. 

 //前序遍历: 根 左 右
    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+" ");
    }

画图理解前序遍历的递归过程. 

A的右子树递归过程与上图类似.

2. 层序遍历

层序遍历 ：除了前序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历, 如下图所示, 层序遍历的结果: A B C D E F G H  代码实现 非递归 层序遍历 :  非递归层序遍历, 我们可以借助上一章所学的队列, 利用队列"先进先出" 的特点 , 实现层序遍历 思路: 二叉树以 根节点  左节点  右节点 的顺序入队,  出队顺序即为层序遍历 如下图: 具体步骤: 先将 根节点 入队 , 进入循环 while(!queue.isEmpty()) , 弹出栈顶元素 赋给 cur . 打印根节点,  将cur 的 左右节点入队. 

//二叉树的层序遍历
    public void levelOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue 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);
            }
        }
    }

1.5.3 二叉树的基本操作

//1.  获取树中节点的个数 int size ( Node root ); 第一种方法: 通过二叉树的遍历求, 每递归遍历一次, size++.

public int size = 0;
    //前序遍历,求二叉树节点个数
    public void nodeSize(TreeNode root) {
        if(root == null) return;
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
    }
    //中序和后序也类似, 无非就是把打印节点的代码换成size++;

第二种方法: 通过子问题解决: 总节点数 = 左子树 + 右子树 + 1;

思路: 总的节点数实际上就是所有的左节点数 + 右节点数 + 1.

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

//2.  获取叶子节点的个数 int getLeafNodeCount ( Node root ); 第一种思路: 定义leafSize存储叶子节点的个数,  在前序遍历中, 当某个节点的左右节点都为null时, 则leafSize++;

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

第二种思路: 求二叉树叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数.

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

//3.  获取第 K 层节点的个数 int getKLevelNodeCount ( Node root , int k );

//获取第K层节点的个数
    public int getKLeveNodeCount(TreeNode root,int k) {
        if(root == null) return 0;
        if(k == 1) {
            return 1;
        }
        return getKLeveNodeCount(root.left,k-1) +
                getKLeveNodeCount(root.right,k-1);
    }

//4.  获取二叉树的高度 int getHeight ( Node root ); 思路: 二叉树的高度 = 左子树与右子树之中最大高度+1,

//求二叉树的高度.
    public int gerHeight(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) {
            return 1;
        }
        int leftTree = gerHeight(root.left);
        int rightTree = gerHeight(root.right);
        return (leftTree > rightTree ? leftTree+1 : rightTree+1);
    }

// 5.  检测值为 value 的元素是否存在 public boolean  find ( Node root , int val ); 还是一样的, 通过遍历来确定二叉树是否存在值为value的节点, 以前序遍历为例, 判断根节点, 递归左子树, 在判断左子树, 递归右子树,再判断右子树. 如果全都没找到则return false.

//检测值为val的元素是否存在
    public boolean find(TreeNode root,char key) {
        if(root == null) return false;
        if(root.val == key) {
            return true;
        }
        boolean leftVal = find(root.left,key);
        if(leftVal == true) {
            return true;
        }
        boolean rightVal = find(root.right,key);
        if(rightVal == true) {
            return true;
        }
        return false;
    }

// 6.  判断一棵树是不是完全二叉树 boolean isCompleteTree ( Node root ); 思路: 利用层序遍历, 将节点入队, 当cur 遇到 null 之后, 如果后面还有不为空的节点就说明 该二叉树不是完全二叉树, 否则是.

//判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue 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 {
                //遇到null节点了,跳出循环
                break;
            }
        }
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                //如果null之后存在不为空的节点,说明不是完全二叉树.
                return false;
            }
        }
        return true;
    }