算法导论 二叉树 按层打印

前一篇博客记录了二叉树的中序遍历，打印出来是一个升序的排列。

本篇文章介绍按层遍历打印二叉树，关键是如何换层（何时打印回车符）。

使用sumup和sumdown记录当前行的个数和下一行的个数，

当当前行的元素个数0，打印回车，并且将下一行sumdown赋给sumup，sumdown归零重新计数，这样迭代下去。

如有疑问，欢迎留言。

----------------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<malloc.h>
#define N 100
#define K 100
typedef struct link S_L;
typedef struct queue SQ;//队列
struct link {
    int n;
    S_L* left;
    S_L* right;

};//申明二叉树元素的结构体，
struct queue{
S_L array[N];
S_L* head;
S_L* tail;
};//申明队列结构体
int enqueue(SQ* p, S_L n);//入队
S_L *dequeue(SQ* p);//出队
void tree(S_L* p, int n);//二叉树的根
int tree_link(S_L* p, int n);//二叉树递归
int printf_tree_layer(S_L*p);//按层遍历打印二叉树
void happen_rand(int* p, int n);//生成随机数
SQ Q = { {0},&Q.array[0],&Q.array[0] };//Q队列初始化
int n, k = 0, tmp[N+1] = { 0 };
int main()
{
    int array[N] = {0}, i;
    happen_rand(array,N);
    S_L P = {0};
    for (i = 0; i < N; i++) {//二叉树插入元素
        tree(&P, array[i]);
    }
    printf_tree_layer(&P);
    return 0;
}

void tree(S_L* p, int n) {
    if (p->n == 0) {
        p->n = n;
        p->left = NULL;
        p->right = NULL;
    }
    else
        tree_link(p, n);


}

int tree_link(S_L* p, int n) {

    if (n < p->n && p->left == NULL) {
        p->left = (S_L*)malloc(sizeof(S_L));
        p->left->n = n;
        p->left->left = NULL;
        p->left->right = NULL;
        return 0;
    }
    else if (n >= p->n && p->right == NULL) {
        p->right = (S_L*)malloc(sizeof(S_L));
        p->right->n = n;
        p->right->left = NULL;
        p->right->right = NULL;
        return 0;
    }
    else if (n < p->n)
        tree_link(p->left,n);
    else if (n >= p->n)
        tree_link(p->right, n);


}

void happen_rand(int* p, int n){
    int i;
    for (i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

int  enqueue(SQ* p, S_L n) {
    *p->tail = n;
    p->tail++;
    if (p->tail == &p->array[N]) {
        p->tail = &p->array[0];
    }//尾部循环
    if (p->head == p->tail)//判断溢出
        return -1;

}

S_L* dequeue(SQ* p) {
    if (p->head == &p->array[N]) {
        p->head = &p->array[0];
    }//尾部循环
    if (p->head == p->tail) //判断溢出
    {  S_L *p=NULL;
        return p;}
    return (p->head++);
}
int sumup=1;//当前行的元素个数
int sumdown=0;//下一行的元素个数
int printf_tree_layer(S_L*p){
    if(0==sumup){//这里是关键，当前元素是0的时候换行，
        if(sumdown==0) return;//判断下一行是否为0
    printf("\n");
        sumup=sumdown;
        sumdown=0;
    }
 printf("%d ",p->n);
    sumup--;//每次打印后当前元素个数减一
 if(NULL!=p->left){ enqueue(&Q,*p->left);sumdown++;}//每次生成子元素后下一行元素个数加一
 if(NULL!=p->right){enqueue(&Q,*p->right);sumdown++;}//每次生成子元素后下一行元素个数加一
    printf_tree_layer(dequeue(&Q));
 
 
}