编写一个C程序,实现根据输入的二叉树后序序列(以单个字符作为一个结点的信息)和中序序列,来构造一棵二叉树,然后输出该树的前序序列,以及该树中所有度为1的结点,① 选择某种存储结构,建立一棵二叉树,并实现二叉树的4种遍历算法(先序、中序、后序、层序)。 ② 输入两个字符串,其长度均小于26。第一行为后序遍历,第二行为中序遍历。二叉树的结点名称以大写字母表示:A,B,C,D.......,最多26个字母。输出前续遍历的字符串。 ③ 根据后序遍历字符串和中序遍历字符串递归构造每个节点及该节点的数据域、左子树指针和右子树指针。如第一遍遍历,后序遍历字符串的最后一个字母为根,然后在中序遍历字符串中查找根字母,并记录偏移数,根字母左侧的都是左子树的节点,根的右侧都是右子树的节点。根据偏移数递归构造左子树和右子树。 ④ 输出度为1的节点。
时间: 2024-04-12 22:31:30 浏览: 181
以下是实现你所描述功能的C程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 二叉树节点结构
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据后序遍历和中序遍历构建二叉树
TreeNode* buildTree(char* inorder, char* postorder, int inStart, int inEnd, int postStart, int postEnd) {
// 递归终止条件
if (inStart > inEnd || postStart > postEnd) {
return NULL;
}
// 创建根节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = postorder[postEnd];
root->left = NULL;
root->right = NULL;
// 在中序遍历中找到根节点的位置
int rootIndex;
for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {
if (inorder[rootIndex] == root->data) {
break;
}
}
// 构建左子树和右子树
root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + (rootIndex - inStart) - 1);
root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + (rootIndex - inStart), postEnd - 1);
return root;
}
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 输出度为1的节点
void printDegreeOneNodes(TreeNode* root) {
if (root == NULL) {
return;
}
if ((root->left != NULL && root->right == NULL) || (root->left == NULL && root->right != NULL)) {
printf("%c ", root->data);
}
printDegreeOneNodes(root->left);
printDegreeOneNodes(root->right);
}
int main() {
char inorder[27];
char postorder[27];
// 输入后序遍历和中序遍历
printf("请输入后序遍历序列: ");
fgets(postorder, sizeof(postorder), stdin);
postorder[strcspn(postorder, "\n")] = '\0'; // 去除换行符
printf("请输入中序遍历序列: ");
fgets(inorder, sizeof(inorder), stdin);
inorder[strcspn(inorder, "\n")] = '\0'; // 去除换行符
int length = strlen(postorder);
// 构建二叉树
TreeNode* root = buildTree(inorder, postorder, 0, length - 1, 0, length - 1);
// 输出前序遍历序列
printf("前序遍历序列为: ");
preorderTraversal(root);
printf("\n");
// 输出度为1的节点
printf("度为1的节点为: ");
printDegreeOneNodes(root);
printf("\n");
return 0;
}
```
以上是一个基于C语言的程序,用于根据给定的后序遍历和中序遍历序列构建二叉树,并输出前序遍历序列以及度为1的节点。注意,在输入时,请确保后序遍历和中序遍历序列的长度都小于26,并且按照要求使用大写字母表示节点名称。
阅读全文