二叉树的层次遍历（C语言实现）

深藏阁楼爱情的钟 2022-02-02 06:27 213阅读 0赞

### 非递归实现二叉树的层次遍历： ###

想了大半个小时终于写出来了，通过自己思考出来的还是有很大成就感。学数据结构就是通过自己思考和参考而学得更深。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70][]

思路：层次遍历就是一层一层遍历，这棵二叉树的层次遍历序列为5 2 11 3 6 4 8，先上到下，先左到右。实现层次遍历用队列比较方便，因为是先进先出（FIFO）。首先把5入队，然后再输出队首元素，并且把队首元素的左结点和右结点入队（如果有的话），以此类推，输出的序列就是层次遍历啦～～～

/* 完整代码 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MaxSize 100
    
    struct tree {
        int data;
        struct tree* left;
        struct tree* right;
    };
    
    typedef struct queue{
        struct tree* numQ[MaxSize];
        int front;
        int rear;
    }Queue;
    
    Queue Q;
    
    void initilize() { //初始化队列
        Q.front = 0;
        Q.rear = 0;
    }
    
    void Push(struct tree* root) { //入队
        Q.numQ[++Q.rear] = root;
    }
    
    struct tree* Pop() { //出队
        return Q.numQ[++Q.front];
    }
    
    int empty() { //判断对列是否为空
        return Q.rear == Q.front;
    }
    
    struct tree* creatTree (struct tree* root) {
        int value;
        scanf("%d", &value);
        if (value == -1)
            return NULL;
        root = (struct tree*)malloc(sizeof(struct tree));
        root->data = value;
        printf("请输入%d的左子树：", root->data);
        root->left = creatTree(root->left);
        printf("请输入%d的右子树：", root->data);
        root->right = creatTree(root->right);
        return root;
    }
    
    void LevelOrderTraversal (struct tree* root) { //二叉树的层次遍历
        struct tree* temp;
        Push(root);
        while (!empty()) {
            temp = Pop();
            printf("%d ", temp->data);  //输出队首结点
            if (temp->left)     //把Pop掉的结点的左子结点加入队列
                Push(temp->left);
            if (temp->right)    把Pop掉的结点的右子结点加入队列
                Push(temp->right);
        }
    }
    
    int main() {
        printf("请输入头节点：");
        struct tree* root = creatTree(root);
        
        initilize();  //初始化队列
        
        LevelOrderTraversal(root);
        putchar('\n');
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70]: /images/20220202/1d8517346c024347beb99ec9d97b1e0a.png