[C++知识库]二叉树的层次遍历

实现方式：主要采用队列实现（利用其FIFO的特性）；因此需要设计头指针、尾指针?

#include <stdio.h>
#include <stdlib.h>

typedef struct treenode {
    char date;
    struct treenode* lchild;
    struct treenode* rchild;
}Tree;

typedef struct node {
    Tree* node;
    struct node* next;
}stack;


typedef struct node1 {
    stack* pre;
    stack* rear;
}Linkstack;

int createtree(Tree** L)
{
    char a;
    scanf("%c", &a);
    if (a == '#')
    {
        (*L) = NULL;
    }
    else
    {
        (*L) = (Tree*)malloc(sizeof(Tree));
        (*L)->date = a;
        createtree(&(*L)->lchild);
        createtree(&(*L)->rchild);
    }
    return 1;
}

int initstack(Linkstack* L)
{
    L->pre = L->rear =(stack*)malloc(sizeof(stack));//设置头节点
    (*L).pre->node=NULL;
    (*L).pre->next = (*L).rear->next =NULL;
    return 1;
}

int empty(Linkstack* L) {
    if ((L->pre)==(L->rear))
    {
        return 1;
    }
    return 0;
}

int push_stack(Linkstack** L, Tree* elem)
{
    stack* p = (stack*)malloc(sizeof(stack));
    p->node = elem;
    p->next = NULL;
    (*L)->rear->next = p;
    (*L)->rear = p;
    return 1;
}

Tree* pop_stack(Linkstack** L)
{
    if (empty(L))
    {
        return NULL;
    }
    stack* q = (*L)->pre->next;
    Tree* k = q->node;
    (*L)->pre->next = q->next;
    if((*L)->rear==q)//若删除的是最后一个元素，就需要姜尾指针指向头节点
        (*L)->rear= (*L)->pre;
    free(q);
    q = NULL;
    return  k;
}

int preorder(Tree* L, Linkstack* p)
{
    push_stack(&p, L);
    while (!empty(p))
    {
        Tree* q = pop_stack(&p);
        printf("%c ", q->date);
        if (q->lchild)
        {
            push_stack(&p, q->lchild);
        }
        if (q->rchild)
        {
            push_stack(&p, q->rchild);
        }
    }
    return 1;
}

int main()
{
    Tree* L = NULL;
    Linkstack p;
    initstack(&p);
    createtree(&L);
    preorder(L,&p);
    return 0;
}