| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1558 人关注过本帖
标题:判断二叉树是否是完全二叉树的算法?
取消只看楼主 加入收藏
kehnoye
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2007-4-13
收藏
 问题点数:0 回复次数:0 
判断二叉树是否是完全二叉树的算法?

各位帮我看看这道“判断二叉树是否是完全二叉树”,我自己照别人算法写的 ,哪位大侠能帮我改改,然后告诉一下怎么测试
要求:
(1)用二叉链表作存储结构,写出相应的算法。
(2)要求从键盘上录入相应的二叉树的结点。
(3)利用完全二叉树的性质及树的层次遍历实现该算法,并在屏幕上输出相应的判定结果。
急用 课程设计就剩一个星期了,快点哦

#include "stdafx.h"
#include "stdlib.h"

typedef int Status;
typedef int QElemType;

#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define MAX_TREE_DEGREE 10
typedef struct BTnode{//以二叉链表作为存储结构
char data;
struct BTnode* lchild;
struct BTnode* rchild;
}BTnode,*BTree;

Status CreateBiTree(BTree &T)
{ /* 按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),*/
/* 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。*/
char ch;
scanf("%c",&ch);
if(ch==' ') /* 空 */
T=NULL;
else{
if(!(T=(BTnode *)malloc(sizeof(BTnode)))) /* 生成根结点 */
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild); /* 构造左子树 */
CreateBiTree(T->rchild);/* 构造右子树 */
}
return OK;
}

/*单链队列--队列的链式存储结构 */
typedef struct QNode
{
BTree data;
struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
int initqueue(LinkQueue Q)//队列初始化
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit (OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status enqueue(LinkQueue Q,BTree e)//入队
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status dequeue(LinkQueue Q,BTree e)//出队
{
if(Q.front==Q.rear)
return ERROR;
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
Status queueempty(LinkQueue Q)//判断队列是不是空的
{
if(Q.front==Q.rear)
return ERROR;
else
return OK;
}

Status iscompletetree(BTree T)//判断是否是完全二叉树、
{
LinkQueue Q;
BTree p;
p=T;
if(!T)
return 0;
enqueue(Q,p);
while(queueempty(Q))
{ dequeue(Q,p);
if(p)
{
enqueue(Q,p->lchild);
enqueue(Q,p->rchild);
}
if(!p)
{
while(queueempty(Q))
{

dequeue(Q,p->rchild);
if(p)
{
printf("不是完全二叉树");
return ERROR;
}
}

}
}
return OK;
}


int main(void)//简单测试
{

BTree root;
CreateBiTree(root);
iscompletetree(root);
return ERROR;
}

搜索更多相关主题的帖子: 二叉树 算法 判断 
2007-06-28 14:36
快速回复:判断二叉树是否是完全二叉树的算法?
数据加载中...
 
   



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

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