楼上的签名好点性别歧视呀!!!哼哼
[此贴子已经被作者于2006-5-28 20:30:28编辑过]
转载 evil_evil C的二叉树.由于没有测试 如果下面代码有问题请发贴.我会修改!
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define maxsize 26
typedef char datatype; //结点属性值类型
typedef struct bitreenode //二叉树结点类型
{
datatype info;
struct bitreenode *leftchild,*rightchild;
}bitreenode;
typedef struct stack //栈的定义
{
bitreenode *data[maxsize];
int tag[maxsize];
int top;
}seqstack;
void initstack(seqstack *t) //栈的初始化
{
t->top=-1;
}
int emptystack(seqstack *t) //判断栈是否为空
{
return(t->top==-1?1:0);
}
void pushstack(seqstack *t,bitreenode *e) //入栈
{
t->data[++t->top]=e;
}
bitreenode *popstack(seqstack *t) //出栈
{
return(t->data[t->top--]);
}
bitreenode *getstack_top(seqstack *t) //取栈顶元素
{
return(t->data[t->top]);
}
bitreenode *creatbitree() //按深度输入完全二叉树来建立二叉树
{ //从上到下,从左到右,输入完全二叉树
int i;
struct
{
datatype x;
bitreenode *p;
}y[maxsize+1];
char c[maxsize];
gets(c);
for(i=0;i<strlen(c);i++)
{
y[i+1].x=c[i];
if(y[i+1].x!='$')
{
y[i+1].p=(bitreenode *)malloc(sizeof(bitreenode));
y[i+1].p->info=c[i];
y[i+1].p->leftchild=y[i+1].p->rightchild=NULL;
}
else
y[i+1].p=NULL;
}
for(i=1;i<=strlen(c)/2;i++)
{
y[i].p->leftchild=y[2*i].p;
if((2*i+1)>strlen(c))
break;
y[i].p->rightchild=y[2*i+1].p;
}
return(y[1].p);
}
void preorder_by_digui(bitreenode *t) //前序遍历(递归)
{
if(t)
{
printf("%c",t->info);
preorder_by_digui(t->leftchild);
preorder_by_digui(t->rightchild);
}
}
void inorder_by_digui(bitreenode *t) //中序遍历(递归)
{
if(t)
{
inorder_by_digui(t->leftchild);
printf("%c",t->info);
inorder_by_digui(t->rightchild);
}
}
void postorder_by_digui(bitreenode *t) //后序遍历(递归)
{
if(t)
{
postorder_by_digui(t->leftchild);
postorder_by_digui(t->rightchild);
printf("%c",t->info);
}
}
void preorder(bitreenode *bitree_root) //前序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
printf("%c",bitree_root->info);
pushstack(temp,bitree_root);
bitree_root=bitree_root->leftchild;
}
if(!emptystack(temp))
{
bitree_root=popstack(temp);
bitree_root=bitree_root->rightchild;
}
}
}
void inorder(bitreenode *bitree_root) //中序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
pushstack(temp,bitree_root);
bitree_root=bitree_root->leftchild;
}
if(!emptystack(temp))
{
bitree_root=popstack(temp);
printf("%c",bitree_root->info);
bitree_root=bitree_root->rightchild;
}
}
}
void postorder(bitreenode *bitree_root) //后序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
pushstack(temp,bitree_root);
temp->tag[temp->top]=0;
bitree_root=bitree_root->leftchild;
}
while(!emptystack(temp)&&temp->tag[temp->top]==1)
{ bitree_root=getstack_top(temp);
printf("%c",bitree_root->info);
temp->top--;
}
if(!emptystack(temp))
{
bitree_root=getstack_top(temp);
temp->tag[temp->top]=1;
bitree_root=bitree_root->rightchild;
}
else
bitree_root=NULL;
}
}
int depth(bitreenode *bitree_root) //求二叉树的深度
{
int h,lh,rh;
if(bitree_root==NULL)
h=0;
else
{
lh=depth(bitree_root->leftchild);
rh=depth(bitree_root->rightchild);
(lh>=rh)?(h=lh+1):(h=rh+1);
}
return(h);
}
main()
{
bitreenode *root; //指向二叉树根结点的指针
root=creatbitree();
printf("二叉树的深度为 %d\n",depth(root));
printf("前序遍历\n");
preorder(root);
printf("\n");
preorder_by_digui(root);
printf("\n中序遍历\n");
inorder(root);
printf("\n");
inorder_by_digui(root);
printf("\n后序遍历\n");
postorder(root);
printf("\n");
postorder_by_digui(root);
printf("\n");
getch();
}
转载 evil_evil C的二叉树.由于没有测试 如果下面代码有问题请发贴.我会修改!
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define maxsize 26
typedef char datatype; //结点属性值类型
typedef struct bitreenode //二叉树结点类型
{
datatype info;
struct bitreenode *leftchild,*rightchild;
}bitreenode;
typedef struct stack //栈的定义
{
bitreenode *data[maxsize];
int tag[maxsize];
int top;
}seqstack;
void initstack(seqstack *t) //栈的初始化
{
t->top=-1;
}
int emptystack(seqstack *t) //判断栈是否为空
{
return(t->top==-1?1:0);
}
void pushstack(seqstack *t,bitreenode *e) //入栈
{
t->data[++t->top]=e;
}
bitreenode *popstack(seqstack *t) //出栈
{
return(t->data[t->top--]);
}
bitreenode *getstack_top(seqstack *t) //取栈顶元素
{
return(t->data[t->top]);
}
bitreenode *creatbitree() //按深度输入完全二叉树来建立二叉树
{ //从上到下,从左到右,输入完全二叉树
int i;
struct
{
datatype x;
bitreenode *p;
}y[maxsize+1];
char c[maxsize];
gets(c);
for(i=0;i<strlen(c);i++)
{
y[i+1].x=c[i];
if(y[i+1].x!='$')
{
y[i+1].p=(bitreenode *)malloc(sizeof(bitreenode));
y[i+1].p->info=c[i];
y[i+1].p->leftchild=y[i+1].p->rightchild=NULL;
}
else
y[i+1].p=NULL;
}
for(i=1;i<=strlen(c)/2;i++)
{
y[i].p->leftchild=y[2*i].p;
if((2*i+1)>strlen(c))
break;
y[i].p->rightchild=y[2*i+1].p;
}
return(y[1].p);
}
void preorder_by_digui(bitreenode *t) //前序遍历(递归)
{
if(t)
{
printf("%c",t->info);
preorder_by_digui(t->leftchild);
preorder_by_digui(t->rightchild);
}
}
void inorder_by_digui(bitreenode *t) //中序遍历(递归)
{
if(t)
{
inorder_by_digui(t->leftchild);
printf("%c",t->info);
inorder_by_digui(t->rightchild);
}
}
void postorder_by_digui(bitreenode *t) //后序遍历(递归)
{
if(t)
{
postorder_by_digui(t->leftchild);
postorder_by_digui(t->rightchild);
printf("%c",t->info);
}
}
void preorder(bitreenode *bitree_root) //前序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
printf("%c",bitree_root->info);
pushstack(temp,bitree_root);
bitree_root=bitree_root->leftchild;
}
if(!emptystack(temp))
{
bitree_root=popstack(temp);
bitree_root=bitree_root->rightchild;
}
}
}
void inorder(bitreenode *bitree_root) //中序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
pushstack(temp,bitree_root);
bitree_root=bitree_root->leftchild;
}
if(!emptystack(temp))
{
bitree_root=popstack(temp);
printf("%c",bitree_root->info);
bitree_root=bitree_root->rightchild;
}
}
}
void postorder(bitreenode *bitree_root) //后序遍历(非递归)
{
seqstack *temp;
temp=(seqstack *)malloc(sizeof(seqstack));
initstack(temp);
while((bitree_root!=NULL)||!(emptystack(temp)))
{
while(bitree_root!=NULL)
{
pushstack(temp,bitree_root);
temp->tag[temp->top]=0;
bitree_root=bitree_root->leftchild;
}
while(!emptystack(temp)&&temp->tag[temp->top]==1)
{ bitree_root=getstack_top(temp);
printf("%c",bitree_root->info);
temp->top--;
}
if(!emptystack(temp))
{
bitree_root=getstack_top(temp);
temp->tag[temp->top]=1;
bitree_root=bitree_root->rightchild;
}
else
bitree_root=NULL;
}
}
int depth(bitreenode *bitree_root) //求二叉树的深度
{
int h,lh,rh;
if(bitree_root==NULL)
h=0;
else
{
lh=depth(bitree_root->leftchild);
rh=depth(bitree_root->rightchild);
(lh>=rh)?(h=lh+1):(h=rh+1);
}
return(h);
}
main()
{
bitreenode *root; //指向二叉树根结点的指针
root=creatbitree();
printf("二叉树的深度为 %d\n",depth(root));
printf("前序遍历\n");
preorder(root);
printf("\n");
preorder_by_digui(root);
printf("\n中序遍历\n");
inorder(root);
printf("\n");
inorder_by_digui(root);
printf("\n后序遍历\n");
postorder(root);
printf("\n");
postorder_by_digui(root);
printf("\n");
getch();
}
还是有一个错误啊