Question

一道数据结构问题，求助各位懂行的大大

void middle1(bitree root)
{
struct bitnode *stack[100];
int top=0;
while(root||top!=0)
{
while (root)
{
stack[top++]=root;
root=root->ltree ;
}
root=stack[--top];
putchar(root->data);
root=root->rtree ;
}
}
能帮我解释一下这个函数么？（最好能逐行解释）这个是不用栈做的二叉树非递归中序遍历，有点不太明白了，谢谢

Answer 1

void middle1(bitree root)
{
struct bitnode *stack[100];//模拟递归调用的栈
int top=0;//初始化栈为空
while(root||top!=0)//取出当前处理的子树的根节点，直到遍历结束
{
while (root)//先处理这个子树的左子树，这里怎么处理跟算法有关，也可以一次只处理一层
{
stack[top++]=root;
root=root->ltree ;
}
root=stack[--top];
putchar(root->data);//处理根节点
root=root->rtree ;//处理其右子树
}
}
递归算法不容易说明，举个例子模拟一下吧，假设对于以下二叉树：
1
2 3
4 5 6 7
初始栈空，root=1；
第一次循环后：root=NULL，栈为：12 | 4（这个4刚刚被弹出处理过，也即其左子树和其自身已遍历，现在处理4的右子树），top=2；
第二次循环后：root=5，栈：1 | 24 （这个2刚刚被弹出处理，现在处理其右子树），top=1；
第三次循环后：root=NULL，栈：1 | 54 （这个5刚刚被弹出处理，现在处理5的右子树），top=1；
第四次循环后：root=3，栈空，此时1的左子树已经处理完，现处理其右子树；
第五次循环后：root=NULL，栈：3 | 64 （这个6刚处理完），top=1；
第六次循环后：root=7，栈空，这时3的左子树以及3已经处理完，处理3的右子树。
第七次循环后算法结束。
上面的栈保留了栈中所有的数据，包括已经处理过但未被覆盖掉的。