层序遍历

层序遍历指的是对二叉树进行一层一层的遍历，每一层分别遍历，这里借助队列进行遍历，基本思路把根放到队列中，当某一个根要出队列时，就令该根的左子树和右子树进队列，这样就能实现一层一层遍历，画法如下：

代码实现相较于前面来说简单一些，但需要引入队列的，关于队列的介绍：

数据结构---手撕队列栈并相互实现

下面展示要使用的队列的相关函数实现

// queue.h
typedef struct BinaryTreeNode* QDataType;

typedef struct QNode
{
   
   
    QDataType data;
    struct QNode* next;
}QNode;

typedef struct Queue
{
   
   
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;

// queue.c
void QueueInit(Queue* pq)
{
   
   
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
   
   
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
    free(pq);
}

QNode* BuyQnode(QDataType x)
{
   
   
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
   
   
        perror("malloc fail");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void QueuePush(Queue* pq, QDataType x)
{
   
   
    assert(pq);
    QNode* newnode = BuyQnode(x);
    if (pq->ptail == NULL)
    {
   
   
        assert(pq->phead == NULL);
        pq->phead = pq->ptail = newnode;
    }
    else
    {
   
   
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}

bool QueueEmpty(Queue* pq)
{
   
   
    if (pq->size == 0)
    {
   
   
        return true;
    }
    return false;
}

void QueuePop(Queue* pq)
{
   
   
    assert(pq);
    assert(!QueueEmpty(pq));

    if (pq->phead->next == NULL)
    {
   
   
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else
    {
   
   
        QNode* newhead = pq->phead->next;
        free(pq->phead);
        pq->phead = newhead;
    }

    pq->size--;
}

QDataType QueueFront(Queue* pq)
{
   
   
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
   
   
    assert(pq);
    return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
   
   
    assert(pq);
    return pq->size;
}

那么借助队列我们来实现刚才的层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
   
   
    Queue q;
    QueueInit(&q);
    if (root)
    {
   
   
        QueuePush(&q, root);
    }
    while (!QueueEmpty(&q))
    {
   
   
        BTNode* front = QueueFront(&q);
        printf("%c ", front->data);
        QueuePop(&q);
        if (front->left)
            QueuePush(&q, front->left);
        if(front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    //BinaryTreeDestory(&q);
}

二叉树的销毁

在知道了遍历的多种途径后，二叉树的销毁就很简单了，在确定代码如何实现前，先思考问题：应该选用哪种遍历来进行二叉树的销毁？

结果是很明显的，选用后序遍历是最方便的，原因在于销毁是需要进行节点的释放的，如果使用前序或者中序遍历，那么在遍历的过程中根节点会被先销毁，那么找左子树或者右子树就带来了不便(可以定义一个变量保存位置)，因此最好用后序遍历，把子树都销毁了最后销毁根

void BinaryTreeDestory(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        return;
    }

    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}

二叉树节点个数

二叉树节点个数也是转换成子树来解决，如果为NULL就返回0，其他情况返回左右相加再加上节点本身

int BinaryTreeSize(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        return 0;
    }

    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

二叉树叶子节点的个数

叶子节点个数求解和上述方法相似，也是找最小的子树，但不同的地方是，叶子节点找到的条件是叶子作为根，它的左右子树都为空，符合这样的就是叶子节点，那么根据这个想法求得代码不难得到：

int BinaryTreeLeafSize(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        return 0;
    }

    if (root->left == NULL && root->right == NULL)
    {
   
   
        return 1;
    }

    int leftleave = BinaryTreeSize(root->left);
    int rightleave = BinaryTreeSize(root->right);

    return leftleave + rightleave;
}