C++代码实现【问题描述】一棵具有n个结点的二叉树采用顺序存储结构,设计算法对该二叉进行前序遍历。并进行测试 【输入形式】二叉树的顺序存储序列 【输出形式】二叉树的前序遍历 【样例输入】ABC DE F G 【样例输出】ABDFCEG
时间: 2023-12-03 22:03:39 浏览: 121
二叉树已知前序和中序遍历,求后序遍历的C++代码实现
4星 · 用户满意度95%
下面是 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_SIZE 100
typedef struct {
char data;
int parent;
} TreeNode;
// 构建二叉树
void CreateTree(TreeNode tree[], char data[], int n) {
int i, j;
for (i = 0; i < n; i++) {
tree[i].data = data[i];
tree[i].parent = -1;
}
for (i = 1; i < n; i++) {
j = (i - 1) / 2; // 父结点下标
tree[i].parent = j;
}
}
// 前序遍历
void PreOrder(TreeNode tree[], int i) {
printf("%c", tree[i].data);
if (2 * i + 1 < MAX_TREE_SIZE && tree[2 * i + 1].data != '\0') {
PreOrder(tree, 2 * i + 1);
}
if (2 * i + 2 < MAX_TREE_SIZE && tree[2 * i + 2].data != '\0') {
PreOrder(tree, 2 * i + 2);
}
}
int main() {
TreeNode tree[MAX_TREE_SIZE];
char data[MAX_TREE_SIZE];
int n, i;
printf("请输入二叉树的顺序存储序列:");
gets(data);
n = strlen(data);
CreateTree(tree, data, n);
printf("前序遍历结果为:");
PreOrder(tree, 0);
printf("\n");
return 0;
}
```
使用方法:
1. 编译运行上述代码;
2. 根据提示输入二叉树的顺序存储序列,例如 `ABC DE F G`;
3. 程序将输出二叉树的前序遍历结果,例如 `ABDFCEG`。
注意事项:
1. 二叉树的顺序存储序列中,空结点使用空格或其他非字母字符表示,例如上述例子中的 ` `;
2. 二叉树的顺序存储结构最多支持100个结点,可以根据需要修改宏定义 `MAX_TREE_SIZE`。
阅读全文