数据结构-5.二叉树

扫测资讯 2024-11-16 12:07 40 0

本篇博客给大家带来的是二叉树的知识点, 其中包括面试经常会提问的真题 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<n ，左孩子序号：2i+1,

2i+2<n ，右孩子序号： 2i+2.

1.4 二叉树的存储

二叉树的存储结构 分为： 顺序存储 和 类似于链表的链式存储 。

顺序存储在下节介绍。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式 ，具体如下：

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

孩子双亲表示法后序在平衡树位置介绍， 本文采用孩子表示法来构建二叉树。

1.5 二叉树的基本操作

1.5.1 二叉树的简单创建

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。为了简单些, 此处手动创建一颗简单的二叉树. 先学习二叉树的操作, 后续再研究二叉树真正的创建方式.

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

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public void createTree() {
        TreeNode A = new TreeNode(4);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(7);
        TreeNode D = new TreeNode(1);
        TreeNode E = new TreeNode(3);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(9);
        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;
   
    }
}

再看二叉树基本操作前，再回顾下二叉树的概念， 二叉树是：

1. 空树

2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

1.5.2 二叉树的遍历

1. 前中后序遍历

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

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

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

抖音发布助手(手机版)

模板安装包

快手【自动发布】【手机版】

快手养号功能

域名采集筛选工具