文章目录
题目描述输入描述输出描述用例题目解析JS算法源码Java算法源码python算法源码c算法源码c++算法源码
题目描述
定义构造三叉搜索树规则如下:
每个节点都存有一个数，当插入一个新的数时，从根节点Q向下寻找，直到找到一个合适的空节点插入。
查找的规则是:
如果数小于节点的数减去500，则将数插入节点的左子树如果数大于节点的数加上500，则将数插入节点的右子树·否则，将数插入节点的中子树给你—系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度Q。
输入描述
第—行为一个数N，表示有N个数，1≤N≤ 10000
第二行为N个空格分隔的整数，每个数的范围为[1,10000]
输出描述
输出树的高度（根节点的高度为1)
用例
输入
5
5000 2000 5000 8000 1800
输出
3
说明
无
输入
3
5000 4000 3000
输出
3
说明
无
输入
9
5000 2000 5000 8000 1800 7500 4500 1400 8100
输出
4
说明
无
题目解析
定义一个三叉树节点类，包含三个子节点（左、中、右）和一个值。定义一个插入函数，按照题目给定的规则插入新的节点。定义一个计算树高度的函数。读取输入数据，依次插入到树中。输出树的高度。JS算法源码
class TriTreeNode { constructor(val) { this.val = val; this.left = null; this.middle = null; this.right = null; }}function insert(root, val) { if (!root) { return new TriTreeNode(val); } if (val < root.val - 500) { root.left = insert(root.left, val); } else if (val > root.val + 500) { root.right = insert(root.right, val); } else { root.middle = insert(root.middle, val); } return root;}function getHeight(node) { if (!node) { return 0; } return 1 + Math.max(getHeight(node.left), getHeight(node.middle), getHeight(node.right));}// 读取输入const readline = require('readline').createInterface({ input: process.stdin, output: process.stdout});readline.question('', (N) => { readline.question('', (line) => { const nums = line.split(' ').map(Number); let root = null; for (const num of nums) { root = insert(root, num); } console.log(getHeight(root)); readline.close(); });});Java算法源码
import java.util.Scanner;class TriTreeNode { int val; TriTreeNode left, middle, right; TriTreeNode(int val) { this.val = val; this.left = this.middle = this.right = null; }}public class Main { public static TriTreeNode insert(TriTreeNode root, int val) { if (root == null) { return new TriTreeNode(val); } if (val < root.val - 500) { root.left = insert(root.left, val); } else if (val > root.val + 500) { root.right = insert(root.right, val); } else { root.middle = insert(root.middle, val); } return root; } public static int getHeight(TriTreeNode node) { if (node == null) { return 0; } return 1 + Math.max(getHeight(node.left), Math.max(getHeight(node.middle), getHeight(node.right))); } 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(); } TriTreeNode root = null; for (int num : nums) { root = insert(root, num); } System.out.println(getHeight(root)); }}python算法源码
class TriTreeNode: def __init__(self, val): self.val = val self.left = self.middle = self.right = Nonedef insert(root, val): if root is None: return TriTreeNode(val) if val < root.val - 500: root.left = insert(root.left, val) elif val > root.val + 500: root.right = insert(root.right, val) else: root.middle = insert(root.middle, val) return rootdef getHeight(node): if node is None: return 0 return 1 + max(getHeight(node.left), getHeight(node.middle), getHeight(node.right))# 读取输入import sysinput = sys.stdin.readdata = input().split()N = int(data[0])nums = list(map(int, data[1:]))root = Nonefor num in nums: root = insert(root, num)print(getHeight(root))c算法源码
#include <stdio.h>#include <stdlib.h>#include <limits.h>typedef struct TriTreeNode { int val; struct TriTreeNode *left, *middle, *right;} TriTreeNode;TriTreeNode* createNode(int val) { TriTreeNode* newNode = (TriTreeNode*)malloc(sizeof(TriTreeNode)); newNode->val = val; newNode->left = newNode->middle = newNode->right = NULL; return newNode;}TriTreeNode* insert(TriTreeNode* root, int val) { if (!root) { return createNode(val); } if (val < root->val - 500) { root->left = insert(root->left, val); } else if (val > root->val + 500) { root->right = insert(root->right, val); } else { root->middle = insert(root->middle, val); } return root;}int getHeight(TriTreeNode* node) { if (!node) { return 0; } return 1 + (int)(fmax(getHeight(node->left), fmax(getHeight(node->middle), getHeight(node->right))));}int main() { int N; scanf("%d", &N); int *nums = (int*)malloc(N * sizeof(int)); for (int i = 0; i < N; i++) { scanf("%d", &nums[i]); } TriTreeNode* root = NULL; for (int i = 0; i < N; i++) { root = insert(root, nums[i]); } printf("%d\n", getHeight(root)); free(nums); return 0;}c++算法源码
#include <iostream>#include <vector>#include <algorithm>using namespace std;struct TriTreeNode { int val; TriTreeNode* left, *middle, *right; TriTreeNode(int x) : val(x), left(nullptr), middle(nullptr), right(nullptr) {}};TriTreeNode* insert(TriTreeNode* root, int val) { if (!root) { return new TriTreeNode(val); } if (val < root->val - 500) { root->left = insert(root->left, val); } else if (val > root->val + 500) { root->right = insert(root->right, val); } else { root->middle = insert(root->middle, val); } return root;}int getHeight(TriTreeNode* node) { if (!node) { return 0; } return 1 + max({getHeight(node->left), getHeight(node->middle), getHeight(node->right)});}int main() { int N; cin >> N; vector<int> nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } TriTreeNode* root = nullptr; for (int num : nums) { root = insert(root, num); } cout << getHeight(root) << endl; return 0; }