使用C语言的二叉树层序遍历的算法优化(通过链表实现伪队列)

[XA2005]

#include "stdio.h"
//定义二叉树结构体
typedef struct TreeNode
    {
        int data;
        TreeNode* lchild;
        TreeNode* rchild;
    }TreeNode;
//定义链式层序遍历的结构体（伪队列）
typedef struct Treeptr
        {
            TreeNode* ptr_tree;
            Treeptr* ptr_tree_next;
        }Treeptr;
//定义遍历函数
Treeptr *levelOrder(TreeNode *root)
    {
    //申请节点并赋出值
    Treeptr* temp = (Treeptr*)malloc(sizeof(Treeptr));
    *temp = {root,NULL};
    //定义头部指针和指向尾部指针域的指针
    Treeptr* head = temp;
    Treeptr** end = &(temp->ptr_tree_next);
    //进入循环
    while (temp != NULL)
    {
        //如果左子节点不为空，就将该节点加入到链表后端
        if (temp->ptr_tree->lchild != NULL)
        {
            Treeptr* next = (Treeptr*)malloc(sizeof(Treeptr));
            *next = { temp->ptr_tree->lchild,NULL };
            *end = next;
            end = &((*end)->ptr_tree_next);
        }
        //如果左子节点不为空，就将该节点加入到链表后端
        if (temp->ptr_tree->rchild != NULL)
        {
           Treeptr* next = (Treeptr*)malloc(sizeof(Treeptr));
           *next = { temp->ptr_tree->rchild,NULL };
           *end = next;
           end = &((*end)->ptr_tree_next);
        }
        //链表节点后移，直到没有节点可添加子节点时循环终止
        temp = temp->ptr_tree_next;
    }
    return head;
}
//遍历方法
while (head != NULL)
{
    printf("%d",head->ptr_tree->data);
    head = head->ptr_tree_next;
    if (head != NULL) printf("->");
}

[krahets]

Hi，请描述做了哪些优化，以及对应原因，谢谢

[XA2005]

Hi，请描述做了哪些优化，以及对应原因，谢谢

/* 辅助队列 */
queue = (TreeNode **)malloc(sizeof(TreeNode *) * MAX_SIZE);

// 更新数组长度的值 size = index; arr = realloc(arr, sizeof(int) (*size)); 总的来说两种算法都差不多，但是原来的代码有两处个人感觉不宜的地方。一是辅助队列的MAX_SIZE的值的问题，如果这个值太小，容量会不够，过大又会浪费空间。二是在C语言中realloc这个函数确实可能会存在着分配内存错误的情况。个人认为使用链表构建一个伪队列的话可以不错的解决前面两个问题。 当然，我的代码也有着 1.在添加子节点到链表的过程中，每次都需要动态分配内存，这个操作可能会导致时间上的消耗。 2.链表操作相对于数组来说，在访问节点时没有数组直接索引那么高效。 3.需要手动管理内存，在添加节点时分配内存。在遍历完成后释放内存，既增加了内存泄漏的风险又需要额外的操 作。当然，我们同时也获得了一个遍历树的链表，可以在后续对树进行操作时使用它 最后本人是学生，提供的建议还是只能说仅供参考。

[krahets]

一是辅助队列的MAX_SIZE的值的问题，如果这个值太小，容量会不够，过大又会浪费空间

是的。不过本节的内容重点是树的遍历，因此队列的实现并不需要很完善。书中 C 代码大量使用了 MAX_SIZE 来简化代码，旨在让读者集中在核心的算法知识上。这种不太规范的简化也是出于无奈，我们必须要在简单性和规范性中间找到一个平衡，同时需要避免核心知识被淹没在冗长实现之中。

使用链表实现队列在“栈与队列”中有介绍。