利用C语言实现利用二叉树创建、遍历算法,编写程序,创建一颗二叉树,实现对二叉树的先序遍历、中序遍历和后序遍历的。
时间: 2024-01-23 07:12:54 浏览: 123
二叉树的创建与遍历,C语言实现
以下是利用C语言实现二叉树创建、遍历算法的程序,包括创建二叉树、先序遍历、中序遍历和后序遍历:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 先序遍历
void preOrder(BiTree T) {
if (T != NULL) {
printf("%c ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
// 中序遍历
void inOrder(BiTree T) {
if (T != NULL) {
inOrder(T->lchild);
printf("%c ", T->data);
inOrder(T->rchild);
}
}
// 后序遍历
void lastOrder(BiTree T) {
if (T != NULL) {
lastOrder(T->lchild);
lastOrder(T->rchild);
printf("%c ", T->data);
}
}
// 创建二叉树
void createBiTree(BiTree *T) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
createBiTree(&((*T)->lchild));
createBiTree(&((*T)->rchild));
}
}
int main() {
BiTree T;
printf("请输入二叉树的先序遍历序列(#表示空结点):\n");
createBiTree(&T);
printf("先序遍历结果为:");
preOrder(T);
printf("\n中序遍历结果为:");
inOrder(T);
printf("\n后序遍历结果为:");
lastOrder(T);
printf("\n");
return 0;
}
```
在程序中,我们首先定义了二叉树的结构体,包括结点的数据域和左右子树指针。然后定义了先序遍历、中序遍历和后序遍历的函数,这些函数都是递归实现的。最后定义了创建二叉树的函数,也是递归实现的。在主函数中,我们首先输入二叉树的先序遍历序列,然后调用创建二叉树的函数创建二叉树,最后分别调用先序遍历、中序遍历和后序遍历的函数输出遍历结果。
阅读全文