void PreOrder(BiTree T)//先序遞歸周遊
{
if(T!=NULL)
{
cout<<T->data<<" ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void SqlPreOrder(BiTree T)//先序非遞歸周遊
{
stack<BiTree> s;
BiTree p=T;
while(p || !s.empty())
{
if(p)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
p=p->rchild;
s.pop();
}
}
}
void InOrder(BiTree T)//中序遞歸周遊
{
if(T!=NULL)
{
InOrder(T->lchild);
cout<<T->data<<" ";
InOrder(T->rchild);
}
}
void SqInOrder(BiTree T)//中序非遞歸周遊
{
stack<BiTree> s;
BiTree p=T;
while(p || !s.empty())
if(p)
{
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
void PostOrder(BiTree T)//後序遞歸周遊
{
if(T!=NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data<<" ";
}
}
//後序非遞歸周遊1思路:因為後序非遞歸周遊二叉樹的順序是先通路左子樹,再通路後子樹,最後
//通路根結點。當用堆棧來存儲結點,必須厘清傳回根結點時,是從左子樹傳回的,還是從右子樹
//傳回的。是以,使用輔助指針r,其指向最近通路過的結點。
void SqlPostOrder1(BiTree T)//後序非遞歸周遊1
{
stack<BiTree> s;
BiTree p=T,r;
while(p || !s.empty())
{
if(p) //走到最左邊
{
s.push(p);
p=p->lchild;
}
else //向右
{
p=s.top();//取棧頂結點
if(p->rchild && p->rchild!=r)//如果右子樹存在,且未被通路過
{
p=p->rchild;
s.push(p);
p=p->lchild; //再走到最左
}
else //否則,通路棧頂結點并彈出
{
cout<<p->data<<" ";
r=p; //記錄該結點
s.pop();
p=NULL; //結點通路完後,重置p指針
}
}
}
}
//思路2:在結點中增加标志域,記錄是否已被通路。
void SqlPostOrder2(BiTree T)//後序非遞歸周遊2
{
stack<BiTree> s;
BiTree p=T;
while(p || !s.empty())
{
if(p && p->lvisited==0) //左走,且左子樹未被通路
{
p->lvisited=1;
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
if(p->rchild!=NULL && p->rvisited==0)//右子樹未被通路,右走一步
{
p->rvisited=1;
p=p->rchild;
}
else //通路棧頂元素并彈棧
{
cout<<p->data<<" ";
s.pop();
if(!s.empty())
p=s.top();
else //當最後一個元素彈棧出去後,結束
return ;
}
}
}
}