主题:二叉树的创建?
lishiyong110
[专家分:300] 发布于 2006-07-30 07:54:00
在学习数据结构的时候,关于二叉树的创建的代码,我怎么总是看不懂啊?他有什么特殊的地方吗?到底应该怎样合理的创建它啊?
回复列表 (共12个回复)
沙发
雨523 [专家分:200] 发布于 2006-07-30 09:38:00
二叉树可以采用前序中序后序的方式创建,也可以用层次法创建,或是其它方法。课本上好象举了一个先序递归的吧?也没有什么特殊的,主要就是利用递归来进行了。你有什么疑问可以详细提出来。
板凳
dorremon1992 [专家分:870] 发布于 2006-07-31 11:37:00
二叉树 可以用递归或队列创建
多数使用递归
3 楼
海上飞洪 [专家分:520] 发布于 2006-08-02 10:37:00
用递归了,比如:创建完根结点,再创的左子树,然后右子树
4 楼
tgbtgb [专家分:490] 发布于 2006-08-19 10:02:00
看看行不行:
#include"malloc.h"
#include"stdio.h"
typedef struct three1
{char data;
struct three1 *l;
struct three1 *r;
}tree;
int g=0,d=0,x=0,y=0;
tree *creat(void)
{ tree *q;
d++;
char ch,mm;
scanf("%c",&mm);
printf("NO.%d\n",d);
scanf("%c",&ch);
if(ch==' ')
{ q=NULL;
return NULL;}
else
{
q=(tree *)(malloc(sizeof(tree)));
q->data=ch;
q->l=creat();
q->r=creat();
}
return q;
}
void visit1(tree *f)
{g++;
if(f!=NULL)
{if(g==1)
goto look_1;
/*printf("(->)");*/
look_1:
printf("%c",f->data);
visit1(f->l);
visit1(f->r);
}
/*else
printf("(->)@");
*/}
void visit2(tree *k)
{x++;
if(k!=NULL)
{if(x==1)
goto look_1;
/*printf("(->)");
*/look_1:
visit2(k->l);
printf("%c",k->data);
visit2(k->r);
}
/*else
printf("(->)@");
*/}
void visit3(tree *b)
{y++;
if(b!=NULL)
{if(y==1)
goto look_1;
/*printf("(->)");
*/look_1:
visit3(b->l);
visit3(b->r);
printf("%c",b->data);
}
/*else
printf("(->)@");
*/}
main()
{tree *head;
int fage;
int i;
fage=1;
printf("注意在第一次使用时必须先建立二杈树.\n");
do{ printf("\n");
printf("\n");
printf("\n");
printf("\n");
printf("\t*******菜单栏**************\n");
printf("\t1----------建立二杈树.\n");
printf("\t2----------先序遍历二杈树.\n");
printf("\t3----------中序遍历二杈树.\n");
printf("\t4----------后序遍历二杈树.\n");
printf("\t0----------退出\n");
printf("\t**************************\n");
printf("\n");
printf("请选择(注意:一定要是数字):\n");
scanf("%d",&i);
switch(i)
{
case 0:fage=0;break;
case 1: printf("开始:\n");head=creat(); break;
case 2: visit1(head);break;
case 3:visit2(head);break;
case 4:visit3(head);break;
defult:printf("您的选择错误.\n");
}
}
while (fage);
return 1;
}
5 楼
ysol [专家分:10] 发布于 2006-08-20 15:44:00
程序里面不用goto是一个好习惯!!!!!!!
6 楼
ysol [专家分:10] 发布于 2006-08-20 16:10:00
tree *creat(void)
{ tree *q;
d++;
char ch,mm;
[color=FF0000]fflush(stdin);[/color]清缓冲区中的回车
scanf("%c",&mm);
printf("NO.%d\n",d);
[color=FF0000]fflush(stdin);[/color]清缓冲区中的回车
scanf("%c",&ch);
if(ch==' ') { q=NULL;
return NULL;}
else
{
q=(tree *)(malloc(sizeof(tree)));
q->data=ch;
q->l=creat();
q->r=creat();
}
return q;
}
7 楼
gugen [专家分:0] 发布于 2006-08-27 23:45:00
学习~~~~
8 楼
polaris912 [专家分:30] 发布于 2006-08-29 18:44:00
我的一个算法 需要一个insert函数 帮助创建排序二叉树
void insert_bnode(struct bnode **root,float key)
{
struct bnode *f,*p=*root //the pointer indicate the rootnode of the BST
while(p) //search the insert position
{
if(p->key==key) return; //already have it
f=p; //to save current searching node
p=(key<p->key)?p->lchild:p->rchild; //if key<p->key,search in the left-part
} //end while
p=(struct bnode *)malloc(leng);
p->key=key;
p->lchild=p->rchild=NULL;
if(*root==NULL) //if there is no such tree make p rootnode
*root=p;
else
if(key<f->key) //if key<f-key,make it left-child
f->lchild=p;
else
f->rchild=p;
} //insert_bnode
(struct bnode*) creat_tree(void)
{ //input a series of number, creat a BST and return the root pointer
struct bnode *root=NULL; //inite a empty tree
float key;
scanf(%f,&key);
while(!(key==0dh))
insert_node(&root,key);
scanf(%f,&key);
}
return root;
} //creat_tree
9 楼
polaris912 [专家分:30] 发布于 2006-08-29 18:49:00
课本上的递归创建二叉树的方法:
#define leng sizeof(struct bnode) //结点所占空间的大小
void creat_tree(struct bnode **root)
//root是指向二叉链表根指针的指针
{ char ch;
scanf("%c",&ch); //输入一个结点,假定为字符型
if (ch =='') (*root)=NULL;
else
{ (*root)=(struct bnode *)malloc(leng);
(*root)->data=ch; //生成根结点
creat_tree(&(*root)->lchild); //递归构造左子树
creat_tree(&(*root)->rchild); //递归构造右子树
}
return;
}
10 楼
芷刀雪狐 [专家分:0] 发布于 2006-11-17 19:59:00
怎样跳出创建的循环啊,谁知道?
我来回复