从键盘输入前序序列和中序序列,打印出此二叉树,打印出后序序列,打印出结点,打印出子结点。使用C语言写出
时间: 2023-08-18 12:06:22 浏览: 92
好的,以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct TreeNode {
char val; // 节点的值
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
};
// 根据前序序列和中序序列构建二叉树
struct TreeNode *buildTree(char *preorder, char *inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
// 创建根节点
struct TreeNode *root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->val = preorder[preStart];
// 在中序序列中找到根节点所在的位置
int i = inStart;
while (i <= inEnd && inorder[i] != root->val) {
i++;
}
// 根据中序序列的划分,递归构建左右子树
root->left = buildTree(preorder, inorder, preStart + 1, preStart + i - inStart, inStart, i - 1);
root->right = buildTree(preorder, inorder, preStart + i - inStart + 1, preEnd, i + 1, inEnd);
return root;
}
// 打印二叉树的后序序列
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
// 先遍历左子树
postorderTraversal(root->left);
// 再遍历右子树
postorderTraversal(root->right);
// 最后遍历根节点
printf("%c ", root->val);
}
// 打印二叉树的所有节点
void printNodes(struct TreeNode* root) {
if (root == NULL) {
return;
}
// 先打印根节点
printf("%c ", root->val);
// 再递归打印左子树和右子树的所有节点
printNodes(root->left);
printNodes(root->right);
}
// 打印二叉树的所有子节点
void printChildNodes(struct TreeNode* root) {
if (root == NULL) {
return;
}
// 如果左子节点或右子节点存在,则打印出来
if (root->left != NULL || root->right != NULL) {
printf("%c: ", root->val);
if (root->left != NULL) {
printf("%c ", root->left->val);
}
if (root->right != NULL) {
printf("%c ", root->right->val);
}
printf("\n");
}
// 递归打印左子树和右子树的子节点
printChildNodes(root->left);
printChildNodes(root->right);
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
// 构建二叉树
struct TreeNode *root = buildTree(preorder, inorder, 0, 5, 0, 5);
// 打印后序序列
printf("后序序列为:");
postorderTraversal(root);
printf("\n");
// 打印所有节点
printf("所有节点为:");
printNodes(root);
printf("\n");
// 打印所有子节点
printf("所有子节点为:\n");
printChildNodes(root);
return 0;
}
```
输入前序序列和中序序列,程序会构建出二叉树,并打印出后序序列、所有节点和所有子节点。注意,这里采用了递归的方式构建二叉树和遍历二叉树。
阅读全文