层次遍历引入队列解决，队列

绝地灬酷狼 2022-06-08 11:08 151阅读 0赞

1.  单链表的快速排序
2.  线索化二叉树结构体：

typedef char ElemType;
    typedef enum{LINK = 0,THREAD = 1}PointTag;
    typedef struct BiThrNode
    {
        BiThrNode *leftchild;
        BiThrNode *rightchild;
        PointTag Ltag,Rtag;  //枚举
        ElemType data;
    }BiThrNode *  ThreadBinaryTree;
    
    //线索化输出

1.  层次遍历引入队列解决：

//层次遍历二叉树   用队列解决
    void LevelOrder(BtNode *ptr)
    {
        if (ptr == NULL)
        {
            return;
        }
        Queue q;
        init_queue(&q);
        push_queue(&q,ptr);  //将ptr的值赋予队列
    
        while(!empty_queue(&q))
        {
            ptr = queue_front(&q);  //将队列头的值给ptr
            pop_queue(&q);  //出队列
            printf("%c ",ptr->data);  //打印ptr的值
    
            if (ptr->leftchild != NULL)
            {
                push_queue(&q,ptr->leftchild);  //把左子树的值给队列
            }
            if (ptr->rightchild != NULL)
            {
                push_queue(&q,ptr->rightchild);  //把右子树的值给队列
            }
        }
        destroy_queue(&q);  //摧毁二叉树
    }
    
    //打印二叉树的第k层元素   不用队列解决
    void printfK(BtNode *ptr,int k)
    {
        if (ptr == NULL || k == 0)
        {
            printf() ptr->data;
            return;
        }
        if (ptr->leftchild != NULL)
        {
            printfK(ptr->leftchild,k-1);  //递归解决
        }
        if (ptr->rightchild != NULL)
        {
            printfK(ptr->rightchild,k-1);  //右子树递归
        }
    }
    
    void print_KLevelData(BtNode *ptr,int k)   //打印第k层元素
    {
        if (ptr == NULL || k<0)
        {
            return;
        }
        printfK(ptr,k);   //函数
    }

1.  队列的结构体：

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <string.h>
    #include "queue.h" 
    #define MAXSIZE 10
    
    //第一种结构体     //放入头文件queue.h中
    typedef int ElemType;
    typedef struct 
    {
        ElemType data[MAXSIZE];  //数组类型
        int front;   //头
        int tail     //尾
    }Queue;
    
    //第二种结构体
    typedef struct
    {
        ElemType *data;   //指针类型
        int front;  //头
        int tail;   //尾
        int maxsize;   //最大空间
        int cuisize;   //当前位置
    }Queue;
    
    //初始化一个队列
    void init_queue(Queue *p)
    {
        assert(p != 0);
        p->front = 0;
        p->tail = 0;
        p->maxsize = 0;
        p->cuisize = 0;
        p->data = (ElemType *)malloc(sizeof(ElemType)*p->maxsize);
    //没有解决内存不足的问题
    }
    //摧毁队列
    void destroy_queue(Queue *p)
    {
        assert(p != NULL);
        free(p->data);
        p->data = NULL;
        p->front = 0;
        p->tail = 0;
        p->maxsize = 0;
        p->cuisize = 0;
    }
    //入队列
    bool push_queue(Queue *p,ElemType value)
    {
        assert(p != NULL);
        if (full_queue(p))  //满队列
        {
            return false;
        }
        p->data[p->tail] = value;  //从尾部入队列
        p->tail++;
        p->cursize++;
        return true;
    }
    //出队列
    //空队列
    bool empty_queue(Queue *p)
    {
        assert(p != NULL);
        return(size_queue(p) == 0);
    }
    //满队列
    bool full_queue(Queue *p)
    {
        assert(p != NULL);
        return(size_queue(p) == p->maxsize);
    }
    //返回队列头
    ElemType queue_front(Queue *p)
    {
        assert(p != NULL);
        return p->front;
    }
    //返回队列尾
    ElemType queue_tail(Queue *p)
    {
        assert(p != NULL);
        int cur = p
        return p->tail;
    }
    //队列当前大小
    int size_queue(Queue *p,ElemType value)
    {
        assert(p != NULL);
        return p->cuisize;
    }