使用C语言,用顺序存储结构来存储一颗具有n个结点的二叉树,编写算法实现对该二叉树进行先序遍历,输出先序遍历序列。
时间: 2023-06-14 08:06:00 浏览: 53
假设二叉树的结点数据类型为`ElemType`,其中包含一个字符型成员变量`data`,则可以使用以下代码实现对二叉树的先序遍历:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 定义二叉树的最大结点数
// 定义二叉树结点数据类型
typedef struct BiTNode {
char data; // 数据域
} BiTNode, *BiTree;
// 创建二叉树
void createBiTree(BiTree *T, char *data, int *index) {
char ch = data[*index];
(*index)++;
if (ch == '#') { // 空结点
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode)); // 创建新结点
(*T)->data = ch;
createBiTree(&((*T)->lchild), data, index); // 递归创建左子树
createBiTree(&((*T)->rchild), data, index); // 递归创建右子树
}
}
// 先序遍历二叉树
void preOrderTraverse(BiTree T) {
if (T != NULL) {
printf("%c ", T->data); // 输出结点数据
preOrderTraverse(T->lchild); // 递归遍历左子树
preOrderTraverse(T->rchild); // 递归遍历右子树
}
}
int main() {
char data[MAX_SIZE]; // 存储二叉树结点数据的数组
int n; // 二叉树结点数
printf("请输入二叉树的结点数:");
scanf("%d", &n);
printf("请输入二叉树的结点数据(以先序遍历的顺序输入,空结点用#表示):");
for (int i = 0; i < n; i++) {
scanf(" %c", &data[i]);
}
BiTree T = NULL; // 定义二叉树的根节点
int index = 0; // 二叉树结点数据的数组下标
createBiTree(&T, data, &index); // 创建二叉树
printf("先序遍历序列为:");
preOrderTraverse(T); // 先序遍历二叉树并输出序列
printf("\n");
return 0;
}
```
在上述代码中,我们首先定义了二叉树结点的数据类型`BiTNode`,包含一个字符型数据域`data`。然后定义了一个指向`BiTNode`类型的指针`BiTree`,用来表示二叉树结点。接着,我们使用`createBiTree`函数创建了一个二叉树,该函数的输入参数包括指向二叉树根节点的指针`T`、二叉树结点数据的数组`data`,以及下标`index`,该函数使用递归的方式创建二叉树,并在遇到空结点时将其置为`NULL`。最后,我们使用`preOrderTraverse`函数对二叉树进行先序遍历,并输出遍历序列。