C语言中如何实现二叉树的创建和不同遍历方法?
发布网友
发布时间:2024-05-08 20:46
我来回答
共1个回答
热心网友
时间:2024-05-12 16:55
深入理解二叉树的遍历,让我们通过C语言实现非递归遍历算法,首先,定义结构体和基本函数如下:
<stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct node *lchild, *rchild;
} treetp, tree;</
函数`create(treetp t, int c)`用于创建新的节点,输入节点和整数:
treetp create(treetp t, int c) {
treetp p, di;
while (c != 0) {
scanf("%d", &c);
if (t == 0) {
t = (treetp)malloc(sizeof(tree));
t->lchild = t->rchild = 0;
t->data = c;
} else {
p = t;
while (p != 0) {
di = p;
if (c < p->data) {
p = p->lchild;
} else {
p = p->rchild;
}
if (c < di->data) {
treetp NEWdi = (treetp)malloc(sizeof(tree));
di->lchild = NEWdi;
NEWdi->lchild = NEWdi->rchild = 0;
NEWdi->data = c;
} else {
treetp NEWdi = (treetp)malloc(sizeof(tree));
di->rchild = NEWdi;
NEWdi->lchild = NEWdi->rchild = 0;
NEWdi->data = c;
}
}
++number;
}
}
printf("叶子的数量:%d</", number);
return t;
}</
接下来,我们分别实现三种遍历方法:前序、中序和后序遍历,它们的逻辑递归地调用自身:
void print1(treetp t) {
if (t != 0) {
printf("%d", t->data);
print1(t->lchild);
print1(t->rchild);
}
}
void print2(treetp t) {
if (t != 0) {
print2(t->lchild);
printf("%d", t->data);
print2(t->rchild);
}
}
void print3(treetp t) {
if (t != 0) {
print3(t->lchild);
print3(t->rchild);
printf("%d", t->data);
}
}</
在主函数中,我们调用这些函数展示非递归遍历的效果:
int main() {
treetp t = 0, r;
r = create(t, 0);
printf("前序排列:</");
print1(r);
printf("中序排列:</");
print2(r);
printf("后序排列:</");
print3(r);
return 0;
}
</
以上就是C语言实现的二叉树非递归遍历算法,通过这个实例,希望你对二叉树遍历有更深入的理解。如果你有任何疑问或想要进一步探讨,欢迎随时提问。