二叉木におけるシーケンス遍歴非再帰アルゴリズム

#include<iostream>

using namespace std;

typedef char ElemType;

//        
typedef struct BiTreeNode{
  ElemType value;
  BiTreeNode *lChild,*rChild;
}BiTreeNode,*BiTree;

//      
typedef struct StNode{
  BiTree elem;
  StNode *link;
}StNode;

//     
void CreateBiTree(BiTreeNode *&root)
{
  char data;
  cout<<"        #  
";
  cin>>data;
  if(data!='#')
  {
     BiTreeNode *newNode=(BiTreeNode *)malloc(sizeof(BiTreeNode));
     newNode->value=data;
     root=newNode;
     CreateBiTree(newNode->lChild);
     CreateBiTree(newNode->rChild);
  }
  else
  {
     root=NULL;
  }
}

//    
void visit(BiTreeNode *node)
{
  cout<<node->value<<"
";
}

//          
void InOrder(BiTree root)
{
  StNode *stackTop=NULL;
  BiTreeNode *ptr=root;
  StNode *q=NULL;
  while(ptr!=NULL||stackTop!=NULL)
  {  
    //ptr         
    while(ptr!=NULL)
    {
      q=(StNode*)malloc(sizeof(StNode));
      if(q==NULL)return;
      q->elem=ptr;
      q->link=stackTop;
      stackTop=q;
      ptr=ptr->lChild;
    }
    q=stackTop;
    stackTop=q->link;
    visit(q->elem);
    ptr=q->elem->rChild;
    free(q);
  }
}

int main()
{
  BiTree root=NULL;
  CreateBiTree(root);
  InOrder(root);
  return 0;
}