#include
#include
#include
#define?NULL?0
#define?OVERFLOW?0
#define?MAXLEN?1000

typedef?struct?BiTNode{
	char?data;
	struct?BiTNode?*?lchild?*?rchild;		//左右孩子指針
}BiTNode?*?BiTree;



struct?node{?
	BiTree?vec[MAXLEN];
????int?fr;?
????????
}?q;
?

int?count=0;



//按先序輸入二叉樹結(jié)點(diǎn)的值
bool?CreateBiTree（BiTree?&T）?{
	char?ch;
????scanf（“%c“&ch）;
????
	if?（ch==‘?‘）?	
		T?=?NULL;
		
????else?{
???????if?（!（T?=?（BiTNode?*）malloc（sizeof（BiTNode））））
??????????exit（OVERFLOW）;
??????T->data?=?ch;???????????????????????//?生成根結(jié)點(diǎn)
	?
??????CreateBiTree（T->lchild）;		//?構(gòu)造左子樹
??????CreateBiTree（T->rchild）;		//?構(gòu)造右子樹
????}
??return?true;
}?




void?Preorder?（BiTree?T）
??????????????????
{????????????????????//?先序遍歷二叉樹?
???if?（T）?{
??????printf（“%c??“T->data?）;??????????//?訪問根結(jié)點(diǎn)
??????Preorder（T->lchild）;?//?遍歷左子樹
??????Preorder（T->rchild）;//?遍歷右子樹
???}
}


void?Inorder?（BiTree?T）
??????????????????
{????????????????????//?中序遍歷二叉樹?
???if?（T）?{
??????
?????Inorder（T->lchild）;?//?遍歷左子樹
	?printf（“%c??“T->data?）;??????????//?訪問根結(jié)點(diǎn)
?????Inorder（T->rchild）;//?遍歷右子樹
???}
}

void?Postorder?（BiTree?T）
??????????????????
{????????????????????//?后序遍歷二叉樹?
???if?（T）?{
??????
?????Postorder（T->lchild）;?//?遍歷左子樹
?????Postorder（T->rchild）;//?遍歷右子樹?
	?printf（“%c??“T->data?）;??????????//?訪問根結(jié)點(diǎn)
???}
}





//先序非遞歸算法
void?preorder（?BiTree??b）
??{?
	BiTree?stack[1000];
	BiTree?p;
????

	int?top;??
????if?（b!=NULL）
?????{
		?top=1;						//根結(jié)點(diǎn)入棧
?????????stack[top]=b;
?????????while?（top>0）				?//棧不為空時循環(huán)
?????????{
			??p=stack[top];			//退棧并訪問該結(jié)點(diǎn)
??????????????top--;
??????????????printf（“%c??“p->data）;
			??if?（p->rchild!=NULL）?????//右孩子入棧
??????????????{?
				??top++;
??????????????????stack[top]=p->rchild;
			??}
??????????????if?（p->lchild!=NULL）????//左孩子入棧?
??????????????{
				??top++;
??????????????????stack[top]=p->lchild;
??????????????}
?????????}
?????}
}


//中序非遞歸算法
void?inorder（?BiTree??b）
??{?
	BiTree?stack[1000]p;
?????int?top=0;??
?????p=b;
?????do
???????{?
		???while?（p!=NULL）????????//掃描所有左結(jié)點(diǎn)，并入棧
????????????{?
			???top++;
???????????????stack[top]=p;
???????????????p=p->lchild;
????????????}
			if?（top>0）?
????????????{?
				p=stack[top];?
								//p所指結(jié)點(diǎn)為無左子樹的結(jié)點(diǎn)或其左子樹已遍歷過
?????????????????top--;
?????????????????printf（“%c??“p->data）;		//訪問結(jié)點(diǎn)
?????????????????p=p->rchild;???????????????//掃描右子樹
?????????????}
????????}?while?（p!=NULL||top!=0）;
???}



//后序非遞歸算法
void?postorder（?BiTree?b）
??{?
	BiTree?stack[1000]p;
????int?tag[1000]?top=0;??
????p=b;
????do
?????{?
		?while（p!=NULL）????????//掃描所有左結(jié)點(diǎn)，并入棧
???????????{?
			???top++;
			???tag[top]=0;
???????????????stack[top]=p;
???????????????p=p->lchild;
???????????}
								//p所指結(jié)點(diǎn)為無左子樹的結(jié)點(diǎn)或其左子樹已遍歷過
??????????while?（（top>0）?&&?tag[top]==1）??
															//?p的左右子樹都訪問過
??????????{?
		????????printf（“%c??“?stack[top]?->dat

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????4405??2008-11-15?20:20??建樹&遍歷&深度&查找\Debug\depth.obj

????.......????168049??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\PrInPoOrder.exe

????.......????194360??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\PrInPoOrder.ilk

????.......?????14204??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\PrInPoOrder.obj

????.......????222380??2004-11-24?10:14??建樹&遍歷&深度&查找\Debug\PrInPoOrder.pch

????.......????435200??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\PrInPoOrder.pdb

????.......?????41984??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\vc60.idb

????.......?????53248??2004-11-24?10:57??建樹&遍歷&深度&查找\Debug\vc60.pdb

????.......????163904??2008-11-09?16:42??建樹&遍歷&深度&查找\Debug\遞歸遍歷.exe

?????文件?????172160??2008-11-09?16:42??建樹&遍歷&深度&查找\Debug\遞歸遍歷.ilk

????.......????222348??2008-11-09?16:42??建樹&遍歷&深度&查找\Debug\遞歸遍歷.pch

????.......????345088??2008-11-09?16:42??建樹&遍歷&深度&查找\Debug\遞歸遍歷.pdb

?????文件???????5797??2008-11-23?00:14??建樹&遍歷&深度&查找\PrInPoOrder.cpp

?????文件???????3461??2004-11-24?10:57??建樹&遍歷&深度&查找\PrInPoOrder.dsp

?????文件????????547??2004-11-24?10:58??建樹&遍歷&深度&查找\PrInPoOrder.dsw

?????文件??????50176??2004-11-24?10:58??建樹&遍歷&深度&查找\PrInPoOrder.ncb

????.......?????48640??2004-11-24?10:58??建樹&遍歷&深度&查找\PrInPoOrder.opt

?????文件???????1216??2004-11-24?10:57??建樹&遍歷&深度&查找\PrInPoOrder.plg

????.......??????4311??2008-11-09?16:43??建樹&遍歷&深度&查找\遞歸遍歷.dsp

?????文件????????541??2008-11-09?16:41??建樹&遍歷&深度&查找\遞歸遍歷.dsw

????.......?????33792??2008-11-09?16:43??建樹&遍歷&深度&查找\遞歸遍歷.ncb

?????文件??????48640??2008-11-09?16:43??建樹&遍歷&深度&查找\遞歸遍歷.opt

?????文件???????1294??2008-11-09?16:42??建樹&遍歷&深度&查找\遞歸遍歷.plg

?????目錄??????????0??2009-04-03?01:04??建樹&遍歷&深度&查找\Debug

?????目錄??????????0??2009-04-03?01:04??建樹&遍歷&深度&查找

-----------?---------??----------?-----??----

??????????????2235745????????????????????25