实现一个链队列#

typedef struct QNode
{
    TreeNode *e;
    struct QNode *next;
} QNode;
// 这个为了实现链队列存取Treenode结点

typedef struct Quece
{
    QNode *f, *r;
    int Qsize;
} Quece;
// 定义队列本身的结构体. 修改队列只能通过f, r指针进行.

// Q构造函数
bool InitQ(Quece **q, int size)
{
    *q = (Quece *)malloc(sizeof(Quece));
    // 初始化第一步: 建立队列.
    (*q)->f = (*q)->r = (QNode *)malloc(sizeof(QNode));
    (*q)->f->next = NULL;
    // 初始化第二步: 建立带头单链表.
    return 1;
}

// Q判空函数
bool isE(Quece *q)
{
    return q->f == q->r;
}

// Q入队函数
bool EnQ(Quece *q, TreeNode *x)
{
    QNode *new_qnode = (QNode *)malloc(sizeof(QNode));
    new_qnode->e = x;
    new_qnode->next = NULL;
    // 1. 创建--初始化一个新队列结点, 准备入队列.
    q->r->next = new_qnode;
    // 2. 将新结点上传到链上
    q->r = new_qnode;
    // 3. 将队列的尾指针指向新的链尾
    printf("[+]EnQ: %d\n", x->id);
    // 打印每个入队节点的ID
    return 1;
}

// Q出队函数
TreeNode *DeQ(Quece *q)
{
    TreeNode *rec;
    if (q->f == q->r)
    {
        return NULL;
    }
    // 特殊情况1: 队元素为0个
    // 判空(当原本的队列事实上只有0个元素, r指向f)
    QNode *p = q->f->next;
    rec = p->e;
    // 拿出队头数据(f指向带头单链表的头结点)
    q->f->next = p->next;
    // 头指针移动到新的队首
    if (q->r == p)
        q->r = q->f;
    free(p);
    // 在链上删除旧的队头结点(出队)

    printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
    return rec;
}

定义访问行为#

// 1. 层序遍历(广度优先遍历)
bool visit_1(TreeNode *any_node)
{
    printf("%d ved\n", any_node->id);
}

层序遍历算法#

大体上就是从树根结点开始不停进行入队—出队+访问操作.

• 入队操作规则: 根结点以外的任何结点的入队, 都是它的双亲结点的出队所导致的.
• 出队操作规则: 出队之后先访问它. 再把按照左孩子—右孩子的顺序把它的两个孩子放进队列.

流程如下:

1. 初始化链式队列, 初始化树一颗.
2. 根结点入队.
3. 根结点点出队&&访问根结点.
4. 根结点的孩子按照规则入队&&出队.
5. 重复4直到队空.

// 1.1. 王道-层序遍历
void levelOrderTR(TreeNode *root)
{
    Quece *q;
    TreeNode *p;
    InitQ(&q, 20);
    EnQ(q, root);
    // 1. 根节点放进队列
    while (!isE(q))
    {
        p = DeQ(q);
        visit_1(p);
        if (p->l)    EnQ(q, p->l);
        if (p->r)    EnQ(q, p->r);
    }
}