用C语言编写1.从键盘读入字符(数字、字母或其他符号)建立一个深度不小于3层的树的孩子兄弟表存储结构,然后①分别递归先根、后根遍历该树并输出相应遍历树结点序列。
时间: 2023-08-31 22:23:09 浏览: 48
### 回答1:
以下是用C语言编写实现上述要求的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char data; // 存储结点的字符数据
struct TreeNode *first_child; // 存储第一个孩子结点的指针
struct TreeNode *next_sibling; // 存储下一个兄弟结点的指针
};
struct TreeNode *create_tree_node(char data) {
struct TreeNode *node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node->data = data;
node->first_child = NULL;
node->next_sibling = NULL;
return node;
}
struct TreeNode *build_tree() {
char ch;
struct TreeNode *node = NULL;
scanf("%c", &ch);
if (ch == '\n') {
return NULL;
}
node = create_tree_node(ch);
node->first_child = build_tree();
node->next_sibling = build_tree();
return node;
}
void preorder_traversal(struct TreeNode *node) {
if (node == NULL) {
return;
}
printf("%c ", node->data);
preorder_traversal(node->first_child);
preorder_traversal(node->next_sibling);
}
void postorder_traversal(struct TreeNode *node) {
if (node == NULL) {
return;
}
postorder_traversal(node->first_child);
postorder_traversal(node->next_sibling);
printf("%c ", node->data);
}
int main() {
struct TreeNode *root = NULL;
printf("请输入一棵树的结点序列(以回车键结束):\n");
root = build_tree();
printf("先根遍历的结果为:");
preorder_traversal(root);
printf("\n后根遍历的结果为:");
postorder_traversal(root);
printf("\n");
return 0;
}
```
代码解释:
1. 定义了一个结构体 `TreeNode` 表示树的结点,其中 `data` 字段存储结点的字符数据,`first_child` 字段存储第一个孩子结点的指针,`next_sibling` 字段存储下一个兄弟结点的指针。
2. 定义了一个 `create_tree_node` 函数用于创建一个新的树结点。
3. 定义了一个 `build_tree` 函数用于从键盘读入字符序列并建立一棵树,采用先建立第一个孩子,再建立下一个兄弟的方法建立树的结构。
4. 定义了一个 `preorder_traversal` 函数用于实现先根遍历,并采用递归的方式遍历每个结点。
5. 定义了一个 `postorder_traversal` 函数用于实现后根遍历,并采用递归的方式遍历每个结点。
6. 在 `main` 函数中调用 `build_tree` 函数建立树,然后分别调用 `preorder_traversal` 和 `postorder_traversal` 函数遍历树并输出遍历序列。
### 回答2:
首先,我们可以使用以下的结构体来表示一个孩子兄弟表的节点:
```c
typedef struct node {
char data; // 存储的数据
struct node *firstChild; // 第一个孩子节点指针
struct node *nextSibling; // 下一个兄弟节点指针
} TreeNode;
```
然后,我们可以写一个函数来递归构建深度不小于3层的树:
```c
TreeNode *buildTree() {
char c;
TreeNode *root = malloc(sizeof(TreeNode)); // 创建根节点
printf("请输入根节点的字符:");
scanf(" %c", &c);
root->data = c;
root->firstChild = NULL;
root->nextSibling = NULL;
constructTree(root);
return root;
}
void constructTree(TreeNode *root) {
char c;
printf("请输入%c节点的第一个子节点的字符:", root->data);
scanf(" %c", &c);
while (c != '#') {
TreeNode *child = malloc(sizeof(TreeNode)); // 创建子节点
child->data = c;
child->firstChild = NULL;
child->nextSibling = NULL;
if (root->firstChild == NULL) {
root->firstChild = child;
} else {
TreeNode *temp = root->firstChild;
while (temp->nextSibling != NULL) {
temp = temp->nextSibling;
}
temp->nextSibling = child;
}
constructTree(child); // 递归构建子节点的子树
printf("请输入%c节点的下一个兄弟节点的字符:", root->data);
scanf(" %c", &c);
}
}
```
接下来,我们可以编写一个函数来递归先根遍历树并输出节点序列:
```c
void preorderTraversal(TreeNode *root) {
if (root != NULL) {
printf("%c ", root->data); // 输出当前节点
preorderTraversal(root->firstChild); // 递归先根遍历第一个子节点的子树
preorderTraversal(root->nextSibling); // 递归先根遍历下一个兄弟节点的子树
}
}
```
最后,我们可以编写一个函数来递归后根遍历树并输出节点序列:
```c
void postorderTraversal(TreeNode *root) {
if (root != NULL) {
postorderTraversal(root->firstChild); // 递归后根遍历第一个子节点的子树
printf("%c ", root->data); // 输出当前节点
postorderTraversal(root->nextSibling); // 递归后根遍历下一个兄弟节点的子树
}
}
```
最后,在主函数中调用上述函数即可:
```c
int main() {
TreeNode *root = buildTree();
printf("先根遍历结果:");
preorderTraversal(root);
printf("\n");
printf("后根遍历结果:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
通过以上步骤,我们就可以实现从键盘读入字符并用孩子兄弟表存储结构建立深度不小于3层的树,然后递归先根和后根遍历该树并输出相应的结果序列。
### 回答3:
首先,我们需要定义一个树的孩子兄弟表存储结构,这个结构包含三个元素:数据域、指向第一个孩子的指针和指向下一个兄弟的指针。
接下来,我们可以按照以下步骤来实现该问题:
1. 定义一个树的节点结构体,包含字符数据域和指向孩子和兄弟节点的指针。
```c
typedef struct TreeNode{
char data;
struct TreeNode* firstChild;
struct TreeNode* nextSibling;
}TreeNode;
```
2. 编写一个函数用于创建树节点。
```c
TreeNode* createNode(char data){
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->firstChild = NULL;
node->nextSibling = NULL;
return node;
}
```
3. 编写一个函数用于建立一棵深度不小于3层的树。
```c
TreeNode* createTree(){
char data;
scanf("%c", &data);
if(data == '#'){ // 输入#表示结束
return NULL;
}
TreeNode* root = createNode(data);
root->firstChild = createTree(); // 递归创建第一个孩子
root->nextSibling = createTree(); // 递归创建下一个兄弟
return root;
}
```
4. 编写一个函数用于递归先根遍历树并输出节点序列。
```c
void preOrderTraversal(TreeNode* root){
if(root == NULL){
return;
}
printf("%c ", root->data); // 输出根节点
preOrderTraversal(root->firstChild); // 递归遍历第一个孩子
preOrderTraversal(root->nextSibling); // 递归遍历下一个兄弟
}
```
5. 编写一个函数用于递归后根遍历树并输出节点序列。
```c
void postOrderTraversal(TreeNode* root){
if(root == NULL){
return;
}
postOrderTraversal(root->firstChild); // 递归遍历第一个孩子
postOrderTraversal(root->nextSibling); // 递归遍历下一个兄弟
printf("%c ", root->data); // 输出根节点
}
```
最后,我们可以在程序主函数中进行调用和测试。
```c
int main(){
printf("请输入树的节点序列(以#表示结束):");
TreeNode* root = createTree();
printf("先根遍历:");
preOrderTraversal(root);
printf("\n后根遍历:");
postOrderTraversal(root);
return 0;
}
```
以上就是用C语言编写从键盘读入字符建立一个深度不小于3层的树的孩子兄弟表存储结构,并进行先根和后根遍历的代码。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)