求助。。层序遍历二叉树。。。
#include <stdlib.h>#include <stdio.h>
#include<string.h>
#define size 100
#define N 15
typedef int DataType; //二叉树的节点结构
typedef struct BiTNode
{
DataType data;
struct BiTNode *parent;
struct BiTNode *lChild;
struct BiTNode *rChild;
}BiTNode, *BiTree;
//返回二叉树的最小节点,空树返回NULL
BiTNode *minImum(BiTree *biTree)
{
BiTNode *curNode = *biTree;
while (curNode != NULL && curNode->lChild != NULL)
{
curNode = curNode->lChild;
}
return curNode;
}
//返回二叉树的最大节点,空树返回NULL
BiTNode *maxImum(BiTree *biTree)
{
BiTNode *curNode = *biTree;
while (curNode != NULL && curNode->rChild != NULL)
{
curNode = curNode->rChild;
}
return curNode;
}
//插入节点
void insertNode(BiTree *biTree, DataType data)
{
//创建节点
BiTNode *targetNode;
targetNode = (BiTNode *)malloc(sizeof(BiTNode));
//没有足够内存
if (targetNode == NULL) return;
if (data == 0) return;
targetNode->data = data;
targetNode->parent = NULL;
targetNode->lChild = NULL;
targetNode->rChild = NULL;
BiTNode *p, *y;
p = *biTree;
y = NULL;
while (p != NULL )
{
y = p;
if (targetNode->data < p->data)
{
p = p->lChild;
}
else
{
p = p->rChild;
}
}
//空树,将新节点置为树根
if (y == NULL)
{
*biTree = targetNode;
}
else
{
if (targetNode->data < y->data)
{
y->lChild = targetNode;
}
else
{
y->rChild = targetNode;
}
}
targetNode->parent = y;
}
//打印一个结点
void printNode(BiTNode *node)
{
printf("%d ", node->data);
}
//队列节点结构
typedef struct queue
{
BiTree *base;
int front;
int rear;
}queue;
//初始化队列
void QueueStart(queue &Q)
{
Q.base=(BiTree*)malloc(size*sizeof(BiTree));
if (!Q.base) return;
Q.front=0;
Q.rear=0;
}
//入队
void QueueInt(queue &Q,BiTree &p)
{
if ((Q.rear+1)%size==Q.front) return;
Q.base[Q.rear]=p;
Q.rear=(Q.rear+1)%size;
}
//出队
void QueueOut(queue &Q,BiTree &p)
{
printf("%d ",p->data);
if (Q.rear==Q.front) return;
p=Q.base[Q.front];
Q.front=(Q.front+1)%size;
}
//层序遍历
void levelTraversal(BiTree &T)
{
queue S;
BiTree p;
p=T;
QueueStart(S);
if (p) QueueInt(S,p);
while (S.rear!=S.front)
{
QueueOut(S,p);
if (p->lChild)
QueueInt(S,p->lChild);
if (p->rChild)
QueueInt(S,p->rChild);
}
}
int main()
{
BiTNode *root;
DataType k;
int i;
root = NULL;
int data[N] = {5,3,1,0,0,4,0,0,7,6,0,0,8,0,0};
for (i = 0; i < N; i++)
{
insertNode(&root, data[i]);
}
printf("层序遍历:");
levelTraversal(root);
printf("\n");
printf("最小值:");
printNode(minImum(&root));
printf("\n最大值:");
printNode(maxImum(&root));
printf("\n插入节点值:%d",k=9);
insertNode(&root,k);
printf("插入后层序遍历:");
levelTraversal(root);
printf("\n");
}