用C++编写程序,有一棵树,其结点的值为互不相同的正整数,这棵树用孩子兄弟表示法做存储结构,现输入一个正整数x。若树中存在值为x的结点,则输出该结点第2个孩子的值,若树中不存在值为x的结点,则输出:“no this node”,若树中值为x的结点没有孩子,或只有一个孩子,则输出:“no child of NO.2”。输入描述:第一行是若干个正整数或“-1”组成的序列,是该树对应的二叉树(将该树转化成的二叉树)的扩展二叉树前序遍历序列,其中的“-1”表示空。第二行,一个正整数,表示x的值。 输出描述:树中值为x的结点第2个孩子的值。若树中不存在值为x的结点,则输出:“no this node”,若树中值为x的结点没有孩子,或只有一个孩子,则输出:“no child of NO.2”
时间: 2023-06-24 21:04:12 浏览: 82
以下是一份 C++ 代码,使用了孩子兄弟表示法来存储树的结构:
```cpp
#include <iostream>
using namespace std;
const int MAXN = 10005;
struct Node {
int value;
int left_child;
int right_sibling;
} nodes[MAXN];
int find_node(int root, int x) {
if (root == -1) {
return -1;
}
if (nodes[root].value == x) {
return root;
}
int child = find_node(nodes[root].left_child, x);
if (child != -1) {
return child;
}
return find_node(nodes[root].right_sibling, x);
}
int find_second_child(int root) {
if (root == -1 || nodes[root].left_child == -1) {
return -1;
}
int child = nodes[nodes[root].left_child].right_sibling;
if (child == -1) {
cout << "no child of NO.2" << endl;
return -1;
}
int second_child = nodes[child].right_sibling;
if (second_child == -1) {
cout << "no child of NO.2" << endl;
return -1;
}
return nodes[second_child].value;
}
int main() {
int root, n, x;
cin >> root >> n;
for (int i = 0; i < n; i++) {
int p, l, r;
cin >> p >> l >> r;
nodes[i].value = i + 1;
nodes[i].left_child = l - 1;
nodes[i].right_sibling = r - 1;
}
cin >> x;
int node = find_node(root - 1, x);
if (node == -1) {
cout << "no this node" << endl;
} else {
int second_child = find_second_child(node);
if (second_child != -1) {
cout << second_child << endl;
}
}
return 0;
}
```
首先我们定义了一个结构体 `Node` 来表示树的结点,其中 `value` 表示结点的值,`left_child` 表示该结点的第一个孩子在数组中的下标,`right_sibling` 表示该结点的下一个兄弟结点在数组中的下标。数组 `nodes` 用来存储树的结构。
`find_node` 函数用来查找值为 `x` 的结点在树中的位置,它使用了递归进行深度优先搜索。
`find_second_child` 函数用来查找给定结点的第二个孩子的值。它首先判断该结点是否存在孩子,如果不存在则直接返回;否则它会查找该结点的第一个孩子,然后再查找第二个孩子,如果第二个孩子不存在则输出提示信息并返回。
在 `main` 函数中,我们首先读入树的结构并构建树,然后读入需要查找的值 `x`,然后查找树中值为 `x` 的结点,如果不存在则输出提示信息;否则查找该结点的第二个孩子,并输出结果。
阅读全文