C语言数据结构，这个二叉树遍历为什么用这个程序可以遍历？能不能用我的例子帮我解答下，拜托啦

Question

如题所述

Answer 1

首先中序遍历二叉树的原则是 左 中 右
然后题主需要注意一点，就是图中的GetTop Push Pop三个函数
这三个函数操作的对象是栈S
其中GetTop(S,p)是获取S的栈顶元素赋值给p 并返回一个值，一般来说是0或者1 0代表获取失败 栈S中没有元素。
Pop(S,p)是弹出一个栈顶元素，赋值给p， 这里我们不需要关心它是否返回值。
Push(S,p)是压栈操作，将p的值作为一个元素压到栈S的顶部。
然后需要注意的是两个Pop操作，这里其实是处理边界问题。
接下来给出一个大概的流程
首先建立一个空栈S 并将二叉树的根节点T指针值压进栈S
然后开始主循环，判断栈S非空 由于S中有根节点T的地址作为一个指针类型数值在保存 ，故进入循环
注意接下来这个While的语句范围只有一个Push语句
从栈S中获取栈顶元素的值，获取成功并且这个值非空的情况下 将此节点的左孩子节点指针压入栈中。
那么这个While第一次循环完的结果就是 栈S中从栈顶到栈底依次为 空指针NULL 节点4指针 节点2指针 节点1指针(根节点) 四个元素
为什么是四个不是三个呢，这就是上面说的边界问题，GetTop的结果为4节点(4号指针在S的栈顶)的时候，还是会成功的获取到一个指针p 并且这个指针p不是NULL 因为p就是4号节点的指针啊。 然后会将4号节点的左孩子压入栈顶，4号节点没有左孩子，p->lchild=NULL 是初始值，故这个NULL就被压进了栈顶 所以接下来才需要这个空指针退栈操作。
我想边界问题处理了，栈也理解了，接下来的循环题主应该可以自己模拟思考了。
最终中序遍历的结果为 4 2 8 5 9 1 6 3 7