看看这个完全二叉树的判定算法问题出在哪里？ - 数据结构与算法

已结贴√ 问题点数：20 回复次数：2

看看这个完全二叉树的判定算法问题出在哪里？

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//////////////////////////////////////////////队列定义
typedef struct QNode
{
    BiTree data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
////////////////////////////////////队列的基本操作
void InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) exit(0);
    Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
    while(Q->front)//*******
    {
        Q->rear=Q->front->next;
        free(Q->front);
        Q->front=Q->rear;
    }
}
void EnQueue(LinkQueue *Q,BiTNode *e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(0);
    p->data=e;//说明这个结点的两个域1
    p->next=NULL;//2
    Q->rear->next=p;
    Q->rear=p;
}
void DeQueue(LinkQueue *Q,BiTree *e)
{
    QueuePtr p;
    if(Q->front==Q->rear) exit(0);
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
//    free(p);
    if(Q->rear==p)
        Q->rear=Q->front;
    free(p);//
}
int QueueEmpty(LinkQueue *Q)
{
    if(Q->front==Q->rear)
        return(1);
    else
        return(0);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
BiTree CreatBiTree()//先序建立二叉链表
{
    TElemType ch;
    BiTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(0);
        T->data=ch;
        T->lchild=CreatBiTree();
        T->rchild=CreatBiTree();
    }
    return T;
}

//判断是否为完全二叉树
int LayerTraverse(BiTree T)//通过层序遍历改编
{

    int flag=1;//默认其为完全二叉树
    LinkQueue queue;
    InitQueue(&queue);
    if(T)
        EnQueue(&queue,T);
    else
    {
        printf("该树为空树!\n");
        exit(0);
    }
    while(!QueueEmpty(&queue))
    {
        DeQueue(&queue,&T);
        if((T==NULL)&&(!QueueEmpty(&queue)))//出队列元素是空指针且此时队列不为空，则可以判断该树不为完全二叉树,返回假值
        {
            flag=0;
            break;
        }
        if(T->lchild||T->rchild)//T->rchild
            break;
        else//有一个不为空就进队列
        {
            EnQueue(&queue,T->lchild);//左子树进队列
            EnQueue(&queue,T->rchild);//右子树进队列
        }
    }
    return(flag);
}
void main()
{
    BiTree t;
    printf("<------------先序建树--------------->\n");
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<参考数据:abc@@de@g@@f@@@，则用空格键表示@，输完后再输入一个回车键.>\n");
    t=CreatBiTree();
    printf("\n");
    printf("<------判断是否为完全二叉树操作---->\n");
    if(LayerTraverse(t))
        printf("该二叉树是完全二叉树!\n");
    else
        printf("该二叉树不是完全二叉树!\n");
}

搜索更多相关主题的帖子: 二叉树　算法　

第 2 楼

得分:20

对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查:
  (1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树;
  (2)如果当前结点有右子树,则它必须也有左子树.
  如果同时满足(1)(2),则是完全二叉树;否则不是.
你看看你那一条不满足。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//////////////////////////////////////////////队列定义
typedef struct QNode
{
    BiTree data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
////////////////////////////////////队列的基本操作
void InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) exit(0);
    Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
    while(Q->front)//*******
    {
        Q->rear=Q->front->next;
        free(Q->front);
        Q->front=Q->rear;
    }
}
void EnQueue(LinkQueue *Q,BiTNode *e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(0);
    p->data=e;//说明这个结点的两个域1
    p->next=NULL;//2
    Q->rear->next=p;
    Q->rear=p;
}
void DeQueue(LinkQueue *Q,BiTree *e)
{
    QueuePtr p;
    if(Q->front==Q->rear) exit(0);
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
//    free(p);
    if(Q->rear==p)
        Q->rear=Q->front;
    free(p);//
}
int QueueEmpty(LinkQueue *Q)
{

 QueuePtr tfront = Q->front;
    if(Q->front==Q->rear)
        return(1);
    else

 {
  while (tfront != Q->rear)
  {
   if (tfront != NULL)
    return 0;
  }
        return 1;

 }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
BiTree CreatBiTree()//先序建立二叉链表
{
    TElemType ch;
    BiTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(0);
        T->data=ch;
        T->lchild=CreatBiTree();
        T->rchild=CreatBiTree();
    }
    return T;
}

//判断是否为完全二叉树
int LayerTraverse(BiTree T)//通过层序遍历改编
{

 // 对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查:  

 // (1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树;  

 // (2)如果当前结点有右子树,则它必须也有左子树. 


 bool flag = true;

 bool bcomfine = false;
    LinkQueue queue;
    InitQueue(&queue);
    if(T)
        EnQueue(&queue,T);
    else
    {
        printf("该树为空树!\n");
  return true;
    }
    while(!QueueEmpty(&queue))
    {
        DeQueue(&queue,&T);
  if (!T->lchild && T->rchild)
   return flag=false;
  if (bcomfine && (T->lchild || T->rchild))
   return flag = false;

  if (T->lchild != NULL)
   EnQueue(&queue, T->lchild);
  if (T->rchild != NULL)
   EnQueue(&queue, T->rchild);
  else
   bcomfine = true;
    }
    return(flag);
}
void main()
{
    BiTree t;
    printf("<------------先序建树--------------->\n");
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<参考数据:abc@@de@g@@f@@@，则用空格键表示@，输完后再输入一个回车键.>\n");
    t=CreatBiTree();
    printf("\n");
    printf("<------判断是否为完全二叉树操作---->\n");
    if(LayerTraverse(t))
        printf("该二叉树是完全二叉树!\n");
    else
        printf("该二叉树不是完全二叉树!\n");
}

编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段

第 3 楼

得分:0

明白了