建立二叉树，层序、先序遍历（用非递归的方法）
#include
#include
#include
#include
#include
#define SIZE 100
using namespace std;
typedef struct BiTNode //??Òå?þ?æÊ??Úµã?á?? {
char data; //Êý?ÝÓò
struct BiTNode *lchild,*rchild; //×óÓÒº?×ÓÖ?ÕëÓò }BiTNode,*BiTree;
int visit(BiTree t);
void CreateBiTree(BiTree &T); //Éú?ÉÒ??ö?þ?æÊ? void InOrderTraverse(BiTree T); //?ǵÝ?éÖÐÐò?éÀú?þ?æÊ? void PreOrder_Nonrecursive(BiTree T);//?ǵÝ?éÏÈÐò?éÀú?þ?æÊ? void LeverTraverse(BiTree T);//?ǵÝ?é?ãÐò?éÀú?þ?æÊ?
//Ö?º?Êý
void main()
{
BiTree T;
char j;
int flag=1;
//---------------------?ÌÐò?â˵-----------------------
printf("???ÌÐòʵÏÖ?þ?æÊ?µÄ?Ù×???\n");
printf("Ò?×Ó?áµãÒÔ?Õ?ñ?íÊ???\n");
printf("?ÉÒÔ?øÐÐ??Á??þ?æÊ????ǵÝ?éÏÈÐò??ÖÐÐò?éÀú???ǵÝ?é?ãÐò?éÀúµÈ
?Ù×???\n");
//----------------------------------------------------
printf("\n");
printf("Çë??Á??þ?æÊ???\n");
printf("??Ê???ÒÔÈý?ö?Õ?ñºó?Ø?µ?áÊø??\n");
printf("ÀýÈç:1 2 3 4 5 6 (?Ø?µ)\n"); CreateBiTree(T);
//?õÊ????ÓÁÐ
getchar();
while(flag)
{
printf("\n");
printf("ÇëÑ?Ôñ: \n");
printf("1.?ǵÝ?éÖÐÐò?éÀú\n");
printf("2.?ǵÝ?éÏÈÐò?éÀú\n");
printf("3.?ǵÝ?é?ãÐò?éÀú\n");
printf("0.ÍË?ö?ÌÐò\n");
scanf(" %c",&j);
switch(j)
{
case '1':if(T)
{
printf("?ǵÝ?éÖÐÐò?éÀú?þ?æÊ?:");
InOrderTraverse(T);
printf("\n");
}
else printf("?þ?æÊ?Ϊ?Õ!\n");
break;
case '2':if(T)
{
printf("?ǵÝ?éÏÈÐò?éÀú?þ?æÊ?:");
PreOrder_Nonrecursive(T);
printf("\n");
}
else printf("?þ?æÊ?Ϊ?Õ!\n");
break;
case '3':if(T)
{
printf("?ǵÝ?é?ãÐò?éÀú?þ?æÊ?:");
LeverTraverse(T);
printf("\n");
}
else printf("?þ?æÊ?Ϊ?Õ!\n");
break;
default:flag=0;printf("?ÌÐòÔËÐÐ?áÊø????ÈÎÒâ?üÍË?ö!\n");
}
}
}
//??Á??þ?æÊ?
void CreateBiTree(BiTree &T) {
char ch;
scanf("%c",&ch); //?ÁÈëÒ??ö×Ö?û
if(ch==' ') T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //Éú?ÉÒ??öÐÂ?áµã
T->data=ch;
CreateBiTree(T->lchild); //Éú?É×ó×ÓÊ?
CreateBiTree(T->rchild); //Éú?ÉÓÒ×ÓÊ?
}
}
//?ǵÝ?éÖÐÐò?éÀú void InOrderTraverse(BiTree T)
{
stack S;
BiTree p;
S.push(T);//?úÖ?Õë?øÕ?
while(!S.empty())
{
p=new BiTNode;
while((p=S.top())&&p)
S.push(p->lchild);//Ïò×ó×ßµ???Í?
S.pop(); //?ÕÖ?ÕëÍËÕ?
if(!S.empty())
{
p=S.top();
S.pop();
cout<data<<" ";
S.push(p->rchild);
}
}
}
//ÏÈÐò?éÀúµÄ?ǵÝ?é
void PreOrder_Nonrecursive(BiTree T)
{
stack S;
BiTree p;
S.push(T);//?ùÖ?Õë?øÕ?
while(!S.empty())//Õ??ÕÊ??áÊø
{
while((p=S.top())&&p)
{
cout<data<<" ";
S.push(p->lchild);
}//Ïò×ó×ßµ???Í?
S.pop();//µ??ö?ÑÕ?
if(!S.empty())
{
p=S.top();
S.pop();
S.push(p->rchild);//ÏòÓÒ×ßÒ???
}
}
}
void LeverTraverse(BiTree T)
{//?ǵÝ?é?ã?Î?éÀú
queue Q;
BiTree p;
p = T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(visit(p->lchild) == 1)
Q.push(p->lchild);
if(visit(p->rchild) == 1)
Q.push(p->rchild);
}
}
int visit(BiTree T) {
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
浙公网安备 33021202002483