内容: 1. 创建二叉树的二叉链表。 2. 实现二叉树的3种遍历递归算法。 步骤: 1. 创建二叉树二叉链表的结点类型,如下: typedef struct node { char data; struct node *lchild,*rchild; }BTNode; 2. 输入二叉树的先序序列,创建二叉树:输入先序序列,输出指向二叉链表的根结点的指针 BTNode *creatBiTree(char *str); 原样输出二叉树: void Dipbtnode(BTNode *b); 3. 实现二叉树的3种遍历递归算法 先序递归算法 void PreOrder1(BTNode *b); 中序递归算法 void InOrder1(BTNode *b); 后序递归算法 void PostOrder1(BTNode *b);
时间: 2024-02-09 18:09:56 浏览: 94
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
以下是C语言实现二叉树的二叉链表和三种遍历递归算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点的结构体
typedef struct node {
char data;
struct node *lchild;
struct node *rchild;
} BTNode;
// 创建二叉树
BTNode *creatBiTree(char *str) {
static int i = 0;
BTNode *p;
if (str[i] == '\0') {
return NULL;
} else {
if (str[i] == '#') {
p = NULL;
i++;
} else {
p = (BTNode *)malloc(sizeof(BTNode));
p->data = str[i];
i++;
p->lchild = creatBiTree(str);
p->rchild = creatBiTree(str);
}
}
return p;
}
// 原样输出二叉树
void Dipbtnode(BTNode *b) {
if (b != NULL) {
printf("%c", b->data);
Dipbtnode(b->lchild);
Dipbtnode(b->rchild);
}
}
// 先序遍历
void PreOrder1(BTNode *b) {
if (b != NULL) {
printf("%c", b->data);
PreOrder1(b->lchild);
PreOrder1(b->rchild);
}
}
// 中序遍历
void InOrder1(BTNode *b) {
if (b != NULL) {
InOrder1(b->lchild);
printf("%c", b->data);
InOrder1(b->rchild);
}
}
// 后序遍历
void PostOrder1(BTNode *b) {
if (b != NULL) {
PostOrder1(b->lchild);
PostOrder1(b->rchild);
printf("%c", b->data);
}
}
int main() {
char str[] = "AB#D##CE##F##";
BTNode *root = creatBiTree(str);
printf("原样输出二叉树:");
Dipbtnode(root);
printf("\n先序遍历结果:");
PreOrder1(root);
printf("\n中序遍历结果:");
InOrder1(root);
printf("\n后序遍历结果:");
PostOrder1(root);
return 0;
}
```
以上是一个简单的实现二叉树的二叉链表和三种遍历递归算法的C语言代码,你可以在本地编译运行查看结果。
阅读全文