二叉树的层次建立,错在哪里

C语言 码拜 8年前 (2015-11-16) 849次浏览
找了好久找不到,能通过编译,可无法输出
这里面的二叉树结点数据为整数,当整数输入为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 ) ;

}
解决方案:10分
二叉树, 每个结点可能有两个子结点, T = DeleteQ( PtrQ ) ;之后应该直接scanf(“%d%d”, &T->Left->BTNodeData,&T->Right->BTNodeData), 你的代码是弹出队首, 读一个, 再弹一个
解决方案:30分
建议修改如下:

#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");
}
//出队,并返回队首(树的地址)
int IsEmpty( PtrQType PtrQ );
PtrBT DeleteQ( PtrQType PtrQ )
{
  int i ;
  if( !IsEmpty(PtrQ) )
  {
    i=PtrQ->front ;
    PtrQ->front++ ;
    return PtrQ->AddressData[i] ;
  }
  else {printf("队列已空\n"); return NULL;} //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 ) //改 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 ;
    if (IsEmpty(PtrQ)) break; //加
    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 ) ;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明二叉树的层次建立,错在哪里
喜欢 (0)
[1034331897@qq.com]
分享 (0)