#include"stdlib.h"/存储分配头文件，或用"malloc.h"/
#include"stdio.h"/标准I/O头文件/
#include"ctype.h"
#defineN10000/定义NULL,本行可省去/
#defineLENGsizeof(structBnode)/确定结点所占空间的字节数/
typedefcharElemType;/抽象元素类型为char类型/
typedefstructBnode/Bnode为结点(C结构体)类型/
{ElemTypedata;/data为抽象元素类型/
structBnodelchild,rchild;/为指针类型/
signedsize;
}Bnode;
intnode[4];
intcreat_tree(Bnoderoot)/root是指向指针的指针类型/
{/本算法递归生成二叉树/
ElemTypech;
scanf("%c",&ch);/输入结点,字符型/
if(ch==''''){(root)->data=NULL;
return;}/生成空二叉树/
else/生成非空二叉树/
{(root)=(Bnode)malloc(LENG);/申请结点空间/
(root)->data=ch;/生成根结点/
creat_tree(&(root)->lchild);/递归生成左子树/
creat_tree(&(root)->rchild);/递归生成右子树/
}
}/creat_tree/
voidpreorder1(Bnoderoot)
{/前序遍历二叉树/
if(root)
{printf("%c",root->data);
if(root->lchild)preorder1(root->lchild);
if(root->rchild)preorder1(root->rchild);
}
}/preorder/
voidpreorder2(Bnoderoot)
{/中序遍历二叉树/
if(root)
{
if(root->lchild)preorder2(root->lchild);
printf("%c",root->data);
if(root->rchild)preorder2(root->rchild);
}
}/preorder/
voidpreorder3(Bnoderoot)
{/后序遍历二叉树/
if(root)
{
if(root->lchild)preorder3(root->lchild);
if(root->rchild)preorder3(root->rchild);
printf("%c",root->data);
}
}/preorder/
voidpreorder4(Bnoderoot)/中序非递归遍历二叉树/
{Bnodep,stack[N];
inttop=0;
p=root;
do{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[top];/p所指的节点为无左子树或其左子树已经遍历过/
top--;
printf("%c",p->data);
p=p->rchild;
}
}while(p!=NULL||top!=0);
}/preorder/
voidpreorder5(Bnoderoot)/先序非递归遍历二叉树/
{Bnodep,stack[N];
inttop;
p=root;
if(root!=NULL)
{top=1;
stack[top]=p;
while(top>0)
{
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;
}
}
}/preorder/
voiddegrees(Bnoderoot)/中序非递归遍历二叉树/
{Bnodep,stack[N];
inttop=0,i=0,j=0,k=0;
p=root;
do{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[top];/p所指的节点为无左子树或其左子树已经遍历过/
top--;
if(p->lchild!=NULL&&p->rchild!=NULL)k++;
elseif(p->lchild==NULL&&p->rchild==NULL)i++;
elsej++;
printf("%c",p->data);
p=p->rchild;
}
}while(p!=NULL||top!=0);
printf("Dgrees=0:%d",i);
printf("Dgrees=1:%d",j);
printf("Dgrees=2:%d",k);
}/preorder/
intnodes(Bnoderoot)
{
intnum1,num2;
if(root==NULL)return(0);
else
{
num1=nodes(root->lchild);
num2=nodes(root->rchild);
return(num1+num2+1);/加1是因为要算上根节点/
}
}
intnodeO(Bnoderoot)
{
intnum1,num2;
if(root==NULL)return(0);
else
{
num1=nodeO(root->lchild);
num2=nodeO(root->rchild);
if(root->lchild==NULL&&root->rchild==NULL)
return(num1+num2+1);/加1是因为要算上根节点/
elsereturn(num1+num2);
}
}
intnode1(Bnoderoot)
{
intnum1,num2;
if(root==NULL)return(0);
elseif((root->lchild!=NULL&&root->rchild==NULL)||(root->lchild==NULL&&root->rchild!=NULL))
return(1);
else
{
num1=node1(root->lchild);
num2=node1(root->rchild);
return(num1+num2+1);/加1是因为要算上根节点/
}
}
intnode2(Bnoderoot)
{
intnum1,num2;
if(root==NULL)return(0);
else
{
num1=node2(root->lchild);
num2=node2(root->rchild);
if(root->lchild!=NULL&&root->rchild!=NULL)
return(num1+num2+1);/加1是因为要算上根节点/
elsereturn(num1+num2);
}
}
voidmain(void)/主函数/
{intj;
charCH;
Bnoderoot;/root是指向根结点的指针变量/
root=(Bnode)malloc(sizeof(Bnode));
do{
printf("\n1:CreateTree:");
printf("\n2:TravelTree:(DLR)");
printf("\n3:TravelTree:(LDR)");
printf("\n4:TravelTree:(LRD)");
printf("\n5:TravelTree:(LDR)(FeiDiGui):");
printf("\n6:TravelTree:(DLR)(FeiDiGui):");
printf("\n7:DegreesofTree:(DiGui);");
printf("\n8:DegreesofTree:(FeiDiGui);");
printf("\nChoose:");
scanf("%d",&j);
switch(j){
case1:creat_tree(&root);
break;/取根指针变量的地址,生成二叉树/
case2:preorder1(root);break;/前序遍历二叉树/
case3:preorder2(root);break;/中序遍历二叉树/
case4:preorder3(root);break;/后序遍历二叉树/
case5:preorder4(root);break;/非递归中序遍历二叉树/
case6:preorder5(root);break;/非递归先序遍历二叉树/
case7:node[3]=nodes(root);
printf("SIZEOFTREE=%d",node[3]);/递归算法求节点总数/
node[0]=nodeO(root);
printf("Degree=0:%d",node[0]);
node[1]=node1(root);
printf("Degree=1:%d",node[1]);
node[2]=node2(root);
printf("Degree=2:%d",node[2]);break;
case8:degrees(root);break;
default:printf("Choosefrom1,2,3,4...8");break;
}
printf("\nCONTINUE?(Y/N)");
while(isspace(CH=getchar()));
}while(CH!=''N''||CH!=''n'');
printf("\nbyebye!");
}
|
|
