本文主要是介绍华为od真题2023-C卷-三叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
定义构造三叉搜索树规则如下:
每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。查找的规则是:
- 1.如果数小于节点的数减去500，则将数插入节点的左子树
- 2.如果数大于节点的数加上500，则将数插入节点的右子树
- 3.否则，将数插入节点的中子树
给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。
输入描述
第一行为一个数N，表示有N个数，1<=N<=10000
第二行为N个空格分隔的整数，每个数的范围为[1,10000]
输出描述
输出树的高度(根节点的高度为1)
示例1
输入
5
5000 2000 5000 8000 1800
输出
3
/*** 根节点*/static Node root;/*** 节点类*/static class Node {int value;Node left, middle, right;public Node(int value) {this.value = value;left = null;middle = null;right = null;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();for (int i = 0; i < N; i++) {int num = in.nextInt();insert(num);//插入到三叉树中}int height = getHeight(root);//获取树的高度System.out.println(height);}/*** 获取树的高度** @param root 根节点* @return 返回树的高度*/private static int getHeight(Node root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int middleHeigth = getHeight(root.middle);int rightHeighth = getHeight(root.right);return 1 + Math.max(Math.max(leftHeight, middleHeigth), rightHeighth);}/*** 插入节点** @param num 待插入的值*/private static void insert(int num) {root = insertRec(root, num);}/*** 递归插入节点** @param root 当前节点* @param value 待插入的值* @return 返回插入后的节点*/private static Node insertRec(Node root, int value) {if (root == null) {return new Node(value);}if (value < root.value - 500) {root.left = insertRec(root.left, value);} else if (value > root.value + 500) {root.right = insertRec(root.right, value);} else {root.middle = insertRec(root.middle, value);}return root;}解题思路
- 定义一个节点类 Node，包含节点值 value 和三个子节点 left、middle、right。
- 定义一个静态的根节点 root。
- 实现插入节点的方法 insert，采用递归方式实现。根据规则将新数插入到合适的子树中。
- 实现计算树高度的方法 getHeight，同样采用递归方式，返回以当前节点为根的子树的高度。
这篇关于华为od真题2023-C卷-三叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
