﻿ 用棧實現二叉樹先序遍歷的非遞歸算法實踐題_電腦知識網

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

2022-06-13   來源: 數據結構

/*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