用链式存储方式建一个二叉树,要可以接受data to data,要实现两个算法:中缀遍历和后序遍历.
并分析时间复杂性.
我是个刚入门的小菜鸟 还望各位大虾指教.
我这里有个关于二叉树的程序,不过可不可以就不知道了,但程序能通过!前几天我才交的作业!
#include<stdio.h>
#include<malloc.h>
typedef struct node
{
char data; /*此例中二叉树的结点采用字符类型*/
struct node *lchild,*rchild;
}NODE;
int count;
NODE *crt_bt_pre() /*按先序遍历序列创建二叉树的二叉链表*/
{
NODE *bt;
char ch;
printf("\n\t\t\t");
scanf("%c",&ch);
getchar();
if(ch==' ') bt=NULL;
else
{
bt=(NODE *)malloc(sizeof(NODE));
bt->data=ch;
printf("\n\t\t\tqingshuru%cjiediandezuohaizi: ",bt->data);
bt->lchild=crt_bt_pre();
printf("\n\t\t\tqingshuru%cjiediandeyouhaizi: ",bt->data);
bt->rchild=crt_bt_pre();
}
return(bt);
}
void Preorder(NODE *bt) /*先序遍历二叉树*/
{
if(bt)
{
printf("\n\t\t\t %c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
void Inorder(NODE *bt) /*中序遍历二叉树*/
{
if(bt)
{
Inorder(bt->lchild);
printf("\n\t\t\t %c",bt->data);
Inorder(bt->rchild);
}
}
void Postorder(NODE *bt) /*后序遍历二叉树*/
{
if(bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("\n\t\t\t %c",bt->data);
}
}
void CountLeaf(NODE *bt) /*统计二叉树中叶子结点个数*/
{
if(bt)
{
if((bt->lchild==NULL)&&(bt->rchild==NULL))
{
count++;
return;
}
CountLeaf(bt->lchild);
CountLeaf(bt->rchild);
}
}
int CountNode(NODE *bt) /*统计二叉树中结点总数*/
{
if(bt==NULL)
return 0;
else
{
count++;
CountNode(bt->lchild);
CountNode(bt->rchild);
return(count);
}
}
int TreeDepth(NODE *bt) /*求二叉树的深度*/
{
int ldep,rdep;
if(bt==NULL)
return 0;
else
{
ldep=TreeDepth(bt->lchild);
rdep=TreeDepth(bt->rchild);
if(ldep>rdep)
return(ldep+1);
else
return(rdep+1);
}
}
main()
{
NODE *bt;
char choice;
int j=1;
int x;
while(j)
{
printf("\n\n\n\n");
printf("\t\t\t-erchushudejibenyunsuan-\n");
printf("\n\t\t\t*******************************************");
printf("\n\t\t\t* 1-------jianerchashu *");
printf("\n\t\t\t* 2-------xianxubianli *");
printf("\n\t\t\t* 3-------zhongxubianli *");
printf("\n\t\t\t* 4-------houxubianli *");
printf("\n\t\t\t* 5-------tongjiyezishu *");
printf("\n\t\t\t* 6-------tongjijiedianshu *");
printf("\n\t\t\t* 7-------qiuerchashushendu *");
printf("\n\t\t\t* 0-------EXIT! *");
printf("\n\t\t\t*******************************************");
printf("\t\t\tqingxuanzecaidanhao(0--7): ");
scanf("%c",&choice);
getchar();
if(choice=='1')
{
printf("\n\t\t\tqingshuruanxianxujianlierchashudejiedianxulie: ");
printf("\n\t\t\tshuoming:zhugeshuru,shurukonggedaibiaohoujijiedianweikong,anhuicheshuruxiayigejiedian.");
printf("\n\t\t\tqingshurugenjiedian: ");
bt=crt_bt_pre(); /*调用创建二叉树的函数*/
printf("\n\t\t\terchashuchenggongjianli!\n");
}
else if(choice=='2')
{
printf("\n\t\t\tgaierchashudexianxubianlixuliewei: ");
Preorder(bt); /*调用先序遍历函数*/
}
else if(choice=='3')
{
printf("\n\t\t\tgaierchashudezhongxubianlixuliewei: ");
Inorder(bt); /*调用中序遍历函数*/
}
else if(choice=='4')
{
printf("\n\t\t\tgaierchashudehouxubianlixuliewei: ");
Postorder(bt); /*调用后序遍历函数*/
}
else if(choice=='5')
{
count=0;
CountLeaf(bt); /*调用统计叶子结点个数的函数*/
printf("\n\t\t\tgaierchashuyou%dgeyezijiedian.\n",count);
}
else if(choice=='6')
{
count=0;
x=CountNode(bt); /*调用统计结点总数的函数*/
printf("\n\t\t\tgaierchashugongyou%dgejiedian.\n",count);
}
else if(choice=='7')
{
x=TreeDepth(bt); /*调用求二叉树深度的函数*/
printf("\n\t\t\tgaierchashudeshenduwei%d",x);
}
else if(choice=='0') break;
}
}
应该能用的!
#include "stdio.h"
#include "malloc.h"
#define OK 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0
typedef int status;
typedef char telemtype;
typedef struct bitnode{
telemtype data;
struct bitnode *lchild,*rchild;
}bitnode ,*bitree;
status creatbitree(bitree &t)//构造函数
{
char ch;
scanf("%c",&ch);
if(ch==' ')
t=0;
else {
if(!(t=(bitnode *)malloc(sizeof(bitnode))))
return OVERFLOW;
else
t->data=ch;
creatbitree(t->lchild);
creatbitree(t->rchild);
}
return OK;
}
void preorder(bitree &t)//先序遍历
{
if(t!=NULL)
{
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void midorder(bitree &t)//中序遍历
{
if(t!=NULL)
{
preorder(t->lchild);
printf("%c",t->data);
preorder(t->rchild);
}
}
void backorder(bitree &t)//后序遍历
{
if(t!=NULL)
{
backorder(t->lchild);
backorder(t->rchild);
printf("%c",t->data);
}
}
int findelem(bitree t,telemtype x)//查找元素
{
int p;
if(!t) return 0;
if(t->data==x)
return 1;
p=findelem(t->lchild,x);
if(p)
return 1;
else
return (findelem(t->rchild,x));
}
void countleaf(bitree &t,int &count) //计算叶子节点
{
if(t)
{
if((!t->lchild)&&(!t->rchild))
count++;
countleaf(t->lchild,count);
countleaf(t->rchild,count);
}
}
//////////////////////////////////////修改中///////////////////////////
int destorytree(bitree &t)
{
bitnode *p=NULL;
if(t->lchild!=NULL)
{
p=t->lchild;
destorytree(p);
}
else if(t->rchild!=NULL)
{
p=t->rchild;
destorytree(p);
}
free(p);
return OK;
}//树的释放
int treeempty(bitree t)
{
if(t->data==NULL)
{
printf("这是个空树");
return 1;
}
else
{
printf("这不是个空树");
return 0;
}
}
//判断是不是空树
void cleartree(bitree &t)
{
t->data='0';
if(t->lchild!=NULL)
cleartree(t->lchild);
else if(t->rchild!=NULL)
cleartree(t->rchild);
else
t->data='0';
}
///////////////////////////////////////////主函数///////////////
void main()
{
bitree t;
char x,y;
int p;
int empty;
int count=0;
printf("创建二叉树:");
creatbitree(t);
/*printf("先序遍历是\n");
preorder(t);
printf("\n");
printf("中序遍历是:\n");
midorder(t);
printf("\n");
printf("后序遍历是:\n");
backorder(t);
printf("\n");
printf("请输入要查询的元素:");
scanf("%c",&x);
scanf("%c",&y);
p=findelem(t, y);
if(p==0)
printf("元素不在树中\n");
else
printf("元素在树中\n");
countleaf(t,count);
printf("树中叶子节点个数是:%d\n",count);
empty=treeempty(t);
printf("\n");
cleartree(t);
printf("先序遍历是\n");
preorder(t);
printf("\n");
if(destorytree(t)== OK)
printf("树已经释放\n");
printf("\n");
}