閱讀以下說(shuō)明和C語(yǔ)言函數(shù),將應(yīng)填入(n)處的語(yǔ)句寫(xiě)在對(duì)應(yīng)欄內(nèi)?!菊f(shuō)明】 本程序利用非遞歸算法實(shí)現(xiàn)二
閱讀以下說(shuō)明和C語(yǔ)言函數(shù),將應(yīng)填入(n)處的語(yǔ)句寫(xiě)在對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
本程序利用非遞歸算法實(shí)現(xiàn)二叉樹(shù)后序遍歷。
【函數(shù)】
include<stdio.h>
include<stdlib.h>
typedef struct node{/*二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)類(lèi)型*/
char data;
struct node *left;
struct node *right;
}BTREE;
void SortTreelnsert(BTREE **tree, BTREE *s)
{
if(*tree==NULL)*tree=s;
else
if(s->data<(*tree)->data)
SortTreelnsert((1),s);
else if(s->data>=(*tree)->data)
SortTreelnsert((2),s);
}
void TraversalTree(BTREE *tree)
{
BTREE *stack[1 000],*p;
int tag[1000],top=0;
p=tree;
do{
while(p !=NULL)
{
stack[++top]=p;
(3);
tag[top]=0; /*標(biāo)記棧頂結(jié)點(diǎn)的左子樹(shù)已進(jìn)行過(guò)后序遍歷*/
}
while(top>0&&(4))/*棧頂結(jié)點(diǎn)的右子樹(shù)是否被后序遍歷過(guò)*/
{
p=stack[top--];
putchar(p->data);
}
if(top>0)/*對(duì)棧頂結(jié)點(diǎn)的右子樹(shù)進(jìn)行后序遍歷*/
{
(5);
tag[top]=1;
}
}while(top>0);
}
void PrintSortTree(BTREE *tree)
{
if(tree !=NULL)
{
printSortTree(tree->left);
putchar(tree->data);
pdntSortTree(tree->right);
}
}
main()
{
BTREE *root=NULL, *node;
char ch;
ch=getchar();
while(ch !='')
{
node=(BTREE*)malloc(sizeof(BTREE));
node->data=ch;
node->left=node->right=NULL;
SortTreelnsert(&root, node);
ch=getchar();
}
PrintSortTree(root);
putchar('\n');
TraversalTree(root);
}