#include
#include
#defineMAX50
#defineMAS20
#defineCHAR1
#ifCHAR
typedefcharTElemType;
TElemTypeNil='''';
#defineform"%c"
#else
typedefintTElemType;
TElemTypeNil=0;
#defineform"%d"
#endif
typedefstructnode
{TElemTypedata;
structnodeleft;
structnoderight;
structnodeparent;
}BiTNode,BiTree;
BiTNodeInitBiTree(BiTNodebt)
{
bt=NULL;
returnbt;
}
BiTNodeCreateBiTree(BiTNodebt)
{TElemTypech;
scanf(form,&ch);
if(ch==Nil)bt=NULL;
else
{bt=(BiTNode)malloc(sizeof(BiTNode));
if(!bt)exit(0);
bt->data=ch;bt->parent=NULL;
bt->left=CreateBiTree(bt->left);
if(bt->left)bt->left->parent=bt;
bt->right=CreateBiTree(bt->right);
if(bt->right)bt->right->parent=bt;
}
returnbt;
}
voidPrintTree(BiTNodebt,inti)
{if(bt!=NULL)
{PrintTree(bt->right,i+5);
#ifCHAR
if(bt->data!=Nil)
printf("%c\n",i,bt->data);
#else
if(bt->data!=Nil)
printf("%d\n",i,bt->data);
#endif
PrintTree(bt->left,i+5);
i=i-5;
}
}
voidProrder1(BiTNodebt,void(visit)(TElemType))/先序遍历/
{if(bt!=NULL)
{visit(bt->data);
Prorder1(bt->left,visit);
Prorder1(bt->right,visit);
}
}
voidProrder2(BiTNodebt,void(visit)(TElemType))/中序遍历/
{BiTNodep,stack[MAS];
inttop;
top=0;p=bt;
while(top!=0||p!=NULL)
{while(p!=NULL)
{stack[top]=p;top++;
p=p->left;
}
if(top!=0)
{p=stack[top-1];
top--;
visit(p->data);
p=p->right;
}
}
}
voidProrder3(BiTNodebt,void(visit)(TElemType))/后序遍历/
{BiTNodep,stack[MAS];
inttop;
top=0;
stack[top]=bt;top++;
while(top>0)
{p=stack[top-1];top--;
while(p!=NULL)
{visit(p->data);
stack[top]=p->right;
top++;
p=p->left;
}
}
}
voidvisit(TElemTypee)
{printf(form"",e);
}
intSumLefts(BiTNodebt,intsum)
{
if(bt!=NULL)
{
if(bt->left==NULL&&bt->right==NULL)
{
printf("%4c",bt->data);sum++;
}
sum=SumLefts(bt->left,sum);
sum=SumLefts(bt->right,sum);
}
return(sum);
}
intSumTree(BiTNodebt)
{staticintsum=0;
if(bt!=NULL)
{printf("%4c",bt->data);
sum++;
sum=SumTree(bt->left);
sum=SumTree(bt->right);
}
return(sum);
}
BiTNodeFindchar(BiTNodebt,charch)/二叉树查找结点/
{BiTNodep;/利用函数名返回结果/
if(bt!=NULL)
{if(bt->data==ch)p=bt;
p=Findchar(bt->left,ch);
p=Findchar(bt->right,ch);
}
if(p!=NULL)return(p);
elsereturn(NULL);
}
main()
{intj,i,a,sum=0;
BiTreebt;
bt=InitBiTree(bt);
#ifCHAR
printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n");
#else
printf("请先序输入二叉树(如:12000表示1为根结点,2为左子树的二叉树)\n");
#endif
bt=CreateBiTree(bt);
printf("输入建立的二叉树!!!\n");
PrintTree(bt,5);
do{
printf("------------------------------------------------------------");
printf("\n主菜单");
printf("\n1二叉树先序遍历");
printf("\n2二叉树中序遍历");
printf("\n3二叉树后序遍历");
printf("\n4二叉树叶子结点数");
printf("\n5二叉树结点数");
printf("\n6二叉树查找x结点");
printf("\n0退出");
printf("\n----------------------------------------------------------");
printf("\n");
printf("输入你要选择的数据:");
scanf("%d",&i);
switch(i)
{case1:printf("先序遍历结果为:");
Prorder1(bt,visit);
break;
case2:printf("后序遍历结果为:");
Prorder2(bt,visit);
break;
case3:printf("中序遍历结果为:");
Prorder3(bt,visit);
break;
case4:j=SumLefts(bt,sum);
printf("树的叶子结点数为%d:",j);
break;
case5:j=SumTree(bt);
printf("树的结点数为%d:",j);
break;
case6:printf("输入要查找的结点字符x:");
scanf("%c",&a);scanf("%c");
j=Findchar(bt,a);
printf("要查找的结点的指针为%d:",j);
break;
case0:exit(0);
}
printf("\n");
getch();
}while(i>0||i<8);
}
/在这个算法中,分别有二叉树的建立,输出,先序,中序,后序
以及查找叶子结点,所有结点数,查找某结点的指针的算法。
算法中还有很多的不足希望大家能进一步的完善它/
/我还希望能结交一些爱好c编程的朋友,我的qq号为:343012669.
E_mail:zhenji512@126.com/
/我非常希望和大家认识/
|
|
