编写一个C语言代码,实现根据输入的二叉树前序序列(以单个字符作为一个结点的信息)和中序序列,来构 造一棵二叉树,然后输出该树的后序序列,以及该树中所有度为1的结点。
时间: 2024-04-12 09:27:10 浏览: 102
好的,下面是一个实现的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构
typedef struct Node {
char data;
struct Node* left;
struct Node* right;
} Node;
// 创建新结点
Node* createNode(char data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 根据前序序列和中序序列构造二叉树
Node* buildTree(char* preorder, char* inorder, int start, int end) {
static int preIndex = 0;
// 前序序列遍历完或起始位置大于结束位置,返回空指针
if (start > end)
return NULL;
// 创建当前结点,并将前序序列的下一个元素作为当前结点
Node* newNode = createNode(preorder[preIndex++]);
// 在中序序列中找到当前结点的位置
int inIndex;
for (int i = start; i <= end; i++) {
if (inorder[i] == newNode->data) {
inIndex = i;
break;
}
}
// 递归构造左子树和右子树
newNode->left = buildTree(preorder, inorder, start, inIndex - 1);
newNode->right = buildTree(preorder, inorder, inIndex + 1, end);
return newNode;
}
// 后序遍历二叉树
void postorderTraversal(Node* root) {
if (root == NULL)
return;
// 后序遍历左子树
postorderTraversal(root->left);
// 后序遍历右子树
postorderTraversal(root->right);
// 输出当前结点的数据
printf("%c ", root->data);
}
// 查找度为1的结点
void findNodesWithDegreeOne(Node* root) {
if (root == NULL)
return;
// 当前结点只有一个子结点
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
printf("%c ", root->data);
// 递归查找左子树和右子树中的度为1的结点
findNodesWithDegreeOne(root->left);
findNodesWithDegreeOne(root->right);
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
Node* root = buildTree(preorder, inorder, 0, sizeof(preorder) / sizeof(preorder[0]) - 1);
printf("后序序列:");
postorderTraversal(root);
printf("\n");
printf("度为1的结点:");
findNodesWithDegreeOne(root);
printf("\n");
return 0;
}
```
这段代码实现了根据输入的前序序列和中序序列构造一棵二叉树,并输出后序序列和所有度为1的结点。你可以根据需要修改前序序列和中序序列的内容来构造不同的二叉树。
阅读全文