二叉树的创建、遍历及其它基本操作的实现

问题描述

1. 以二叉链表作存储结构创建如下二叉树：

1. 输出二叉树的中序遍历序列和后序遍历序列，以验证所建二叉树的正确性；
2. 按二叉树的层次输出所建二叉树各层的结点，要求同层的结点自左向右排列。（提示：用到两个队列P、Q。其中P存放当前层上的结点，Q存放下一层的结点。）

题目解析

本实验就是对二叉树的简单操作，熟悉二叉树即可

二叉树介绍链接：

[数据结构---手撕图解二叉树]
==注意：==

创建二叉树的方法有很多种，标准的创建二叉树的方法是用递归调用进行创建，基本原理可以在上文链接寻找

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

typedef struct BinaryTreeNode* QDataType;

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

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

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

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

void QueueDestroy(Queue* pq)
{
    assert(pq);

    QNode* cur = pq->phead;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }

    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

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;
}

BTNode* BuyNode(BTDataType a)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = a;
    newnode->left = NULL;
    newnode->left = NULL;
    return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* root = BuyNode(a[*pi]);
    (*pi)++;

    root->left = BinaryTreeCreate(a, pi);
    root->right = BinaryTreeCreate(a, pi);

    return root;
}

void BinaryTreeDestory(BTNode* root)
{

    if (root == NULL)
    {
        return;
    }

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

void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        //printf("N ");
        return;
    }

    printf("%c ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}

void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
    {
        //printf("N ");
        return;
    }

    BinaryTreeInOrder(root->left);
    printf("%c ", root->data);
    BinaryTreeInOrder(root->right);
}

void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
    {
        //printf("N ");
        return;
    }

    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->data);
}

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");
    QueueDestroy(&q);
}

int main()
{
    char ch[] = "AB##CDF###E##";
    int pos = 0;
    BTNode* tree = BinaryTreeCreate(ch, &pos);
    printf("前序遍历:");
    BinaryTreePrevOrder(tree);
    printf("\n");
    printf("中序遍历:");
    BinaryTreeInOrder(tree);
    printf("\n");
    printf("后序遍历:");
    BinaryTreePostOrder(tree);
    printf("\n");
    printf("层序遍历:");
    BinaryTreeLevelOrder(tree);
    printf("\n");
    BinaryTreeDestory(tree);
    tree = NULL;
    return 0;
}