很简单的树问题，大家请帮忙

Question

怎么没有人理我二叉树我知道，但是我手头没有这些算法了，写了一个递归调用的模块，可是总是遇到错误

Answer 1

#include <stdio.h> 
#include <malloc.h> #define TRUE 1 
#define FALSE 0 
typedef int BOOL; typedef char DATATYPE; 
typedef struct _node 
{ 
DATATYPE Data; 
struct _node *pLeft; 
struct _node *pRight; 
} NODE; /*队列*/ 
typedef struct 
{ 
BOOL bIsEmpty; 
int nFront; 
int nRear; 
int nSize; 
NODE **pData; 
} QUEUE; /*队列初始化。nSize = 数组大小*/ 
void InitQueue(QUEUE *pQue, int nSize) 
{ 
pQue->pData = (NODE **)malloc(sizeof(NODE *) * nSize); 
pQue->nSize = nSize; 
pQue->nFront = pQue->nRear = 0; 
pQue->bIsEmpty = TRUE; 
} /*入队列*/ 
BOOL InQueue(QUEUE *pQue, NODE *Data) 
{ 
if (pQue->bIsEmpty || pQue->nRear != pQue->nFront) /*判断队列是否满*/ 
{ 
pQue->bIsEmpty = FALSE; 
pQue->pData[pQue->nRear] = Data; 
pQue->nRear++; 
if (pQue->nRear == pQue->nSize) 
pQue->nRear = 0; 
return TRUE; 
} 
else 
return FALSE; 
} /*出队列。pDataBfr为容纳数据的变量的指针*/ 
BOOL OutQueue(QUEUE *pQue, NODE **pDataBfr) 
{ 
if (pQue->bIsEmpty) 
return FALSE; 
else 
{ 
*pDataBfr = pQue->pData[pQue->nFront]; 
pQue->nFront++; 
if (pQue->nFront == pQue->nSize) 
pQue->nFront = 0; 
if (pQue->nFront == pQue->nRear) 
pQue->bIsEmpty = TRUE; 
return TRUE; 
} 
} /*二叉树的层次遍历并判断是否为完全二叉树*/ 
BOOL LevelTraverse(NODE *pRoot) 
{ 
BOOL bResult = TRUE; 
BOOL bComfine = FALSE; 
NODE *pCurNode; 
QUEUE Que; if (pRoot == NULL) 
return TRUE; InitQueue(&Que,1024); /*这里不考虑队列溢出，在应用中应根据实际情况使用合适 
的队列*/ 
InQueue(&Que,pRoot); while (OutQueue(&Que,&pCurNode)) 
{ 
if (!pCurNode->pLeft && pCurNode->pRight) 
{ 
bResult = FALSE; 
break; 
} 
if (bComfine && (pCurNode->pLeft || pCurNode->pRight)) 
{ 
bResult = FALSE; 
break; 
} 
if (pCurNode->pLeft) 
InQueue(&Que,pCurNode->pLeft); 
if (pCurNode->pRight) 
InQueue(&Que,pCurNode->pRight); 
else 
bComfine = TRUE; 
} 
return bResult; 
} /*简单的测试环境*/ /* 从键盘缓冲区中读取一个不为空格且不为回车的字符 */ 
char GetNextChar(void) 
{ 
char ch; 
do 
{ 
ch = getchar(); 
} while (ch == ' ' || ch == '\n'); 
return ch; 
} /*利用前序遍历序列建立二叉树。扩充结点用‘*’代表。前序序列从键盘输入*/ 
void CreateTree(NODE *Root) 
{ 
Root->pLeft = Root->pRight = NULL; 
if (Root->Data != '*') /* 如果不为扩充结点, 要建立左结点和右结点 */ 
{ 
Root->pLeft = (NODE *)malloc(sizeof(NODE)); 
Root->pLeft->Data = GetNextChar(); 
CreateTree(Root->pLeft); 
Root->pRight = (NODE *)malloc(sizeof(NODE)); 
Root->pRight->Data = GetNextChar(); 
CreateTree(Root->pRight); 
} 
} /*除去'*'结点*/ 
void TrimTree(NODE *pRoot) 
{ 
if (pRoot->pLeft) 
if (pRoot->pLeft->Data == '*') 
{ 
free(pRoot->pLeft); 
pRoot->pLeft = NULL; 
} 
else 
TrimTree(pRoot->pLeft); 
if (pRoot->pRight) 
if (pRoot->pRight->Data == '*') 
{ 
free(pRoot->pRight); 
pRoot->pRight = NULL; 
} 
else 
TrimTree(pRoot->pRight); 
} void main() 
{ 
NODE Root; Root.Data = GetNextChar(); 
CreateTree(&Root); 
TrimTree(&Root); printf("%d\n",LevelTraverse(&Root)); 
}