| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2368 人关注过本帖
标题:[原创]二叉树,有中,后,前序……都有了,呵呵
只看楼主 加入收藏
coolg
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2006-5-21
收藏
得分:0 

楼上的签名好点性别歧视呀!!!哼哼

[此贴子已经被作者于2006-5-28 20:30:28编辑过]


2006-05-28 20:29
mechanics
Rank: 1
等 级:新手上路
帖 子:87
专家分:0
注 册:2006-5-16
收藏
得分:0 
好东西

2006-05-30 00:34
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 

转载 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();

}


[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-05-30 11:27
kglyt
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-5-30
收藏
得分:0 
以下是引用SunShining在2006-5-30 11:27:00的发言:

转载 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();

}

还是有一个错误啊

2006-05-30 15:58
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 
以下是引用kglyt在2006-5-30 15:58:00的发言:

还是有一个错误啊

TC编译无错误.C-FREE编译无错误...建议用C-FREE.VC应该也可以吧!


[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-05-30 16:27
kehnoye
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2007-4-13
收藏
得分:0 
刚开始教树 不大懂 回去研究一下
2007-04-13 10:26
快速回复:[原创]二叉树,有中,后,前序……都有了,呵呵
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.061917 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved