给定二叉树T(树深度不超过H<=10,深度从1开始,节点个数N<1024,节点编号1~N)的层序和中序遍历,输出T从左向右叶子节点以及树先序和后序遍历序列,用C语言写出完整代码
时间: 2023-11-30 09:02:49 浏览: 122
好的,我来给你提供一份C语言的完整代码,实现上述功能。代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1024
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int n;
int levelOrder[MAXN];
int inorder[MAXN];
TreeNode* buildTree(int levelStart, int levelEnd, int inStart, int inEnd) {
if (levelStart > levelEnd) return NULL;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = levelOrder[levelStart];
int idx;
for (idx = inStart; idx <= inEnd; ++idx) {
if (inorder[idx] == root->val) break;
}
int leftLen = idx - inStart;
root->left = buildTree(levelStart + 1, levelStart + leftLen, inStart, idx - 1);
root->right = buildTree(levelStart + leftLen + 1, levelEnd, idx + 1, inEnd);
return root;
}
void getLeaves(TreeNode *root, int *leaves, int *cnt) {
if (!root) return;
if (!root->left && !root->right) {
leaves[(*cnt)++] = root->val;
}
getLeaves(root->left, leaves, cnt);
getLeaves(root->right, leaves, cnt);
}
void preorder(TreeNode *root, int *pre, int *cnt) {
if (!root) return;
pre[(*cnt)++] = root->val;
preorder(root->left, pre, cnt);
preorder(root->right, pre, cnt);
}
void postorder(TreeNode *root, int *post, int *cnt) {
if (!root) return;
postorder(root->left, post, cnt);
postorder(root->right, post, cnt);
post[(*cnt)++] = root->val;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &levelOrder[i]);
for (int i = 0; i < n; ++i) scanf("%d", &inorder[i]);
TreeNode *root = buildTree(0, n - 1, 0, n - 1);
int leaves[MAXN], cnt = 0;
getLeaves(root, leaves, &cnt);
int pre[MAXN], preCnt = 0;
preorder(root, pre, &preCnt);
int post[MAXN], postCnt = 0;
postorder(root, post, &postCnt);
printf("Leaves: ");
for (int i = 0; i < cnt; ++i) {
printf("%d ", leaves[i]);
}
printf("\n");
printf("Preorder: ");
for (int i = 0; i < preCnt; ++i) {
printf("%d ", pre[i]);
}
printf("\n");
printf("Postorder: ");
for (int i = 0; i < postCnt; ++i) {
printf("%d ", post[i]);
}
printf("\n");
return 0;
}
```
具体实现方法与Python版本相似,主要分为三个部分:
1. 构建二叉树,采用递归方法实现。
2. 找出二叉树T从左向右的叶子节点,同样采用递归方法实现。
3. 分别输出二叉树T的先序遍历和后序遍历序列,同样采用递归方法实现。
需要注意的是,C语言中的数组需要预先指定大小,因此代码中定义了一个最大节点个数MAXN,来限制数组的大小。同时,为了避免数组越界,需要在函数参数中指定数组的实际大小,而不能直接使用数组。
最后,通过读入层序遍历和中序遍历,构建二叉树,找出叶子节点以及输出先序遍历和后序遍历序列。完整的输出结果与Python版本相同。
阅读全文