这里面的二叉树结点数据为整数,当整数输入为0时表示该结点不存在
程序代码:
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 30
typedef struct QueueNode* PtrQType ;
typedef struct BinTreeNode* PtrBT ;
//二叉树结点结构体
struct BinTreeNode
{
int BTNodeData ;
struct BinTreeNode* Right;
struct BinTreeNode* Left ;
} ;
//顺序队列
struct QueueNode
{
struct BinTreeNode* AddressData[MaxSize] ;//指针数组,数组中保存的是地址
int rear ;
int front ;
} ;
//队列的初始化
PtrQType CreateQueue( )
{
PtrQType PtrQ ;
PtrQ=(struct QueueNode*)malloc(sizeof(struct QueueNode));
PtrQ->front=0 ;
PtrQ->rear=0 ;
return PtrQ ;
}
//入队
void AddQ( PtrQType PtrQ , struct BinTreeNode* a )
{
int IsFull( PtrQType PtrQ ) ;
//判断队列是否已满
if( !IsFull(PtrQ) )//没满添加数据
{
(PtrQ->AddressData[PtrQ->rear]) = a ;
(PtrQ->rear)++ ;
}
else
printf("队列已满,停止入队\n");
}
//出队,并返回队首(树的地址)
PtrBT DeleteQ( PtrQType PtrQ )
{
int i ;
if( !IsEmpty(PtrQ) )
{
i=PtrQ->front ;
PtrQ->front++ ;
return PtrQ->AddressData[i] ;
}
else printf("队列已空\n") ;
}
//队列是否已满
int IsFull( PtrQType PtrQ )
{
if (PtrQ->rear == MaxSize-1)
return 1 ;
else
return 0 ;
}
//队列已空
int IsEmpty( PtrQType PtrQ )
{
if( PtrQ->front > PtrQ->rear )
return 1 ;
else
return 0 ;
}
PtrBT CreateBinTree( )
{
//函数声明
PtrQType CreateQueue( ) ; //队列初始化
void AddQ( PtrQType PtrQ , struct BinTreeNode* a ) ; //入队
PtrBT DeleteQ( PtrQType PtrQ ) ; //出队
int Data ;
PtrBT BT,T ;
PtrQType PtrQ ;
BT = NULL ; //树的初始化
T = NULL ;
PtrQ = CreateQueue() ;
scanf("%d",&Data) ; //读入数根节点数据,数据为0则输出空树
if( Data )
{
BT = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
BT->BTNodeData = Data ;
AddQ( PtrQ , BT ) ;
}
else return NULL ;
while( !IsEmpty(PtrQ) ) //当队列非空时执行...
{
T = DeleteQ( PtrQ ) ; //弹出队首,地址赋给指针T
scanf("%d",&Data) ; //读入左儿子结点数据
if( Data ) //左儿子结点读入数据,并将左儿子结点指针入队
{
T->Left = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
T->Left->BTNodeData = Data ;
AddQ( PtrQ , T->Left ) ;
}
else T->Left=NULL ;
T = DeleteQ( PtrQ ) ;
scanf("%d",&Data) ; //读入右儿子结点数据
if( Data ) //右儿子结点读入数据,并将右儿子结点指针入队
{
T->Right = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
T->Right->BTNodeData = Data ;
AddQ( PtrQ , T->Right ) ;
}
else T->Right=NULL ;
}
return BT ;
}
void InOrderTraversal( PtrBT BT )
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d",BT->BTNodeData);
InOrderTraversal(BT->Right);
}
}
int main( )
{
PtrBT BT ;
printf("请输入树(层次建立)\n") ;
BT = CreateBinTree() ;
//中序遍历
InOrderTraversal(BT);
printf( "层次输出树:\n" ) ;
// PrintfBT( BT ) ;
}
#include <stdlib.h>
#define MaxSize 30
typedef struct QueueNode* PtrQType ;
typedef struct BinTreeNode* PtrBT ;
//二叉树结点结构体
struct BinTreeNode
{
int BTNodeData ;
struct BinTreeNode* Right;
struct BinTreeNode* Left ;
} ;
//顺序队列
struct QueueNode
{
struct BinTreeNode* AddressData[MaxSize] ;//指针数组,数组中保存的是地址
int rear ;
int front ;
} ;
//队列的初始化
PtrQType CreateQueue( )
{
PtrQType PtrQ ;
PtrQ=(struct QueueNode*)malloc(sizeof(struct QueueNode));
PtrQ->front=0 ;
PtrQ->rear=0 ;
return PtrQ ;
}
//入队
void AddQ( PtrQType PtrQ , struct BinTreeNode* a )
{
int IsFull( PtrQType PtrQ ) ;
//判断队列是否已满
if( !IsFull(PtrQ) )//没满添加数据
{
(PtrQ->AddressData[PtrQ->rear]) = a ;
(PtrQ->rear)++ ;
}
else
printf("队列已满,停止入队\n");
}
//出队,并返回队首(树的地址)
PtrBT DeleteQ( PtrQType PtrQ )
{
int i ;
if( !IsEmpty(PtrQ) )
{
i=PtrQ->front ;
PtrQ->front++ ;
return PtrQ->AddressData[i] ;
}
else printf("队列已空\n") ;
}
//队列是否已满
int IsFull( PtrQType PtrQ )
{
if (PtrQ->rear == MaxSize-1)
return 1 ;
else
return 0 ;
}
//队列已空
int IsEmpty( PtrQType PtrQ )
{
if( PtrQ->front > PtrQ->rear )
return 1 ;
else
return 0 ;
}
PtrBT CreateBinTree( )
{
//函数声明
PtrQType CreateQueue( ) ; //队列初始化
void AddQ( PtrQType PtrQ , struct BinTreeNode* a ) ; //入队
PtrBT DeleteQ( PtrQType PtrQ ) ; //出队
int Data ;
PtrBT BT,T ;
PtrQType PtrQ ;
BT = NULL ; //树的初始化
T = NULL ;
PtrQ = CreateQueue() ;
scanf("%d",&Data) ; //读入数根节点数据,数据为0则输出空树
if( Data )
{
BT = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
BT->BTNodeData = Data ;
AddQ( PtrQ , BT ) ;
}
else return NULL ;
while( !IsEmpty(PtrQ) ) //当队列非空时执行...
{
T = DeleteQ( PtrQ ) ; //弹出队首,地址赋给指针T
scanf("%d",&Data) ; //读入左儿子结点数据
if( Data ) //左儿子结点读入数据,并将左儿子结点指针入队
{
T->Left = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
T->Left->BTNodeData = Data ;
AddQ( PtrQ , T->Left ) ;
}
else T->Left=NULL ;
T = DeleteQ( PtrQ ) ;
scanf("%d",&Data) ; //读入右儿子结点数据
if( Data ) //右儿子结点读入数据,并将右儿子结点指针入队
{
T->Right = ( PtrBT )malloc(sizeof(struct BinTreeNode) ) ;
T->Right->BTNodeData = Data ;
AddQ( PtrQ , T->Right ) ;
}
else T->Right=NULL ;
}
return BT ;
}
void InOrderTraversal( PtrBT BT )
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d",BT->BTNodeData);
InOrderTraversal(BT->Right);
}
}
int main( )
{
PtrBT BT ;
printf("请输入树(层次建立)\n") ;
BT = CreateBinTree() ;
//中序遍历
InOrderTraversal(BT);
printf( "层次输出树:\n" ) ;
// PrintfBT( BT ) ;
}