第1关:二叉树的创建 100 学习内容 参考答案 记录 评论72 任务描述 本关任务:利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。 相关知识 为了完成本关任务,你需要掌握:1.二叉树的先序遍历,2.如何创建一棵二叉树,3.二叉树的中序遍历,4.二叉树的二叉链表存储表示。 二叉树的先序遍历 先序遍历preorder traversal是指按照先根结点,再左子树,最后右子树的次序访问二叉树中所有的结点,使得每个结点被访问且仅被访问一次。 例:图1表示一棵二叉树,先序遍历的结果为ABCDEF。
时间: 2025-05-23 07:07:14 浏览: 54
### 如何利用先序遍历创建二叉树并获取其中序遍历结果
#### 创建二叉树的过程
通过先序遍历的方式构建二叉树时,可以依据输入的字符流来判断是否需要创建当前节点。如果遇到 `'#'` 字符,则表示该位置无需创建节点;否则,创建一个新的节点并将对应的字符作为其数据部分[^2]。
以下是基于 C 语言实现的一个简单例子:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 使用先序递归方式创建二叉树
void CreateBiTree(BiTree *T) {
char ch;
scanf(" %c", &ch);
if (ch == '#') {
*T = NULL; // 如果读取的是 '#',则设置当前节点为空
} else {
*T = (BiTNode *)malloc(sizeof(struct BiTNode)); // 否则分配内存给新节点
(*T)->data = ch; // 设置节点的数据域
CreateBiTree(&((*T)->lchild)); // 递归创建左子树
CreateBiTree(&((*T)->rchild)); // 递归创建右子树
}
}
```
#### 中序遍历算法
对于已经构建好的二叉树,可以通过中序遍历来访问各个节点,并按特定顺序输出它们的内容。中序遍历遵循“左-根-右”的原则,即先处理左子树,接着是根节点本身,最后才是右子树[^3]。
下面是执行中序遍历操作的具体函数定义:
```c
void InOrderTraverse(BiTree T) {
if (T != NULL) {
InOrderTraverse(T->lchild); // 首先进行左子树的中序遍历
printf("%c ", T->data); // 输出当前节点的数据
InOrderTraverse(T->rchild); // 接着进行右子树的中序遍历
}
}
```
将以上两段代码结合起来就可以完成整个流程——先是根据指定规则建立起一棵完整的二叉树实例,然后再调用相应的遍历方法打印出它的内部结构信息。
#### 完整程序示例
下面给出一个综合性的完整源码清单用于演示这一过程的实际效果:
```c
int main() {
BiTree T;
printf("请输入先序序列(以‘#’代表空节点):\n");
CreateBiTree(&T);
printf("\n中序遍历的结果为:\n");
InOrderTraverse(T);
return 0;
}
```
运行这个程序之后,用户可以根据提示提供一组合法的先序序列字符串,随后系统便会自动生成匹配的目标二叉树模型以及对应于它自身的标准中序表达形式。
---
阅读全文
相关推荐


















