PTA（树和二叉树）2-2 求根结点到x结点的路径

2-2 求根结点到x结点的路径

分数 4

作者 王东

单位 贵州师范学院

求根结点到x结点的路径（假定结点不重复）。

输入样例：

输入一行字符序列先序递归构建二叉树。每个字符对应一个结点，#表示空结点。第二行输入一个结点值x。

1
2
52#3##41##6##
3

输出样例：

输出从根到结点x的路径。

1
5 2 3

我的错误答案

测试点 提示 内存(KB) 用时(ms) 结果 得分
0 308 2 答案错误 0 / 2
1 520 2 答案正确 2 / 2 
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
#include <iostream>

using namespace std;

typedef struct BTNode {
    int data;
    BTNode *lchild, *rchild;
};

BTNode* CreateBTree(BTNode *p) {
    char c;
    cin >> c;
    int num; // 用于存输入字符对应的数字
    if (c == '#') {
        return NULL;
    } else {
        num = c - '0';
    }
    p->data = num;
    // 创建左右子树
    p->lchild = CreateBTree(p->lchild);
    p->rchild = CreateBTree(p->rchild);
    return p;
}

// 先序遍历
void inTraverse(BTNode *p, int x, bool isOver) {
    if (p == NULL) {
        return;
    }
    if (isOver == true) {
        return;
    }
    if (p->data == x) {
        isOver = true;
    }
    cout << p->data << " ";
    inTraverse(p->lchild, x, isOver);
    inTraverse(p->rchild, x, isOver);
}

int main() {
    BTNode *root;
    root = CreateBTree(root);
    int x;
    cin >> x;
    bool isOver = false;
    inTraverse(root, x, isOver);
}

1. 创建节点时未分配内存

CreateBTree 函数中，参数 p 是未初始化的指针（传入的 root 未分配内存），直接对 p->data 赋值会导致空指针访问（段错误）。

修正：在创建节点时，需先用 new 分配内存：

2.函数参数 isOver 传递方式错误

inTraverse 函数中，isOver 是按值传递的局部变量，递归中修改其值不会影响外层调用（无法终止遍历）。

修正：通过引用传递（&）让修改生效

3.我发现致命的错误

如果x在右子树上，但是把左子树上的还是输出了，应该不输出