查找二叉树(tree_a)

题目描述

一棵 $n$ （ $n \leqslant 100$ ）个结点的二叉树用孩子链表存储：第一行是结点个数 $n$ ，第二行是要查找的值 $x$ ，接下来 $n$ 行每行三个数，依次是结点的值、左儿子编号、右儿子编号（ $0$ 表示空，根没有直接给出）。按中序顺序（左子树 $\to$ 根 $\to$ 右子树）访问这棵树，输出值为 $x$ 的结点是第几个被访问的结点（从 $1$ 数起）。样例中树的中序序列为 $29, 12, 8, 15, 23, 5, 10$ ，值 $15$ 排第 $4$ ，故输入 $7$ 、 $15$ 和 $7$ 行结点表时输出 $4$ 。

思路

按父亲孩子表示法的二叉树特化建表：一个结点的值、左儿子、右儿子、父亲收进同一个 node[u]（C++ 是 struct Node，Python 是 Node 对象）。读入第 $i$ 行时写入 node[i] 的值和左右孩子，顺手写 node[儿子].fa = i，于是除根外每个结点的 fa 都不为 0，fa == 0 的那个点就是根，不必另开数组去判"谁没当过儿子"。再按"左 $\to$ 根 $\to$ 右"递归中序遍历，用计数器数访问名次，值等于 $x$ 时输出并停止。注意树不一定满足二叉排序树性质，不能按值二分，只能老实遍历， $O(n)$ 即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:30
# update_at: 2026-10-12 14:36

# 树的存储：父亲孩子表示法（二叉树特化）
# 一个结点的四个字段聚合成 Node 对象：值、左儿子、右儿子、父亲，
# 对应文章模板里的 val/lch/rch/fa 四个全局列表，这里收进同一个对象。
# 如何使用：
# 1. init(n)                     # 多组数据必须调用
# 2. 读入第 i 行：node[i].value/lch/rch 赋值，顺手 node[儿子].fa = i
# 3. 向下：node[u].lch / node[u].rch；向上：node[u].fa；根就是 fa == 0 的点

import sys
from collections.abc import Iterator


class Node:
    """编号 u 的结点：值 + 左右孩子 + 父亲（父亲孩子表示法的二叉树特化）。"""

    def __init__(self) -> None:
        self.value = 0  # 结点的值
        self.lch = 0    # 左儿子编号，0 表示空
        self.rch = 0    # 右儿子编号，0 表示空
        self.fa = 0     # 父亲编号；fa == 0 表示这个点是根


node: list[Node] = []  # node[u]：编号 u 的结点


def init(n: int) -> None:
    """造出 0..n 共 n+1 个结点，字段全为 0（fa == 0 正好表示"根没有父亲"）。"""
    global node
    node = [Node() for _ in range(n + 1)]


def find_root(n: int) -> int:
    """根是唯一没当过儿子的点：读入时每个儿子都写了 fa，所以 fa == 0 的就是根。"""
    return next(i for i in range(1, n + 1) if node[i].fa == 0)


def inorder(u: int) -> Iterator[int]:
    """中序遍历：左子树 -> 根 -> 右子树，依次产出结点编号。"""
    if u:
        yield from inorder(node[u].lch)  # 先走左子树
        yield u                          # 再访问根
        yield from inorder(node[u].rch)  # 最后走右子树


def solve() -> None:
    data = iter(map(int, sys.stdin.read().split()))
    n = next(data)
    target = next(data)  # 要查找的结点值

    init(n)
    for i in range(1, n + 1):
        v, l, r = next(data), next(data), next(data)
        node[i].value = v
        node[i].lch = l
        node[i].rch = r
        # 孩子一登记，父亲也顺手记下：这一步就把 fa 填好了
        if l:
            node[l].fa = i
        if r:
            node[r].fa = i

    # 中序序列里第 i 个结点的名次从 1 开始数
    rank = next(i for i, u in enumerate(inorder(find_root(n)), 1) if node[u].value == target)
    print(rank)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:14
 * update_at: 2026-10-12 14:37
 */
// main.cpp：树的存储（父亲孩子表示法的二叉树特化）+ 中序遍历计数。
//
// 一个结点的四个字段聚合成 struct：值、左儿子、右儿子、父亲。
// 对应文章《树的存储》模板里的 val[] / lch[] / rch[] / fa[] 四个全局数组，
// 这里按结点下标收进 node[u]，读入时顺手写 node[儿子].fa = 父亲，
// 于是"谁没当过儿子"不用另开数组，node[i].fa == 0 的点就是根。

#include <cstdio>

typedef long long ll;

const int maxn = 105; // 题面 n ≤ 100，按上界开

struct Node {
    ll val;   // 结点的值
    int lch;  // 左儿子编号，0 表示空
    int rch;  // 右儿子编号，0 表示空
    int fa;   // 父亲编号；fa == 0 表示这个点是根
};

Node node[maxn]; // node[u]：编号 u 的结点
int n;           // 结点个数
ll x;            // 要查找的结点值
int cnt;         // 中序访问计数器：第 cnt 个被访问的结点

// 初始化：把 0..n 全部清成 0，node[i].fa == 0 正好表示"根没有父亲"
// 模板签名保留，多组数据时必须调用
void init(int n) {
    for (int i = 0; i <= n; i++) {
        node[i] = Node{};
    }
}

// 根是唯一没当过儿子的点：读入时每个儿子都写了 fa，所以 fa == 0 的就是根
int find_root(int n) {
    for (int i = 1; i <= n; i++) {
        if (node[i].fa == 0) {
            return i;
        }
    }
    return 1; // 题面保证输入是一棵二叉树，走到这里说明输入不合法
}

// 中序遍历：左 -> 根 -> 右，一边数名次一边找值为 x 的结点
// 返回 true 表示子树里已经命中，调用方不要再往另一边走（替代 exit(0)）
bool inorder(int u) {
    if (u == 0) {
        return false;             // 0 表示空子树
    }
    if (inorder(node[u].lch)) {
        return true;              // 先走左子树
    }
    cnt++;                        // 到了根，这是第 cnt 个被访问的结点
    if (node[u].val == x) {
        printf("%d\n", cnt);
        return true;              // 命中，把"停"信号往上传
    }
    return inorder(node[u].rch);  // 最后走右子树
}

int main() {
    scanf("%d %lld", &n, &x);
    init(n);
    for (int i = 1; i <= n; i++) {
        int l, r;
        scanf("%lld %d %d", &node[i].val, &l, &r);
        node[i].lch = l;
        node[i].rch = r;
        // 孩子一登记，父亲也顺手记下：这一步就把 fa 填好了
        if (l != 0) {
            node[l].fa = i;
        }
        if (r != 0) {
            node[r].fa = i;
        }
    }

    inorder(find_root(n));
    return 0;
}