学习日记五：层次建立二叉树
1.先建立根节点，根节点数据为0则为空树，返回NULL根结点地址压入队。
2.如果队列不为空，出队，记录出队结点地址
读入数据，如果不为0，给出队结点左孩子开辟空间并赋值，然后将左孩子地址入队
读入数据如果不为0，给出队结点右孩子开辟空间并赋值，然后将右孩子地址入队。
3.重复步骤2，直到队列为空。
层次建立大致就这个方法吧，方法并不难，可代码老写错。
建立队列时，第一次我先给队列的队首队尾赋初值0了，入队：读入数据，队尾加1。出队：返回数据，队首加1。
判断队列为空条件队首队尾下标相同。
目前还不知道错误原因
第二次给队列的队首赋初值0，队尾赋初值-1，入队：队尾加1，读入数据。 出队：返回数据，队首加1.
判断队列为空条件：队首下标大于队尾下标
这次对了。两个结果对比一下。（中序遍历二叉树）
正确的代码：
程序代码：#include <stdio.h>
#include <stdlib.h>
#define MaxSize 30
typedef struct QueueNode* PtrQType ;
typedef struct BinTreeNode* PtrBTType ;
//二叉树结点结构体
struct BinTreeNode
{
int BTNodeData ;
struct BinTreeNode* Right;
struct BinTreeNode* Left ;
} ;
//顺序队列
struct QueueNode
{
struct BinTreeNode* AddressData[MaxSize] ;//指针数组，数组中保存的是地址
int rear ;
int front ;
} ;
//队列的初始化
PtrQType InitializeQ( )
{
PtrQType Q ;
Q = (PtrQType)malloc( sizeof(struct QueueNode) );
Q->rear = -1 ;
Q->front= 0 ;
return Q ;
}
//队列是否为空
int IsEmptyQ( PtrQType Q )
{
if( Q->front > Q->rear )
return 1 ;
else
return 0 ;
}
//队列是否已满
int IsFullQ( PtrQType Q )
{
if(Q->rear == MaxSize-1 )
return 1 ;
else
return 0 ;
}
//入队
void AddQ( PtrQType Q , struct BinTreeNode* T)
{
int IsFullQ( PtrQType Q ) ;//函数声明
if( !IsFullQ( Q ))
{
Q->rear++ ;
Q->AddressData[Q->rear] = T ;
}
else printf("队列已满，停止添加数据\n") ;
}
//出队，并返回队列结点数据（地址）
PtrBTType DeleteQ( PtrQType Q )
{
int IsFullQ( PtrQType Q ) ;//函数声明
int i ;
i = Q->front ;
if( !IsEmptyQ(Q) )
{
Q->front++ ;
return Q->AddressData[ i ] ;
}
else printf("队列已空\n");
}
//层序建立二叉树
PtrBTType CreateBT( )
{
void AddQ( PtrQType Q , struct BinTreeNode* T) ;
PtrBTType DeleteQ( PtrQType Q ) ;
PtrQType InitializeQ( ) ;
int IsEmptyQ( PtrQType Q ) ;
int Data ;
PtrBTType BT , T ;
PtrQType Q ;
//初始化队列
Q = InitializeQ( ) ;
//输入根结点数据
BT = ( PtrBTType )malloc(sizeof(struct BinTreeNode)) ;
// BT->Left = NULL ;
// BT->Right = NULL ;
scanf("%d",&BT->BTNodeData ) ;
if( BT->BTNodeData )//如果根节点数据不为0，将根节点地址入队,否则返回空树
AddQ( Q, BT ) ;
else return NULL ;
while( !IsEmptyQ(Q) )//当队列不为空
{
//初始化左右儿子结点
T = DeleteQ( Q ) ;
scanf("%d",&Data) ;//输入左儿子结点数据
if(Data)
{
T->Left = ( PtrBTType )malloc(sizeof(struct BinTreeNode)) ;
T->Left->BTNodeData = Data ;
//T->Left->Left = T->Left->Right = NULL ;
AddQ( Q,T->Left ) ;
}
else T->Left = NULL ;
scanf("%d",&Data) ;//输入右儿子结点数据
if(Data)
{
T->Right = ( PtrBTType )malloc(sizeof(struct BinTreeNode)) ;
T->Right->BTNodeData = Data ;
//T->Right->Left = T->Right->Right = NULL ;
AddQ( Q,T->Right ) ;
}
else T->Right = NULL ;
}
return BT ;
}
void InOrderTraversal( PtrBTType BT )
{
if(BT)
{
InOrderTraversal( BT->Left ) ;
printf("%d ",BT->BTNodeData ) ;
InOrderTraversal( BT->Right ) ;
}
}
int main()
{
PtrBTType BT ;
printf("请输入树（层次建立）\n") ;
BT = CreateBT() ;
//中序遍历
InOrderTraversal(BT);
}错误的代码：
程序代码：#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 ;
BT->Left = BT->Right = NULL;
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 ;
T->Left->Left = T->Left->Right = NULL;
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 ;
T->Right->Left = T->Right->Right = NULL;
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 ) ;
}
