c语言：二叉树中序遍历
标签：在c语言二叉树中依次扫描
by小威
这周作业的主题是关于二叉树的中顺扫描。 中顺扫描是先读左子树，然后读根节点，最后读右子树。 主题的意思是，先输出左子树，再输出根节点，最后输出右子树。
主题如下：
利用链表实现二叉树结构，完成中序遍历。
首先，在头文件中定义节点结构：
类型定义结构节点{
int x；
结构节点*左；
结构节点*权限；
(bn；
接下来为了实现两个函数，函数buildTree通过读取一系列的整数来构建二叉树，使层次优先从左到右，函数outputTree输出该树的中序扫描。 两个函数的原型如下：
语音下载(bn * *根ptr )；
voidoutputtree(bn*root；
输入： n个正整数，1=N=30，用空格分隔，以-1结尾。 注意-1不包含在此树的结构中，仅用作输入的结尾符号。
输出：行遍历以空格分隔的正整数。 最后输出的元素后面有空格，没有换行符
注意： main函数已经给出，其中给出了指向树根节点的指针和整树free的过程。 buildTree函数中的所有节点都是以malloc格式生成的，如果一个节点没有左儿子或右儿子，则相应的指针应该等于NULL。
Sample:
input:
1 2 3 4 5 6 7 8 9 -1
output :
8 4 9 2 5 1 6 3 7
主题的难点是以层次优先的方式从左到右依次构建子树。 我知道可以利用递归创建子树，但不能做这个问题。 因为这个问题显然是从左到右造成的。 我该怎么办？
那就是用队列的思想制作子树。 简单来说，将每个节点的位置保存为一个数组，然后按顺序处理数组中的元素就是处理每个节点。 为每个节点打开两个子树。 要从左向右打开，请优先选择层次结构，将从左到右节点的地址顺序存储在数组中，然后在一个循环中遍历数组以创建子树。 清空的思想也是如此，总之这个问题全身都是宝啊。
另一个难点是双重指针！ 请注意，必须在函数中使用双重指针操作根节点。 否则，在函数内所做的一切都是徒劳的！ 要在函数中打开其他子树，只需要使用一个指针，但这样生成的子树与根节点分离。 必须将根节点连接到其子树。 因此，在根节点上打开空间，用双重指针给根节点分配值，将根节点的地址发送到数组中。
接下来是我的代码：
/*main.c*/
#包含
#包含
#包含
#include'tree.h '
#define MAXI 50
int main () )。
bn*路线；
BN* que[MAXI]；/*使用for free * /
int head=0；/* OFF * /
int tail=1； /*tail of que*/
构建树(根)；
输出树(根)；
/*the free procedure*/
que[0]=根；
wile (头！=tail ) {
if(que[head]-left！=空) {
que[tail]=que[head]-left；
tail=(tail1) % MAXI；
}
if(que[head]-right！=空) {
que[tail]=que[head]-right；
tail=(tail1) % MAXI；
}
free(que[head]；
head=(head1) % MAXI；
}
返回0；
}
/*tree.h*/
#包含
#包含
#define MAXI 50
类型定义结构节点{
int x；
结构节点*左；
结构节点*权限；
(bn；
voidbuildtree (bn * *根ptr ) {
BN* p1；
BN* a[MAXI]；
*rootptr=malloc(sizeof(bn )；
a[0]=*根ptr；
int head=0；
int tail=1；
扫描(' % d )，(*rootptr )-x )；
(*根ptr )-left=NULL；
(*根ptr )-right=NULL；
wile(1) {
int val；
扫描(' % d '，val )；
if(val==-1 ) {
布雷克；
} else {
P1=malloc(sizeof ) bn )；
p1-x=val；
a[tail]=p1；
tail=(tail1) % MAXI；
a[head]-left=p1；
p1-left=NULL；
p1-right=NULL；
}
扫描(' % d '，val )；
if(val==-1 ) {
布雷克；
} else {
P1=malloc(sizeof ) bn )；
p1-x=val；
a[tail]=p1；
tail=(tail1) % MAXI；
a[head]-right=p1；
p1-left=NULL；
p1-right=NULL；
}
head=(head1) % MAXI；
}
}
voidoutputtree(bn*root ) {
bn*P1=路线；
if(P1==null ) {
返回；
}
输出树(P1-left )；
printf('%d '，p1-x )；
输出树(P1-right )；
}
以上内容都是本人的观点，欢迎大家批评和指导，我们一起探讨！