回 帖 发 新 帖 刷新版面

主题:二叉树的创建?

在学习数据结构的时候,关于二叉树的创建的代码,我怎么总是看不懂啊?他有什么特殊的地方吗?到底应该怎样合理的创建它啊?

回复列表 (共12个回复)

沙发

二叉树可以采用前序中序后序的方式创建,也可以用层次法创建,或是其它方法。课本上好象举了一个先序递归的吧?也没有什么特殊的,主要就是利用递归来进行了。你有什么疑问可以详细提出来。

板凳

二叉树 可以用递归或队列创建
 多数使用递归

3 楼

用递归了,比如:创建完根结点,再创的左子树,然后右子树

4 楼

看看行不行:

#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 楼

程序里面不用goto是一个好习惯!!!!!!!

6 楼


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 楼

学习~~~~

8 楼

我的一个算法 需要一个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 楼

课本上的递归创建二叉树的方法:
#define leng sizeof(struct bnode)  //结点所占空间的大小
void creat_tree(struct bnode **root)
//root是指向二叉链表根指针的指针
{ char ch;
  scanf("%c",&ch);  //输入一个结点,假定为字符型
  if (ch =='&#61510;') (*root)=NULL;
  else
  { (*root)=(struct bnode *)malloc(leng);
    (*root)->data=ch;              //生成根结点
     creat_tree(&(*root)->lchild); //递归构造左子树
     creat_tree(&(*root)->rchild); //递归构造右子树
   }
  return;
 }

10 楼

怎样跳出创建的循环啊,谁知道?

我来回复

您尚未登录,请登录后再回复。点此登录或注册