文章作者：姜南(Slyar) 文章來(lái)源：Slyar Home (輸入:ABDH##I##EJ##K##CF#L##G##
前序遍歷:A B D H I E J K C F L G
中序遍歷:H D I B J E K A F L C G
后序遍歷:H I D J K E B L F G C A
代碼如下:
/*
Slyar
//www.slyar.com
2009.5.16
*/
#include
#include
#define MAXSIZE 200
/* 定義二叉樹(shù)節點(diǎn)類(lèi)型 */
typedef struct node
{
char data;
struct node *lchild, *rchild;
}BTNode;
/* 函數聲明 */
BTNode* CreatBitTree();
void PreOrder(BTNode*);
void InOrder(BTNode*);
void PostOrder(BTNode*);
/* 主函數 */
int main()
{
BTNode *root = NULL;
root = CreatBitTree();
PreOrder(root);
InOrder(root);
PostOrder(root);
system('pause');
return 0;
}
/* 遞歸前序建立二叉樹(shù) */
BTNode* CreatBitTree()
{
char ch;
BTNode *b;
scanf('%c', &ch);
/* 遇到空節點(diǎn)停止遞歸 */
if (ch == '#')
{
b = NULL;
}
else
{
b = (BTNode*) malloc(sizeof(BTNode));
/* 建立根節點(diǎn) */
b->data = ch;
/* 遞歸先序建立左子樹(shù) */
b->lchild = CreatBitTree();
/* 遞歸先序建立右子樹(shù) */
b->rchild = CreatBitTree();
}
return b;
}
/* 非遞歸前序遍歷二叉樹(shù) */
void PreOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int top = -1;
if (b != NULL)
{
/* 根節點(diǎn)入棧 */
top++;
stack[top] = b;
/* 棧不空時(shí)循環(huán) */
while (top > -1)
{
/* 出棧并訪(fǎng)問(wèn)該節點(diǎn) */
p = stack[top];
top--;
printf('%c ', p->data);
/* 右孩子入棧 */
if (p->rchild != NULL)
{
top++;
stack[top] = p->rchild;
}
/* 左孩子入棧 */
if (p->lchild != NULL)
{
top++;
stack[top] = p->lchild;
}
}
printf('\n');
}
}
/* 非遞歸中序遍歷二叉樹(shù) */
void InOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int top = -1;
if (b != NULL)
{
p = b;
while (top > -1 || p != NULL)
{
/* 掃描p的所有左節點(diǎn)并入棧 */
while (p != NULL)
{
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1)
{
/* 出棧并訪(fǎng)問(wèn)該節點(diǎn) */
p = stack[top];
top--;
printf('%c ', p->data);
/* 掃描p的右孩子 */
p = p->rchild;
}
}
printf('\n');
}
}
/* 非遞歸后序遍歷二叉樹(shù) */
void PostOrder(BTNode* b)
{
BTNode *stack[MAXSIZE], *p;
int sign, top = -1;
if (b != NULL)
{
do
{
/* b所有左節點(diǎn)入棧 */
while (b != NULL)
{
top++;
stack[top] = b;
b = b->lchild;
}
/* p指向棧頂前一個(gè)已訪(fǎng)問(wèn)節點(diǎn) */
p = NULL;
/* 置b為已訪(fǎng)問(wèn) */
sign = 1;
while (top != -1 && sign)
{
/* 取出棧頂節點(diǎn) */
b = stack[top];
/* 右孩子不存在或右孩子已訪(fǎng)問(wèn)則訪(fǎng)問(wèn)b */
if (b->rchild == p)
{
printf('%c ', b->data);
top--;
/* p指向被訪(fǎng)問(wèn)的節點(diǎn) */
p = b;
}
else
{
/* b指向右孩子節點(diǎn) */
b = b->rchild;
/* 置未訪(fǎng)問(wèn)標記 */
sign = 0;
}
}
}while (top != -1);
printf('\n');
}
}
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
