【数据结构与算法】9. 二叉树的基本操作

🕗 发布于 2024-10-14 14:52 Java 数据结构 算法

📚博客主页：爱敲代码的小杨.

✨专栏：《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 |《MySQL探索之旅》 |《Web世界探险家》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

小杨近些在学习人工智能方面的知识,发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

文章目录

1. 二叉树的基本操作
2. 二叉树相关OJ题

前面我们了解了二叉树的基本概念，以及二叉树的三种遍历方式，今天我们来学习二叉树的基本操作

1. 二叉树的基本操作

1.1 获取树中节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
不为空，返回左子树的个数+右子树的个数+根节点

size方法：

    /**
     * 获取树种节点的个数
     * 子问题
     * @param root
     * @return
     */
    public int size(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 左子树的个数+右子树的个数+1
        int nums = size(root.left) + size(root.right) + 1;
        return nums;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int num = binaryTree.size(root); // 调用size方法
        System.out.println("二叉树的节点个数:" + num);
    }
}

1.2 获取叶子节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
如果不为空，根节点左子树和右子树为空，则返回1（只有根节点）
如果都不为空，则返回左子树的个数+右子树的个数

getLeafNodeCount方法：

    /**
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 只有头节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        int i = getLeafNodeCount(root.left);   // 左子树的个数
        int j = getLeafNodeCount(root.right);  // 右子树的个数
        return (i + j);
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int num = binaryTree.getLeafNodeCount(root); // 
        System.out.println("叶子节点的个数" + num);
    }
}

1.3 获取第K层节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
不为空，如果层数为1并且根节点不为空，则返回1
如果层数大于1，则返回根节点的左子树和右子树的k-1层之和

getKLevelNodeCount方法：

    /**
     * 获取第k层节点的个数
     * @param root 树的头节点
     * @param k 第k层
     * @return
     */
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int i = getKLevelNodeCount(root.left, k - 1);
        int j = getKLevelNodeCount(root.right, k - 1);
        return i + j;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int k = 2;
        int num = binaryTree.getKLevelNodeCount(root, k);
        System.out.println("第" + k +"层的节点个数:" + num);
    }
}

1.4 获取二叉树的高度

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
如果不为空，则计算根节点的左子树和右子树的高度
返回子树的最高层+1

getHeight方法：

    /**
     * 获取二叉树的高度
     * @param root
     * @return
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int i = getHeight(root.left); // 左子树的高度
        int j = getHeight(root.right); // 右子树的高度
        return Math.max(i, j) + 1;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int height = binaryTree.getHeight(root);
        System.out.println("二叉树的高度：" + height);
    }
}

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

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回null；
如果不为空，判断根节点的值是否为要查找的值；如果是，则返回根节点的值；
递归在左子树中查找值，如果在左子树中找到了值，则返回找到的节点；
如果没在左子树找到值，则递归在右子树中查找值，如果在右子树中找到了值，则返回找到的节点；
如果左右子树都没有找到值，则返回null

find方法：

    /**
     * 判断val是否存在
     * @param root 头节点
     * @param val 要查找的值
     * @return
     */
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 判断根节点是否是要找的数据
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }

        return null;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree();

        BinaryTree.TreeNode num = binaryTree.find(root, 'A');
        if (num == null) {
            System.out.println("没有找到要查找的值");
            return;
        }
        System.out.println(num.val);
    }
}

1.6 完整代码

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;
        E.right = H;
        C.left = F;
        C.right = G;
        return A; // 返回根节点
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        // 判断是否为空树
        if (root == null) {
            return;
        }
        // 打印当前节点的值
        System.out.print(root.val + " ");
        // 递归左子树
        preOrder(root.left);
        // 递归右子树
        preOrder(root.right);

    }

    // 中序遍历
    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 + " ");
    }

    /**
     * 获取树种节点的个数
     * 子问题
     * @param root
     * @return
     */
    public int size(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 左子树的个数+右子树的个数+1
        int nums = size(root.left) + size(root.right) + 1;
        return nums;
    }

    /**
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 只有头节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        int i = getLeafNodeCount(root.left);   // 左子树的个数
        int j = getLeafNodeCount(root.right);  // 右子树的个数
        return (i + j);
    }

    /**
     * 获取第k层节点的个数
     * @param root 树的头节点
     * @param k 第k层
     * @return
     */
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int i = getKLevelNodeCount(root.left, k - 1);
        int j = getKLevelNodeCount(root.right, k - 1);
        return i + j;
    }

        /**
         * 获取二叉树的高度
         * @param root
         * @return
         */
        public int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int i = getHeight(root.left); // 左子树的高度
            int j = getHeight(root.right); // 右子树的高度
            return Math.max(i, j) + 1;
        }

    /**
     * 判断val是否存在
     * @param root 头节点
     * @param val 要查找的值
     * @return
     */
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 判断根节点是否是要找的数据
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }

        return null;
    }
}

2. 二叉树相关OJ题

奋笔疾书中…

原文地址：https://blog.csdn.net/QQ3447387928/article/details/142914097

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：流域生态系统服务评价、水文水生态分析、碳收支、气候变化影响、制图等领域中的应用
下一篇：数据结构：红黑树

行情波动，普通人有必要开融资融券账户吗？
同时，投资者也应该在充分了解融资融券交易的特点和风险后做出决策。融资融券账户因此成为了一种杠杆交易方式，能够增加投资者的投资收益，但同时也伴随着相应的风险。最后，需要强调的是，无论是否开通融资融券交易
阅读更多2024-10-14
智能码二维码zhinengma.cn的防伪技术有哪些创新点？
智能码二维码的防伪技术不仅提高了产品的防伪溯源能力，还为企业带来了精准营销和用户互动的机会。
阅读更多2024-10-14
多级缓存架构设计
应用 Nginx 本地内存Redis 缓存JVM 内存DB接入层 Nginx：处理入口流量，用作流量分发应用层 Nginx：接近业务层，处理业务逻辑，用作热点缓存的读取Nginx 作为高性能的 Web
阅读更多2024-10-14
UM981的机械尺寸和工作条件
注：因产品会不断更新升级，最新的参数指标请参考和芯星通官方网站。图1 UM981机械尺寸。图2 UM981 机械图。图3 UM981工作条件。
阅读更多2024-10-14
【前端】Bootstrap：响应式布局与工具类
Bootstrap 作为一个强大的前端框架，不仅为开发者提供了丰富的组件，还内置了强大的响应式设计工具。这些工具使得网页能够适应不同设备的屏幕尺寸，无论是桌面、平板，还是手机，网页都能呈现最佳的用户体
阅读更多2024-10-14
Unity DOTS框架学习系列四
本文主要介绍Unity的多线程式数据导向型技术堆栈(DOTS)，将具体阐述DOTS的核心机制与概述。Unity DOTS（Data-Oriented Technical Stack）是一个面向数据的技
阅读更多2024-10-14
搭建车载仿真环境进行测试时的主要步骤和注意事项
车载仿真环境进行测试
阅读更多2024-10-14
Python知识点：基于Python工具，如何使用Brownie进行智能合约测试
Brownie是一个基于Python的智能合约开发和测试框架，它提供了一套完整的工具来帮助开发者编写、测试和部署智能合约。Brownie是一个功能强大的Python框架，它简化了智能合约的开发和测试过
阅读更多2024-10-14
【零基础学懂算法】：动态规划算法
文章首先帮助读者理解动态规划中的关键概念，如“状态”和“状态转移方程”，并深入分析如何从这些概念出发解决复杂问题。接着，文章提供了清晰的做题步骤，包括如何进行状态的填表、初始化、计算以及如何从中提取最
阅读更多2024-10-14
机器学习——解释性AI
解释性AI（XAI）是一种人工智能技术，旨在提高ML模型和AI系统决策的解释和可解释性。XAI通过揭示AI系统背后的推理、决策和预测过程，以及解释其结果和行为，使人们能够理解、相信和信任AI系统的行为
阅读更多2024-10-14

【数据结构与算法】9. 二叉树的基本操作

文章目录

1. 二叉树的基本操作

1.1 获取树中节点的个数

1.2 获取叶子节点的个数

1.3 获取第K层节点的个数

1.4 获取二叉树的高度

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

1.6 完整代码

2. 二叉树相关OJ题

相关文章