###### 帅过吴彦祖

2017-07-15 10:09 阅读 892

3

# include

//二叉树结点类型定义
typedef struct btNode
{
char data;
struct btNode * lchild;
struct btNode * rchild;
}BiTree,*Tree;

//队列结点类型定义
typedef struct Node
{
Tree data;
struct Node * next;
}Node,*pNode;

typedef struct Queue
{
pNode front;
pNode rear;
}QUEUE;
/*==========队列函数定义==========*/
void InitQueue(QUEUE &);
void EnQueue(QUEUE &, Tree);
void DeQueue(QUEUE &);
bool EmptyQueue(QUEUE);
/*==========队列函数定义==========*/

/*==========二叉树函数定义==========*/
void CreateTree(Tree &);
void Visit(Tree);
int Height(Tree);
void LevelOrder(Tree);
/*==========二叉树函数定义==========*/

int main(void)
{
Tree T;
printf("\n按先序序列输入结点序列，'#'代表空:");
CreateTree(T);

``````printf("二叉树的高度为%d\n",Height(T));
printf("二叉树的层次遍历结果为:");
LevelOrder(T);
printf("\n");

return 0;
``````

}

void init(QUEUE & Q)
{
Q.front = (pNode)malloc(sizeof(Node));
if(NULL == Q.front)
{
printf("动态分配内存失败\n");
exit(-1);
}
Q.rear = Q.front;
}

//入队
void EnQueue(QUEUE & Q, Tree e)
{
pNode pNew = (pNode)malloc(sizeof(Node));
if(NULL == pNew)
{
printf("动态分配内存失败\n");
exit(-1);
}
pNew->data = e;
pNew->next = NULL;
Q.rear->next = pNew;
Q.rear = pNew;
}

//出队
void DeQueue(QUEUE & Q)
{
if(Q.front == Q.rear)
return;
else
{
pNode p = Q.front->next;
Q.front = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
}
}

//判断队列是否为空
bool EmptyQueue(QUEUE Q)
{
if(Q.rear == Q.front)
return true;
else
return false;
}

//获得对首元素
void GetHead(QUEUE Q, Tree & e)
{
if(EmptyQueue(Q))
{
return;
}
else
{
e = Q.front->next->data;
}
}

//创建二叉树
void CreateTree(Tree &T)
{
char ch;
scanf("%c", &ch);
if('#' == ch)
T = NULL;
else
{
T = (Tree)malloc(sizeof(BiTree));
if(NULL == T)
{
printf("动态分配内存失败");
exit(-1);
}
else
{
T->data = ch;
CreateTree(T->lchild);
CreateTree(T->rchild);
}
}
}

//访问节点
void Visit(Tree T)
{
printf("%c", T->data);
}

//求树的高度
int Height(Tree T)
{
int ld = 0;
int rd = 0;
if(NULL == T)
return 0;
else
{
ld = Height(T->lchild);
rd = Height(T->rchild);
return 1 + (ld>rd?ld:rd);
}
}

//层次遍历
void LevelOrder(Tree T)
{
QUEUE Q;
init(Q);
Tree p;

``````if(NULL != T)
{
EnQueue(Q, T);
while(!EmptyQueue(Q))
{
DeQueue(Q);
Visit(p);
if(NULL != p->lchild)
EnQueue(Q, p->lchild);
if(NULL != p->rchild)
EnQueue(Q, p->rchild);
}
}
``````

}

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享