非遞歸先序周遊二叉樹、非遞歸中序周遊二叉樹、非遞歸後序周遊二叉樹

 // traverse binary tree.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include<iostream>

using namespace std;

typedef struct BitNode

{

char data;

BitNode *lchild,*rchild;

}BitNode,*BT;

void CreateBT(BT &T)

{

char k;

cin>>k;

if(k=='+')

T=NULL;

else

{

T=new BitNode;

T->data=k;

CreateBT(T->lchild);

CreateBT(T->rchild);

}

}

void PreTra(BT T)

{

if(T)

{

cout<<T->data<<',';

PreTra(T->lchild);

PreTra(T->rchild);

}

}

const int M=1000;

void Pre(BT T) //先序非遞歸

{

BT top[M];

int i=-1;

BT p;//=new BitNode;

p=T;

if(!T)

return ;

top[++i]=NULL;// the bottom of top is NULL first,void the tree has only a node;

do

{

cout<<p->data<<','; //通路左子樹

if(p->rchild) //右子樹不為空則進棧

top[++i]=p->rchild;

p=p->lchild;

if(!p) //到左子樹盡頭，出棧

p=top[i--];

}while(i>=0||p);

}

void inorder(BT T)//中序非遞歸

{

if(!T)

return;

BT p=T;

BT top[M];

int i=0;

while(i>0||p)

{

if(p) //直到左子樹為空

{

top[i++]=p;

p=p->lchild;

}

else

{

p=top[--i]; //出棧，通路

cout<<p->data<<','; //

p=p->rchild;

}

}

}

void last(BT T)

{

BT top[M],p=T;

int i=0,top2[M],b; //top2用來标記是第幾次通路

while(p||i>0)

{

if(p)

{

top[i]=p;

top2[i++]=0;

p=p->lchild;

}

else

{

b=top2[--i];

p=top[i];

if(b==0) //第一次，不予通路

{

top2[i++]=1;

p=p->rchild;

}

else

{ //第二次，通路（其實質與周遊二叉樹一樣可以看作是第三次通路時輸出，

cout<<p->data<<','; //第一次，入棧，第二次，出棧（top2=0，不出），第三次，出棧）

p=NULL;

}

}

}

}

int main(int argc, char* argv[])

{

BT t;

CreateBT(t);

Pre(t);

system("pause");

return 0;

}