怎样用C语言实现先序遍历二叉树的非递归算法？？

shufeec

算法如下，谁能把我搞定C语言实现部分呀？？
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } //向左走到尽头
    pop(S,p);
    if(!StackEmpty(S))
    {
     pop(S,p);
     push(S,p->rchild); //向右一步
    }
  }//while
}//PreOrder_Nonrecursive

shufeec

谁帮帮我呀。。。

lordbyorn

You have done all, what do you want further?

shufeec

好了，自己搞定了。。。。

libinary

算法已经很清楚了，用堆栈实现，自己写一个堆栈就行了。

1. 
   
2. Bitree *stack[100];
   
3. int top = 0;
   
4. 
   
5. void
   
6. push(Bitree *p)
   
7. {
   
8.   stack[top++] = p;
   
9. }
   
10. 
    
11. Bitree *
    
12. pop(void)
    
13. {
    
14.   return stack[--top];
    
15. }
    
16. 
    
17. int
    
18. StackEmpty(void)
    
19. {
    
20.   return top;
    
21. }
    

复制代码

这里的代码只是一个示意，很不完整，比如push、pop里没有范围检查，堆栈是固定大小的，等等。
堆栈写好了把你那个函数稍微改一下就行了。

harrypotter

用队列也可以，通过层次遍历，先让root入列，判断有无child,有让child如列,访问root,root出列,检察第一层的接点(child)有无child。依次类推。直到遍历最后一层。