什么是树的孩子表示法？
树的孩子表示法（Child-Sibling Representation），也称为左孩子右兄弟表示法（Left-Child Right-Sibling Representation），是一种用于表示树结构的常见方法。在这种表示法中，每个节点包含两个指针，分别指向其第一个孩子节点和其兄弟节点。这样的表示方法适合描述不同的树结构，如二叉树和多叉树等。
具体地，对于一个节点而言，其第一个孩子节点可以通过其左指针找到，而其兄弟节点可以通过其右指针找到。如果一个节点没有孩子节点，那么其左指针指向空，如果一个节点没有兄弟节点，那么其右指针指向空。
树的孩子表示法可以有效地描述树的结构，尤其是在需要进行树的遍历和搜索等操作时，具有一定的优势。
#include <iostream>
#include <vector>
using namespace std;
// 树节点的结构体定义
struct TreeNode {
int val;
TreeNode* firstChild; // 指向第一个孩子节点
TreeNode* nextSibling; // 指向兄弟节点
TreeNode(int x) : val(x), firstChild(NULL), nextSibling(NULL) {}
};
// 建立一棵树
TreeNode* buildTree() {
int n, val;
cout << "请输入节点个数: ";
cin >> n;
vector<TreeNode*> nodes(n); // 存放每个节点的指针
cout << "请依次输入每个节点的值: ";
for (int i = 0; i < n; i++) {
cin >> val;
nodes[i] = new TreeNode(val);
}
int rootIndex, parentIndex, childIndex;
cout << "请依次输入每个节点的父节点编号（根节点编号为 0）: ";
for (int i = 1; i < n; i++) {
cin >> parentIndex;
childIndex = i;
// 将当前节点作为其父节点的孩子节点或兄弟节点
if (nodes[parentIndex]->firstChild == NULL) {
nodes[parentIndex]->firstChild = nodes[childIndex];
} else {
TreeNode* sibling = nodes[parentIndex]->firstChild;
while (sibling->nextSibling != NULL) {
sibling = sibling->nextSibling;
}
sibling->nextSibling = nodes[childIndex];
}
}
return nodes[0]; // 返回根节点指针
}
// 先序遍历输出树
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->firstChild);
preorderTraversal(root->nextSibling);
}
int main() {
TreeNode* root = buildTree();
cout << "先序遍历输出树的节点值: ";
preorderTraversal(root);
return 0;
}在上面的示例中，我们首先定义了一个树节点的结构体，其中包含了节点的值 val、指向第一个孩子节点的指针 firstChild 和指向兄弟节点的指针 nextSibling。
接下来，我们定义了一个 buildTree() 函数，用于通过输入建立一棵树。在该函数中，我们首先输入节点个数和每个节点的值，并存放到一个 vector 中。然后，我们逐个输入每个节点的父节点编号，并将当前节点作为其父节点的孩子节点或兄弟节点。最后，我们返回根节点的指针。
最后，我们定义了一个 preorderTraversal() 函数，用于先序遍历输出树的节点值。在该函数中，我们首先输出当前节点的值，然后递归遍历其第一个孩子节点和兄弟节点。
代码2：
#include <iostream>
using namespace std;
// 树节点的结构体定义
struct TreeNode {
int val;
TreeNode* firstChild; // 指向第一个孩子节点
TreeNode* nextSibling; // 指向兄弟节点
TreeNode(int x) : val(x), firstChild(NULL), nextSibling(NULL) {}
};
// 树节点的个数
const int MAX_N = 100;
// 存放每个节点的指针
TreeNode* nodes[MAX_N];
// 当前节点编号
int nodeIndex = 0;
// 建立一棵树
TreeNode* buildTree() {
int n, val, parentIndex, childIndex;
cout << "请输入节点个数: ";
cin >> n;
cout << "请依次输入每个节点的值: ";
for (int i = 0; i < n; i++) {
cin >> val;
nodes[i] = new TreeNode(val);
}
cout << "请依次输入每个节点的父节点编号（根节点编号为 0）: ";
for (int i = 1; i < n; i++) {
cin >> parentIndex;
childIndex = i;
// 将当前节点作为其父节点的孩子节点或兄弟节点
if (nodes[parentIndex]->firstChild == NULL) {
nodes[parentIndex]->firstChild = nodes[childIndex];
} else {
TreeNode* sibling = nodes[parentIndex]->firstChild;
while (sibling->nextSibling != NULL) {
sibling = sibling->nextSibling;
}
sibling->nextSibling = nodes[childIndex];
}
}
return nodes[0]; // 返回根节点指针
}
// 先序遍历输出树
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->firstChild);
preorderTraversal(root->nextSibling);
}
int main() {
TreeNode* root = buildTree();
cout << "先序遍历输出树的节点值: ";
preorderTraversal(root);
return 0;
}在这个示例代码中，我们使用一个 nodes 数组来存放每个节点的指针，其大小为常量 MAX_N。在建立树时，我们先输入节点个数和每个节点的值，并将其存放到 nodes 数组中。然后，我们逐个输入每个节点的父节点编号，并将当前节点作为其父节点的孩子节点或兄弟节点。最后，我们返回根节点的指针。
在 preorderTraversal() 函数中，我们同样使用了递归的方式进行先序遍历，并输出当前节点的值、其第一个孩子节点和兄弟节点的值。
