华为OD机试E卷 –计算三叉搜索树的高度–24年OD统一考试（Java & JS & Python & C & C++）

文章目录

题目描述

定义构造三叉搜索树规则如下:
每个节点都存有一个数，当插入一个新的数时，从根节点Q向下寻找，直到找到一个合适的空节点插入。

查找的规则是:

给你—系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度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

说明
无

题目解析

1. 定义一个三叉树节点类，包含三个子节点（左、中、右）和一个值。
2. 定义一个插入函数，按照题目给定的规则插入新的节点。
3. 定义一个计算树高度的函数。
4. 读取输入数据，依次插入到树中。
5. 输出树的高度。

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 = None

def 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 root

def getHeight(node):
    if node is None:
        return 0
    return 1 + max(getHeight(node.left), getHeight(node.middle), getHeight(node.right))

# 读取输入
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
nums = list(map(int, data[1:]))

root = None
for 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;
  }

作者：飞码创造者