- 完全二叉树判断问题
- 完全二叉树判断问题
基本功能与要求
1 编写一个创建二叉树的
2 编写算法判断一个给定的二叉树是否为完全二叉树
3 编写一个测试主函数，要求测试主函数中要包括是完全二叉树和不是完全二叉树两种情况
- 1。
创建 并 中序遍历输出
#include
#include
typedef enum{Link,Thread} PointerTag; //指针标志
typedef int DataType;
typedef struct BiThreTree{ //定义结点元素
PointerTag LTag,RTag;
DataType data;
struct BiThreTree *lchild,*rchild;
}BiThreTree;
BiThreTree *pre; //全局变量，用于二叉树的线索化
BiThreTree *CreateTree() //按前序输入建立二叉树
{
BiThreTree *T;
DataType e;
scanf("%d",&e);
if(e==0)
T=NULL;
else
{T=(BiThreTree *)malloc(sizeof(BiThreTree));
T->data=e;
T->LTag=Link; //初始化时指针标志均为Link
T->RTag=Link;
T->lchild=CreateTree();
T->rchild=CreateTree();
}
return T;
}
void InThread(BiThreTree *T)
{
BiThreTree *p;
p=T;
if(p)
{
InThread(p->lchild);
if(!p->lchild)
{ p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)
{ pre->RTag=Thread;
pre->rchild=p;
}
pre=p;
InThread(p->rchild);
}
}
BiThreTree *InOrderThrTree(BiThreTree *T) //中序线索化二叉树
{
BiThreTree *Thre; //Thre为头结点的指针
Thre=(BiThreTree *)malloc(sizeof(BiThreTree));
Thre->lchild=T;
Thre->rchild=Thre;
pre=Thre;
InThread(T);
pre->RTag=Thread;
pre->rchild=Thre;
Thre->rchild=pre;
return Thre;
}
void InThrTravel(BiThreTree *Thre) //中序遍历二叉树
{
BiThreTree *p;
p=Thre->lchild;
while(p!=Thre) //指针回指向头结点时结束
{
while(p->LTag==Link)
p=p->lchild;
printf("%4d",p->data);
while(p->RTag==Thread&&p->rchild!=Thre)
{p=p->rchild;
printf("%4d",p->data);
}
p=p->rchild;
}
}
int main()
{
BiThreTree *T,*Thre;
T=CreateTree();
Thre=InOrderThrTree(T);
InThrTravel(Thre);
system("pause");
}
******************************************
2。
struct node
{
T value;
node * left, * right;
};
//traverse binary tree in pre-order fashion. * pMaxH should be
//-1 initially indicating the value of * pMaxH be invalid
int Traverse (node * pNode, int H, int * pMaxH, int * pMinH)
{
int ret = 0;
if (pNode == 0)
{
//external node
if (* pMaxH == -1)
{
//the first external node
* pMaxH = H;
* pMinH = H - 1;
ret = 1;
}
else
{
if (H == * pMaxH)
{
ret = 1;
}
else
{
if (H == * pMinH)
{
* pMaxH = H;
ret = 1;
}
}
}
}
else
{
if ((ret = Traverse (pNode->left, H + 1, pMaxH, pMinH)) == 1)
ret = Traverse (pNode->right, H + 1, pMaxH, pMinH);
}
return ret;
}
***************************************************
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;
}