华为OD机试 - 计算三叉搜索树的高度 - 二叉树（Java 2024 C卷 100分） 小咪咪 2024-05-11 09:11 22阅读 0赞 ![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center] > 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1] ### 专栏导读 ### 本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。 **刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。 ### 一、题目描述 ### 定义构造三叉搜索树规则如下: 每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入查找的规则是: 1.如果数小于节点的数减去500，则将数插入节点的左子树 2.如果数大于节点的数加上500，则将数插入节点的右子树 3.否则，将数插入节点的中子树 给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。 ### 二、输入描述 ### 第一行为一个数N，表示有N个数，1<=N<=10000 第二行为N个空格分隔的整数，每个数的范围为\[1,10000\] ### 三、输出描述 ### 输出树的高度(根节点的高度为1)。 #### 1、输入 #### 5 5000 2000 5000 8000 1800 #### 2、输出 #### 3 #### 3、说明 #### 最终构造出的树如下，高度为3。 ![在这里插入图片描述][dca2e7b18c414a749545145ae97da047.png_pic_center] ### 四、解题思路 ### 1. 定义一个三叉搜索树的节点类，包括节点的值、左子节点、中子节点和右子节点。 2. 实现一个方法来插入节点到三叉搜索树中。根据题目描述的规则，我们从根节点开始向下寻找合适的插入位置，直到找到一个合适的空节点插入。 3. 在插入过程中，我们需要不断更新树的高度。 4. 最后，输出树的高度即可。 ### 五、Java算法源码 ### public class OdTest01 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数的个数 int N = scanner.nextInt(); // 读取待插入的数 int[] nums = new int[N]; for (int i = 0; i < N; i++) { nums[i] = scanner.nextInt(); } // 构建三叉搜索树 TreeNode root = null; int height = 0; for (int num : nums) { if (root == null) { // 树为空，创建根节点 root = new TreeNode(num); height = 1; } else { // 插入新节点，并更新树的高度 int nodeHeight = insertNode(root, num, 1); height = Math.max(height, nodeHeight); } } // 输出树的高度 System.out.println(height); } // 插入节点到三叉搜索树中 private static int insertNode(TreeNode root, int num, int height) { if (root == null) { // 创建新节点 return height; } if (num < root.val - 500) { // 插入左子树 if (root.left == null) { root.left = new TreeNode(num); return height + 1; } else { return insertNode(root.left, num, height + 1); } } else if (num > root.val + 500) { // 插入右子树 if (root.right == null) { root.right = new TreeNode(num); return height + 1; } else { return insertNode(root.right, num, height + 1); } } else { // 插入中子树 if (root.middle == null) { root.middle = new TreeNode(num); return height + 1; } else { return insertNode(root.middle, num, height + 1); } } } } class TreeNode { int val; TreeNode left; TreeNode middle; TreeNode right; public TreeNode(int val) { this.val = val; } } ### 六、效果展示 ### #### 1、输入 #### 3 5000 4000 3000 #### 2、输出 #### 3 #### 3、说明 #### 最终构造出的树如下，高度为3。 ![在这里插入图片描述][642633c727474b4396b8300a3e986cb4.png_pic_center] ![在这里插入图片描述][4f2af23c8a9e42c1825c7d370600988c.png_pic_center] ?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200] ?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C] **刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。 ![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center] [986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/8f45c010e8244b3282195625c40c4b75.gif [Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473 [OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html [dca2e7b18c414a749545145ae97da047.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/2967e17595fe4c4db6f4c59bb113d152.png [642633c727474b4396b8300a3e986cb4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/d9e8f5cab4b24350aa649968ba02a5ae.png [4f2af23c8a9e42c1825c7d370600988c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/7dbac523785047cb85ca4cddbb95c904.png [OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477 [8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/fd48c3e296594dc4b492fd5c88b6b0f5.gif
还没有评论，来说两句吧...