#include<stdio.h>
#include<stdlib.h>
#define ElemType TreeNode
//定义树的结点
typedef struct node{ //树的结点
int data; //数据域
struct node* left; //左儿子
struct node* right; //右儿子
} Node,*TreeNode;
//利用树的结点类型指针指向根结点
typedef struct {
TreeNode root; //树根
}*TreeFirstNode,FirstNode;
//创建根
void Init( TreeFirstNode &tree, int value)//创建树
{
TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
node->data = value;
node->left = NULL;
node->right = NULL;
tree->root = node;//创建根结点
printf("初始化成功\n");
}
//插入结点(二叉排序树)
void Insert(TreeFirstNode &tree,int value){
TreeNode temp = tree->root;//工作从树根开始
TreeNode node=(TreeNode)malloc(sizeof(Node));//创建一个节点
node->data = value;
node->left = NULL;
node->right = NULL;
while (temp!= NULL)
{
if (value < temp->data) //小于就进左子树
{
if (temp->left == NULL)
{
temp->left = node;
printf("插入成功\n");
return;
}
else
{ //不空继续判断
temp = temp->left;
}
}
else{ //否则进右子树
if(temp->right == NULL)
{
temp->right = node;
printf("插入成功\n");
return;
}
else{ //不空继续判断
temp = temp->right;
}
}
}
}
//定义队列储存类型
typedef struct qnode{
TreeNode ptrl;
struct qnode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
//初始化队列
bool InitQueue(LinkQueue &q){ //传引用更加方便
q.front=q.rear = (LinkNode*)malloc(sizeof(struct node));
q.front->next=NULL; //是首结点置空
//printf("初始化成功!\n");
return true;
}
//判断队列是否为空
bool QueueEmpty(LinkQueue q){
if(q.front==q.rear)
return true;
return false;
}
//入队操作
bool EnterQueue(LinkQueue &q,TreeNode x){
LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
s->ptrl = x;
printf("%d入队成功\n",s->ptrl->data);
s->next = NULL;
q.rear->next = s; //这个时候front和rear还在一个地方 就有等效与q.front->next = s;
q.rear = s;
return true;
}
//出队操作
bool OutQueue(LinkQueue &q,TreeNode &temp){ //j用来保存出队数据 引用传递
if(q.front==q.rear)
return false;
LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
p = q.front->next;
temp = p->ptrl;
printf("%d出队成功\n",temp->data);
q.front->next = p->next;
if(q.rear==p)
q.front=q.rear;
free(p);
return true;
}
//层遍历二叉树
void LevelOrder(TreeNode TreeRoot,LinkQueue &q){
InitQueue(q);
TreeNode temp;
EnterQueue(q,TreeRoot);
while(!QueueEmpty(q)){
OutQueue(q,temp);
printf("%d\n",temp->data);
if(temp->left!=NULL){
EnterQueue(q,temp->left);
// printf("%d\n",q.front->next->ptrl->data);
}
if(temp->right!=NULL){
EnterQueue(q,temp->right);
}
}
}
int main(){
int value;
int N,i;
ElemType t;
ListStack S,L;
LinkQueue q;
printf("请输入根结点的值:\n");
scanf("%d",&value);
TreeFirstNode tree=(TreeFirstNode)malloc(sizeof(FirstNode));
Init(tree,value);
printf("请输入要插入树的数据个数(N):");
scanf("%d",&N);
for(i=1;i<N+1;i++){
printf("请输入第%d个数:",i);
scanf("%d",&value);
Insert(tree,value);
}
printf("层遍历二叉树:\n");
LevelOrder(tree->root,q);
return 0;
}
又是你呀