求高手编写二叉树的非递归先序遍历和后序遍历的代码，要求和下面给出的中序遍历类似的做法，程序如下： 求C语言非递归建立二叉树和非递归非递归先序遍历的完整代码
\u5efa\u7acb\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u8981\u6c42\u5206\u522b\u7528\u9012\u5f52\u548c\u975e\u9012\u5f52\u65b9\u6cd5\u5b9e\u73b0\u4e8c\u53c9\u6811\u7684\u5148\u5e8f\u3001\u4e2d\u5e8f\u548c\u540e\u5e8f\u904d\u5386\u3002\u6211\u4eec\u7684\u6570\u636e\u7ed3\u6784\u5b9e\u9a8c\u4e5f\u662f\u8fd9\u9898\uff0c\u9700\u8981\u6211\u628a\u6211\u7684\u5b9e\u9a8c\u62a5\u544a\u7ed9\u4f60\u53c2\u8003\u4e0b\u4e48\uff01
\u6211\u8fd9\u91cc\u5c31\u53ea\u53d1\u8fd9\u90e8\u5206\u7684\u4ee3\u7801\u3002
Status PreOrderTraverse(BiTree T)
{
//\u5148\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u9012\u5f52\u7b97\u6cd5
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
elsereturn OK;
}
Status PreOrder(BiTree T)
{
//\u5148\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u975e\u9012\u5f52\u7b97\u6cd5
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//\u4e2d\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u9012\u5f52\u7b97\u6cd5
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//\u4e2d\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u975e\u9012\u5f52\u7b97\u6cd5
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//\u540e\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u9012\u5f52\u7b97\u6cd5
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//\u540e\u5e8f\u904d\u5386\u4e8c\u53c9\u6811T\u7684\u9012\u5f52\u7b97\u6cd5
unsigned sign;//\u8bb0\u5f55\u7ed3\u70b9\u4ece\u6808\u4e2d\u5f39\u51fa\u7684\u6b21\u6570
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//\u7b2c\u4e00\u6b21\u9047\u5230\u7ed3\u70b9T\u65f6\u538b\u5165\u5176\u6307\u9488
push(1);//\u7f6e\u6807\u5fd7\u4e3a1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//\u8868\u793a\u8d70\u8fc7T\u7684\u5de6\u5b50\u6811
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//\u8868\u793aT\u7684\u5de6\u53f3\u5b50\u6811\u90fd\u5df2\u8d70\u8fc7
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
\u7ed9\u4f60\u7f16\u4e86\u4e2a\uff0c\u5148\u5e8f\u9012\u5f52\u5efa\u6811\u7684\u3002
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;//\u6811\u7c7b\u578b
typedef struct SqStack
{
BiTNode *base;
BiTNode *top;
int stacksize;
} SqStack;//\u6808\u7c7b\u578b
void InitStack(SqStack *S)//\u521b\u5efa
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,BiTNode e)//\u8fdb\u6808
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}
BiTNode Pop(SqStack *S)//\u51fa\u6808
{
S->top --;
return *S->top;
}
int StackEmpty(SqStack *S)//\u5224\u65ad\u6808\u662f\u5426\u975e\u7a7a
{
if(S->top == S->base )
return 1;
else
return 0;
}
BiTree CreateBiTree()//\u521b\u5efa\u6811\uff08\u5148\u5e8f\u9012\u5f52\uff09
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
void PreOrder(BiTree T)//\u5148\u5e8f
{
SqStack S;
BiTree p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
}
void InOrder(BiTree T)//\u4e2d\u5e8f
{
SqStack S;
BiTree p=T;
InitStack(&S);
while(p||!StackEmpty(&S))
{
if(p)
{
Push(&S,*p);
p=p->lchild;
}
else
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
p=p->rchild;
}
}
}
void main()
{
BiTree Ta;
printf("\u8bf7\u521b\u5efa\u6811");
Ta=CreateBiTree();
printf("\u5148\u5e8f\u904d\u5386:");
printf("\n");
PreOrder(Ta);
printf("\n");
printf("\u4e2d\u5e8f\u904d\u5386:");
printf("\n");
InOrder(Ta);
}
{//先序遍历二叉树T的递归算法
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}else return OK;
}
void PostOrderTraverse(BiTree bt)
{//后序遍历二叉树的递归算法
if(bt){
PostOrderTraverse(bt->lchild); /* 后序遍历根结点 */
PostOrderTraverse(bt->rchild);/* 访问根结点 */
printf("%c",bt->data); /* 后序遍历右子树*/
}
} /* Postorder*/
绛旓細/*---閫掑綊---鍏堝簭寤虹珛浜屽弶鏍---*/void CreateBiTree(bitree **T) { //鎸夊厛搴忔搴忚緭鍏浜屽弶鏍戜腑鐨勭粨鐐圭殑鍊(涓涓瓧绗),绌烘牸瀛楃琛ㄧず绌烘爲, //鏋勯犱簩鍙夐摼琛ㄨ〃绀轰簩鍙夋爲 char ch; scanf("%c",&ch); if(ch=='#') *T=NULL; else{ *T=(bitree * )malloc(sizeof(bitree)); if(!*T) exit(1)...
绛旓細1銆闈為掑綊鍓嶅簭閬嶅巻 鍙ｈ瘈锛氭牴宸﹀彸銆傚墠搴忛亶鍘嗛鍏堣闂牴缁撶偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆傚湪閬嶅巻宸︺佸彸瀛愭爲鏃讹紝浠嶇劧鍏堣闂牴鑺傜偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆1.1 鍏蜂綋娴佺▼ 1.2 鍏蜂綋浠ｇ爜 2銆侀潪閫掑綊涓簭閬嶅巻 涓簭閬嶅巻鏄滃乏鏍瑰彸"锛屽嵆鍏堥亶鍘嗗乏瀛愭爲鑺傜偣锛屽啀閬嶅巻鏍硅妭鐐癸紝鍐嶉亶鍘嗗彸瀛愭爲鑺傜偣 2...
绛旓細Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){//鍏堝簭閬嶅巻浜屽弶鏍T鐨勯掑綊绠楁硶 if(T){ if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;} void PostOrderTraverse(BiTree bt){/...
绛旓細绗1涓暟鎹槸20,浣滀负鏍圭粨鐐,// 绗2涓暟鎹槸15,姣20灏,浣滀负20鐨勫乏鍒嗘敮,绗3涓暟鎹槸10,姣20鍜15灏,// 浣滀负15鐨勫乏鍒嗘敮,绗4涓暟鏄12,姣20鍜15灏,浣嗘瘮10澶,浣滀负10鐨勫彸鍒嗘敮,// 濡傛绫绘帹,鍒涘缓瀹屾暣鐨浜屽弶鏍.// 鍏堝簭閬嶅巻鐢╗鏍圿,灞傚簭
绛旓細鏈创缁欏嚭浜屽弶鏍戝厛搴銆佷腑搴忋佸悗搴忎笁绉嶉亶鍘鐨勯潪閫掑綊绠楁硶锛屾涓変釜绠楁硶鍙涓烘爣鍑嗙畻娉曪紝鐩存帴鐢ㄤ簬鑰冪爺绛旈銆1.鍏堝簭閬嶅巻闈為掑綊绠楁硶 define maxsize 100 typedef struct { Bitree Elem[maxsize];int top;}SqStack;void PreOrderUnrec(Bitree t){ SqStack s;StackInit(s);p=t;while (p!=null || ...
绛旓細/*---闈為掑綊---鍏堝簭寤虹珛浜屽弶鏍---*/ bitree *createprebitree(){char ch;bitree *ht,*p,*q;sqstack *s;s=malloc(sizeof(bitree)); //鍔犱笂杩欎竴鍙ヤ负s 鍒濆鍖栧紑杈熺┖闂 ch=getchar();if(ch!='#'&&ch!='\n') /* 杈撳叆浜屽弶鏍戝厛搴忛『搴 鏄互瀹屽叏浜屽弶鏍戠殑鍏堝簭椤哄簭 涓嶆槸...
绛旓細PreOrderTraverse(T->rchild,Visit); // 鏈鍚鍏堝簭閬嶅巻鍙冲瓙鏍 } } void InOrderTraverse(BiTree T,void(*Visit)(int))//浜屽弶鏍T瀛樺湪锛孷isit鏄缁撶偣鎿嶄綔鐨勫簲鐢ㄥ嚱鏁帮紝涓簭閫掑綊閬嶅巻T锛屽姣忎釜缁撶偣璋冪敤鍑芥暟Visit涓娆′笖浠呬竴娆 { if(T){ InOrderTraverse(T->lchild,Visit); // 鍏堜腑搴忛亶鍘嗗乏瀛愭爲...
绛旓細p=T;//鍙栨爤椤 while(P||!StackEmpty(S)){ //P瀛樺湪鎴栬呮爤闈炵┖ if(p) { //p闈炵┖锛屽嵆宸﹀瓙鏍戞垨鑰呭彸瀛愭爲瀛樺湪 Push(S,p); //灏嗗乏瀛愭爲鍏ユ爤 p=p->lchild; //鍙栦笅涓涓乏瀛愭爲 } else{ Pop(S,p); //鍑烘爤锛岀浉褰撲簬鍏堝簭閬鍘嗕簡锛屽洜涓哄乏瀛愭爲閮絋MD鍏ユ爤浜嗭紝鐜板湪鍙嶅悜杈撳嚭 p=p...
绛旓細//===閲囩敤鍚搴閬嶅巻姹浜屽弶鏍戠殑娣卞害銆佺粨鐐规暟鍙婂彾瀛愭暟鐨閫掑綊绠楁硶=== int TreeDepth(BinTree T){ int hl,hr,max;if(T){ hl=TreeDepth(T->lchild); //姹傚乏娣卞害 hr=TreeDepth(T->rchild); //姹傚彸娣卞害 max=hl>hr? hl:hr; //鍙栧乏鍙虫繁搴︾殑鏈澶у NodeNum=NodeNum+1; //姹...
绛旓細void PreOrder_Nonrecursive(Bitree T)//鍏堝簭閬嶅巻浜屽弶鏍戠殑闈為掑綊绠楁硶 {//鎬濊矾涓哄埄鐢ㄨ嚜宸辩殑鍫嗘爤妯℃嫙鍑芥暟閫掑綊璋冪敤鏃舵爤鍖虹殑鍙樺寲銆侷nitStack(S);//鍒濆鍖栧爢鏍堛傚弬鐓т弗钄氭晱缂栥婃暟鎹粨鏋凜璇█鐗堛嬪疄鐜板爢鏍堢殑鐩稿叧鍔熻兘鍑芥暟锛岃繖閲屼細鐢ㄥ埌銆侾ush(S,T); //鏍规寚閽堣繘鏍 while(!StackEmpty(S)){ while(Gettop(...
