主题：急需！！求助＂二叉树程序～＂
yechaoming1
[专家分：0] 发布于 2006-06-04 18:48:00
要求：
求二叉树的高度；
．．．．．所有结点数；
．．．．．所有叶结点数；
能按各种遍历（前序，中，后，层次）输出所有结点；
能进行查找操作；
哪位朋友能帮个忙啊～～小弟万分感谢！！！！
回复列表 （共3个回复）
沙发
中国台湾 [专家分：2140] 发布于 2006-06-06 12:28:00
#include<stdio.h>
#include<stdlib.h>
#define M 100
#define ERROR 0
#define FALSE 0
#define TURE 1
#define OK 1
typedef int status;
typedef struct Bitree
{
char data;
struct Bitree *lchild, *rchild;
}Bitree,*bitree;
typedef struct
{
bitree a[M];
int top ;
}stack;
status InitStack(stack *s)//初始化栈
{
s->top = 0;
return OK;
}
status PushStack(stack *s,bitree *T)//进栈操作
{
if (s->top > 100)
{
return ERROR;
}
s->a[++s->top] = (*T);
return OK;
}
status PopStack (stack *s, bitree *T)//出栈操作
{
if ( s->top == 0)
{
return ERROR;
}
(*T) = s->a[s->top--];
return OK;
}
status EmptyStack(const stack *s)//判断是否为空
{
if ( s->top == 0)
{
return TURE;
}
else
{
return FALSE;
}
}
status CreatBitree(bitree *T)//建树
{
char ch;
printf("请输入字符:");
scanf("%c",&ch);
getchar();
printf("\n");
if ( ch == ' ')
{
(*T) = NULL;
return 0;
}
else
{
(*T) = (bitree)malloc(sizeof(Bitree));
if(*T==NULL)
{
printf("memory allocation failed ,Goodbye");
exit(1);
}
(*T)->data = ch;
CreatBitree(&(*T)->lchild);
CreatBitree(&(*T)->rchild);
}
return OK;
}
status PreOrderTraverse( bitree *T)//前序遍历
{
stack s;
InitStack(&s);
while ((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
printf("%c",(*T)->data);
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
(*T) = (*T)->rchild;
}
}
return OK;
}
status InorderTraverse( bitree *T)//中序遍历
{
stack s;
InitStack(&s);
while((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
printf("%c",(*T)->data);
(*T) = (*T)->rchild;
}
}
return OK;
}
status BefororderTraverse(bitree *T)//后序遍历
{
int flag = 0;
stack s;
InitStack(&s);
while((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
flag = 0;
}
if (!EmptyStack(&s) && flag == 1)
{
printf("%c",(*T)->data);
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
(*T) = (*T)->rchild;
flag = 1;
}
}
return OK;
}
int main(void)
{
bitree T;
int select ;
CreatBitree(&T);
do
{
printf("1: 进行前序遍历\n");
printf("2: 进行中序遍历\n");
printf("3: 进行后序遍历\n");
printf("请选择:");
scanf("%d",&select);
}while( select < 1 || select > 4);
switch(select)
{
case 1:
printf("前序遍历:");
PreOrderTraverse(&T);
printf("\n");
break;
case 2:
printf("\n中序遍历");
InorderTraverse(&T);
printf("\n");
break;
case 3:
printf("\n后序遍历");
BefororderTraverse(&T);
printf("\n");
default:
break;
}
system("pause");
return 0;
}
后序遍历还有点问题
板凳
中国台湾 [专家分：2140] 发布于 2006-06-06 12:30:00
//////////////////////////////////////////////////////////////////
//////////////////目的:2叉树的基本操作(查找元素还有问题)
//////////////////////////////////////////////////////////////////
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#define INITSTACKSIZE 100
#define INCREMENT 10
#define TURE 1
#define ERROR 0
#define OK 1
#define M 100
typedef int SElemType;
typedef int status ;
static int number=1;
typedef struct bitnode//定义一个2叉数
{
char data;
struct bitnode *lchild ,*rchild;
}bitnode ,*bitree;
int CreatBitree(bitree *T)//建立一个2叉树
{
char ch;
printf("请输入字符:");
scanf("%c",&ch);
getchar();//吃掉残留的数据
if ( ch ==' ')
{
(*T)=NULL;
return 0;
}
else
{
(*T) = (bitree)malloc(sizeof(bitnode));
if((*T) == NULL)
{
printf("memory allocation failed,goodbye");
exit(1);
}
(*T)->data=ch;
CreatBitree(&(*T)->lchild);
CreatBitree(&(*T)->rchild);
}
return OK;
}
void PreOrderTraverse1(bitree T)// 前序遍历递归形式
{
if(T)
{
printf("%c",T->data);
PreOrderTraverse1((*T).lchild);
PreOrderTraverse1((*T).rchild);
}
}
void PreOrderTraverse2(bitree T)// 前序遍历非递归形式
{
int top = 0;
bitree a[M];
while (T!=NULL||top!=0)
{
while ( T!=NULL)
{
printf("%c",T->data);
a[++top] = T;
T = T->lchild;
}
if(top > 0)
{
T = a[top--];
T = T->rchild;
}
}
}
void InOrderTraverse1(bitree T)//中序递归形式访问
{
if(T)
{
InOrderTraverse1(T->lchild);
printf("%c",T->data);
InOrderTraverse1(T->rchild);
}
}
void InOrderTraverse2(bitree T)//中序非递归形式
{
int top = 0;
bitree s[M];
while(T!=NULL||top!=0)
{
while(T!=NULL)
{
s[++top] = T;
T = T->lchild;
}
if (top>0)
{
T = s[top--];
printf("%c",T->data);
T = T->rchild;
}
}
}
void BerforOrderTraverse1(bitree T)//后序递归形式
{
if(T)
{
BerforOrderTraverse1((*T).lchild);
BerforOrderTraverse1((*T).rchild);
printf("%c",T->data);
}
}
void BerforOrderTraverse2(bitree t) //后序非递归形式（别人写的 我复制 以后多要看）
{
typedef struct node
{
bitree t;
int tag;
} stack;
stack s[100] ;
int top=0;
while (t!=NULL|| top!=0)
{
while (t!=NULL)
{
s[++top].t=t;
s[top].tag=0;
t=t->lchild;
}
while (top!=0 && s[top].tag==1)
{
printf("%c" ,s[top--].t->data);
}
if (top)
{
s[top].tag=1;
t = s[top].t->rchild ;
}
}
}
status Depth(bitree T) //求树的深度
{
int i = 0;
int j = 0;
if(!T)
{
return 0;
}
else
{
i = Depth(T->lchild);
j = Depth(T->rchild);
return ((i>j?i:j)+1);
}
}
status Node2(bitree T)//求度为2的结点个数
{
int i = 0;
int j = 0;
if(!T)
{
return 0;
}
else
{
j = Node2(T->lchild);
i = Node2(T->rchild);
if(i!=0&&j!=0)
return (i+j+1);
else
return (i+j);
}
}
int Node(bitree T)//求所有的接点数
{
int i=0;
int j=0;
if(!T)
{
return 0;
}
else
{
i = Node(T->lchild);
j = Node(T->rchild);
return (i+j+1);
}
}
int Node0(bitree T)//叶子接点的个数
{
int i ,j;
if(!T)
{
return 0;
}
else
{
i = Node0(T->lchild);
j = Node0(T->rchild);
if(i==0&&j==0)
return (i+j+1);
else
return (i+j);
}
}
void locate(bitree t, char x)
{
bitree p;
p=t;
if (t == NULL)
printf("0\n");
else if( t->data == x)
printf("%d\n",p->data);
else
{
p=t->lchild;
if (p)
locate(t->lchild, x);
else
locate(t->rchild, x);
}
}
3 楼
中国台湾 [专家分：2140] 发布于 2006-06-06 12:30:00
int main(void)
{
bitree T;
int choose;
char num;
int flag = 1, sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
CreatBitree(&T);
while(1)
{
printf("\n");
do
{
printf("1:***************** 先序递归遍历形式\n");
printf("2:***************** 先序非递归遍历形式\n");
printf("3:***************** 中序递归遍历形式\n");
printf("4:***************** 中序非递归遍历形式\n");
printf("5:***************** 后序递归遍历形式\n");
printf("6:***************** 后序非递归遍历形式\n");
printf("7:***************** 计算所有结点个数\n");
printf("8:***************** 计算叶子结点个数\n");
printf("9:***************** 算度为2的结点个数\n");
printf("10:**************** 计算树的深度\n");
printf("11:**************** 查到相同的元素\n");
printf("12:**************** 退出\n");
printf("请选择你需要执行的任务:");
scanf("%d",&choose);
if(choose == 12)
{
flag = 0;
}
}while(choose<0||choose>12);
if(flag==0)
{
break;
}
switch(choose)
{
case 1:
{
printf("\n先序递归遍历形式:");
PreOrderTraverse1(T);
printf("\n");
}
break;
case 2:
{
printf("\n先序非递归遍历形式:");
PreOrderTraverse2(T);
printf("\n");
}
break;
case 3:
{
printf("\n中序递归遍历形式:");
InOrderTraverse1(T);
printf("\n");
}
break;
case 4:
{
printf("\n中序非递归遍历形式:");
BerforOrderTraverse1(T);
printf("\n");
}
break;
case 5:
{
printf("\n后序递归遍历形式:");
BerforOrderTraverse1(T);
printf("\n");
}
break;
case 6:
{
printf("\n后序非递归遍历形式\n");
BerforOrderTraverse2(T);
}
break;
case 7:
{
printf("\n计算所有结点个数:");
sum1 = Node(T);
printf("%d\n",sum1);
}
break;
case 8:
{
printf("\n计算叶子结点个数:");
sum2 =Node0( T);
printf("%d\n",sum2);
}
break;
case 9:
{
printf("计算度为2的结点个数:");
sum3 = Node2(T);
printf("%d\n",sum3);
}
break;
case 10:
{
printf("计算树的深度:");
sum4 = Depth(T) ;
printf("%d\n",sum4);
}
break;
case 11:
{
printf("请输入需要查找的元素:");
scanf("%c",&num);
getchar();
locate(T, num);
}
break;
default:
{
break;
}
}
}
system("pause");
return 0;
}
我来回复
您所在位置：