/*===============================================
* 文件名称：seqtree.c
* 创 建 者：
* 创建日期：2022年12月07日
* 描 述：
================================================*/
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
//创建完全二叉树
TREE *create_tree(int num, int tail_num){//num：节点编号 tail_num：最后节点标号
//创建根节点
TREE *root = (TREE *)malloc(sizeof(TREE));
//判断是否创建成功
if(NULL == root)
return NULL;
//初始化
root->data = num;
//判断是否有左节点
if(2 * num <= tail_num)
root-> left = create_tree(2 * num, tail_num);
else
root-> left = NULL;
//判断是否有右节点
if(2 * num + 1 <= tail_num)
root->right = create_tree(2 * num + 1, tail_num);
else
root->right = NULL;
return root;
}
//先序打印
void print_tree_dlr(TREE *root){
//判断树是否存在
if(root == NULL)
return ;
//打印data
printf("%d ", root->data);
//打印左子树
print_tree_dlr(root->left);
//打印右子树
print_tree_dlr(root->right);
}
//中序打印
void print_tree_ldr(TREE *root){
//判断树是否存在
if(root == NULL)
return ;
//打印左子树
print_tree_ldr(root->left);
//打印data
printf("%d ", root->data);
//打印右子树
print_tree_ldr(root->right);
}
//后序打印
void print_tree_lrd(TREE *root){
//判断树是否存在
if(root == NULL)
return ;
//打印左子树
print_tree_lrd(root->left);
//打印右子树
print_tree_lrd(root->right);
//打印data
printf("%d ", root->data);
}
//创建头节点
LNODE *create_lqueue(void){
//为头节点申请空间
NODE *head = (NODE *)malloc(sizeof(NODE));
//判断是否申请成功
if(NULL == head){
return NULL;
printf("error");
}
//为队头队尾申请空间
LNODE *lq = (LNODE *)malloc(sizeof(LNODE));
//判断是否申请成功
if(NULL == lq)
return NULL;
lq->front = head;
lq->rear = head;
return lq;
}
//判队列是否是空
int lqueue_is_mepty(LNODE *lq){
//判断列表是否存在
if(NULL == lq)
return -1;
//判断是否是空
return ((lq->front == lq->rear)?1:0);
}
//入队
int insert_lqueue(LNODE *lq, TREE *data){
//判断列表是否存在
if(NULL == lq)
return -1;
//入队
lq->rear->next = (NODE *)malloc(sizeof(NODE));
//判断新成员是否申请成功
if(NULL == lq->rear->next)
return -1;
//队尾后移
lq->rear = lq->rear->next;
//赋值
lq->rear->data = data;
lq->rear->next = NULL;
return 0;
}
//出队
TREE *out_lqueue(LNODE *lq){
//判断队列是否是空
if(lqueue_is_mepty(lq))
return NULL;
//出队
//将front后一位的地址保存下来
NODE *p = lq->front->next;
TREE *data = p->data;
//将front的next指向在下一位
lq->front->next = p->next;
free(p);
p = NULL;
//判断队列是否为空
if(NULL == lq->front->next)
lq->rear = lq->front;
return data;
}
//层次打印
void print_tree(TREE *root){
//创建队列
LNODE *p = create_lqueue();
//判断队列是否申请成功
if(NULL == p)
return ;
//根节点入队
insert_lqueue(p, root);
while(!lqueue_is_mepty(p)){
//出队
root = out_lqueue(p);
printf("%d ",root->data);
//左节点入队
if(root->left != NULL){
insert_lqueue(p, root->left);
}
//右节点入队
if(root->right != NULL)
insert_lqueue(p, root->right);
}
}
