用广度优先创建二叉树（C语言），高手请进！！！ 哭！！！

longwen

我昨天看了一下图的广度优先遍历，就想用这个方法建立一棵树，主要其中用到了队列的（有点不同），结果程序没有调成。。希望大家帮一下。。
下面是我的源程序。。。
//tree.h是树的头文件，里面定义了树的结点类型binode和指向结点的指针bitree
//用的是链式存储结构  

//queue.h
//里面定义了队列的结构，一个head和rear，分别指向队列的头和尾

//create_b.c
/*
里面定义了两个函数create_bi_tree_queue() is used to create a binary tree，下面是函数bitree createnode(void)用于创建一个结点，返回结点地址。
它被上面的create_bi_tree_queue() 调用。
*/
//$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
//queue.c
/*
这里面实现了队列的操作。。它用到了队列的思想,但是他的enqueue（）和dequeue（）并没有申请空间！！！！（因为结点已经存在！！（创建树时申请了））
在这里用结点的rchild指针域充当next域
*/
//$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

//main_tes.c
//用于驱动函数。。
//tree.h

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef struct bitreenode{
  int data;
  struct bitreenode* lchild;
  struct bitreenode* rchild;
}binode , *bitree;



//queue.h

/*************************************************
queue.h is used to declare the data structue type
***************************************************/

#include "tree.h"

typedef struct {
  bitree head;
  bitree rear;
}queue;


//queue.c
/***************************************************
queue.c is to give the pro of a queue
Witer:Longwen    Date:01/06/04
***************************************************/

#include "queue.h"
#include "tree.h"
//initqueue()
int initqueue(queue *pq)
{
  if((pq->head=pq->rear=(bitree)malloc(sizeof(binode))))
    return 0;
  pq->head->lchild=pq->head->rchild=NULL;
  return 1;
}

//enqueue()
int enqueue(queue *pq,bitree T)
{
  pq->rear->rchild=T;
  pq->rear=T;
  return 1;
}

//emptyqueue()
int emptyqueue(queue q)
{
  if(q.rear==q.head)
    return 1;
  else return 0;
}

//dequeue()
int dequeue(queue *pq,bitree *ppt)
{
  if(pq->head==pq->rear)
    return 0;
  *ppt=pq->head->rchild;
  pq->head=pq->head->rchild->rchild;
  return 1;
}

//create_b.c
/*********************************************
create_bi_tree_queue() is used to create a binary tree
using a queue data structure.
Writer:Longwen     Date:01/06/04  
**********************************************/

#include "queue.h"
#include "tree.h"
bitree createnode();

int create_bi_tree_queue(bitree *pT)
{
  char ch;
  queue q;//queue.h
  if(!initqueue(&q))
    return 0;//queue.c
  if((*pT=createnode())==NULL)
    return 1;
  else if(!enqueue(&q,*pT))
          return 0;   //queue.c

  while(!emptyqueue(q))//
    {
      bitree pt;/*used for dequeue*/
      if(!dequeue(&q,&pt))
           return 0;  //queue.c
      if((pt->lchild=createnode())!=NULL)
enqueue(&q,pt->lchild);
      if((pt->rchild=createnode())!=NULL)
enqueue(&q,pt->rchild);
    }
  return 1;
}

bitree createnode(void)
{
  char ch;
  bitree temp;
  puts("Is it NULL or not?(Enter blank means NULL!)");
  scanf("%s",&ch);
  if(ch==' ')
    return(NULL);
  else
    {
      if(!(temp=(bitree)malloc(sizeof(binode))))
exit(-1);
      printf("Please input the data(a integer):\n");
while(scanf("%d",temp->data)!=1)
  fprintf(stderr,"Sorry,I can not recognize.Again.\n");
      temp->rchild=temp->lchild=NULL;
      return temp;
    }
}


//main_tes.c
/*************************************************
Used to dive the other func.
Writer:Longwen     Date:01/06/04  
************************************************/
#include "queue.c"
#include "create_b.c"

int main()
{
  bitree T;
  if(!create_bi_tree_queue(&T))
fprintf(stderr,"ERROR IN create_bi_tree_queue()\n");
  return 0;
}

quarkonics

你实现的那个队列好像不大对

quarkonics

按你的思想实现了按广度优先创建二叉树
两个头文件
queue.h:
[code:1]
#ifndef QUEUE_H
#define QUEUE_H
#include <stdlib.h>
#include <stdio.h>
#include "bitree.h"



struct queuenode{
        struct bitreenode *data;
        struct queuenode *next;
};

struct queue{
        struct queuenode *front;
        struct queuenode *rear;
};


void
init_queue(struct queue *q);

void
enqueue(struct queue *q, int data);

int
dequeue(struct queue *q);

[/code:1]
bitree.h:
[code:1]
#ifndef BITREE_H
#define BITREE_H
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

struct bitreenode {
        int data;
        struct bitreenode *lchild;
        struct bitreenode *rchild;
};


struct bitreenode *
create_bitree(void);

struct bitreenode *
create_node(void);

#endif
[/code:1]


源文件:
queue.c:
[code:1]
#include "queue.h"



void
init_queue(struct queue *q) {
        q->front = (struct queuenode *)malloc(sizeof(struct queuenode));
        if (q->front == NULL) {
                printf("malloc error\n");
                return;
        }
        q->rear = q->front;
        q->rear->next = NULL;
}


void
enqueue(struct queue *q, int data) {
        q->rear->next = (struct queuenode *)malloc(sizeof(struct queuenode));
        if (q->rear->next == NULL) {
                printf("malloc error\n");
                return;
        }
        q->rear = q->rear->next;
        q->rear->data = data;
        q->rear->next = NULL;
}


int
dequeue(struct queue *q) {
        int temp;
        struct queuenode *pNode;

        if (q->front->next == NULL) {
                return -1;
        }

        pNode = q->front->next;
        temp = pNode->data;
        q->front->next = pNode->next;
        if (q->rear == pNode) {
                q->rear = q->front;
        }
        free(pNode);

        return temp;
}


int
emptyqueue(struct queue *q) {
        return (q->front->next == NULL);
}


void
printqueue(struct queue *q) {
        struct queuenode *pNode = q->front->next;


        while (pNode != NULL) {
                printf("%d->", pNode->data);
                pNode = pNode->next;
        }

        printf("NULL\n");
}

[/code:1]


bitree.c:
[code:1]
#include "bitree.h"


struct bitreenode *
create_node(void) {
        char temp[10];
        struct bitreenode *pNode;

        printf("Is it NULL or not?(Enter blank means NULL!)\n");
        scanf("%s", temp);
        if (temp[0] == 'n')
                return NULL;
        else {
                if(!(pNode = (struct bitreenode *)malloc(sizeof(struct bitreenode))))
                        exit(-1);
                printf("Please input the data(a integer):\n");
                while (scanf("%d", &pNode->data) != 1)
                        fprintf(stderr,"Sorry,I can not recognize.Again.\n");
                pNode->rchild = pNode->lchild = NULL;
                return pNode;        
        }
        return NULL;
}


struct bitreenode *
create_bitree(void) {
        struct queue q;
        struct bitreenode *bt;
        struct bitreenode *pNode;

       
        init_queue(&q);
       
        bt = create_node();
        enqueue(&q, bt);

        while (!emptyqueue(&q)) {
                pNode = dequeue(&q);
                pNode->lchild = create_node();
                if (pNode->lchild != NULL)
                        enqueue(&q, pNode->lchild);
                pNode->rchild = create_node();
                if (pNode->rchild != NULL)
                        enqueue(&q, pNode->rchild);
        }

        return bt;
}

[/code:1]

longwen

非常感谢！！！！！！！！
！！！！！！！！！！！！！！！！！！111

sagaeon

quarkonics兄，常来啊！  

longwen

不错，我从你的启发里找到了我的错误
但是你这样做浪费了不少空间和效率
不过你的编程格式比我强百倍

quarkonics

不错，我从你的启发里找到了我的错误
但是你这样做浪费了不少空间和效率
不过你的编程格式比我强百倍

不大明白
说说你得想法

longwen

你在进队是申请空间了。在这里是不用的。（只要将已申请的空间连成队列。）
你调一下程序。。还是有错误。。

我有铁了个智能编码程序。。希望指教

quarkonics

你在进队是申请空间了。在这里是不用的。（只要将已申请的空间连成队列。）
你调一下程序。。还是有错误。。

不申请空间，你怎么储存树节点得地址，并把这些地址链成队列，除非在节点结构里边添加新得域

longwen

[quote:2059dfcdff="quarkonics"]

你在进队是申请空间了。在这里是不用的。（只要将已申请的空间连成队列。）
你调一下程序。。还是有错误。。

不申请空间，你怎么储存树节点得地址，并把这些地址链成队列，除非在节点结构里边添加新得域[/quote]


[code:1]
int enqueue(queue *pq,bitree T)
{
pq->rear->rchild=T;
pq->rear=T;
return 1;
}

[/code:1]

这个算法说是按层序遍历创建更为合适..
不用申请空间,是将已经创建的结点(总是树的最下层结点(左右子树指针为空))放到队列中....

队列中是树的叶子结点...

希望大家继续讨论..顺便调出最终代码

longwen

[quote:99411faa76="quarkonics"]

你在进队是申请空间了。在这里是不用的。（只要将已申请的空间连成队列。）
你调一下程序。。还是有错误。。

不申请空间，你怎么储存树节点得地址，并把这些地址链成队列，除非在节点结构里边添加新得域[/quote]


[code:1]
int enqueue(queue *pq,bitree T)
{
pq->rear->rchild=T;
pq->rear=T;
return 1;
}

[/code:1]

这个算法说是按层序遍历创建更为合适..
不用申请空间,是将已经创建的结点(总是树的最下层结点(左右子树指针为空))放到队列中....

队列中是树的叶子结点...

希望大家继续讨论..顺便调出最终代码

quarkonics

恩，大概明白什么意思了，聪明得做法