用棧實現二叉樹先序遍歷的非遞歸算法實踐題

　　/*syc*/

　　#include

　　#include

　　typedef char DataType;

　　typedef struct node{

　　DataType data;

　　struct node *lchild*rchild;

　　}BinTNode;

　　typedef BinTNode *BinTree;

　　int count;

　　void CreateBinTree(BinTree *T);

　　void PreorderN(BinTree T);

　　#define StackSize /*假定預分配的棧空間最多為*/

　　typedef BinTree SDataType; /*棧的元素類型設為整型*/

　　#define Error printf

　　typedef struct{

　　SDataType data[StackSize];

　　int top;

　　}SeqStack;

　　void InitStack(SeqStack *S) /*初始棧*/

　　{ S>top=;

　　}

　　int StackEmpty(SeqStack *S) /*判棧空*/

　　{return S>top==;

　　}

　　int StackFull(SeqStack *S) /*判棧滿*/

　　{return S>top==StackSize;

　　}

　　void Push(SeqStack *S SDataType x) /*進棧*/

　　{if(StackFull(S))

　　Error(棧已滿\n); /*上溢退出*/

　　else S>data[++S>top]=x; /*棧頂指針加後將x進棧*/

　　}

　　SDataType Pop(SeqStack *S) /*出棧*/

　　{if (StackEmpty(S))

　　Error(Stack underflow); /*下溢退出*/

　　else return S>data[S>top]; /*棧頂指針返回後將棧頂指針減*/

　　}

　　SDataType StackTop(SeqStack *S) /*取棧頂元素*/

　　{if (StackEmpty(S))

　　Error(棧已空\n);

　　return S>data[S>top];

　　}

　　main()

　　{BinTree T;

　　char chch;

　　printf(\n歡迎進入二叉樹操作測試程序請選擇\n);

　　ch=y;

　　while(ch==y || ch==Y)

　　{printf(\nA二叉樹建立);

　　printf(\nB先序遍歷(非遞歸));

　　printf(\nC退出\n);

　　scanf(\n%c&ch);

　　switch(ch)

　　{case A:

　　case a:printf(按二叉樹帶空指針的先序次序輸入結點:\n);

　　CreateBinTree(&T);

　　printf(二叉樹建立成功\n);break;

　　case B:

　　case b:printf(遍歷的結果為:\n);

　　PreorderN(T);break;

　　case C:

　　case c:ch=n;break;

　　default:ch=n;

　　}

　　}

　　}

　　void CreateBinTree(BinTree *T)

　　{char ch;

　　scanf(\n%c&ch);

　　if (ch==) *T=NULL;

　　else {*T=(BinTNode*)malloc(sizeof(BinTNode));

　　(*T)>data=ch;

　　CreateBinTree(&(*T)>lchild);

　　CreateBinTree(&(*T)>rchild);

　　}

　　}

　　void PreorderN(BinTree T)

　　{/*先序遍歷二叉樹T的非遞歸算法*/

　　SeqStack *S;

　　BinTree p;

　　InitStack(S);Push(ST); /*根指針進棧*/

　　while(!StackEmpty(S))

　　{while(p=StackTop(S))

　　{ printf(%cp>data); /*訪問入棧結點的數據域*/

　　Push(Sp>lchild); /*向左走到盡頭*/

　　}

　　p=Pop(S); /*空指針退棧*/

　　if (!StackEmpty(S)) /*輸出結點向右一步*/

　　{p=Pop(S);

　　/* printf(%cp>data); */

　　Push(Sp>rchild);

　　}

　　}

　　}/*PreorderN */

From:http://tw.wingwit.com/Article/program/sjjg/201311/23547.html