二叉树（基础）¶

typedef int BTNDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* Left;   // 指向当前节点左孩子
    struct BinTreeNode* Right; // 指向当前节点右孩子
    BTNDataType data; // 当前节点值域
}

// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* Parent; // 指向当前节点的双亲
    struct BinTreeNode* Left;   // 指向当前节点左孩子
    struct BinTreeNode* Right; // 指向当前节点右孩子
    BTNDataType data; // 当前节点值域
}；

//定义二叉树的数据类型
typedef int BTNDataType;

//定义二叉树结构
typedef struct BinaryTreeNode
{
    BTNDataType data;
    struct BinaryTreeNode* leftTree;
    struct BinaryTreeNode* rightTree;
}BTN;

//创建树节点
BTN* createNode(int x);
//创建树
BTN* createTree();
//前序遍历
void frontOrder(BTN* tree);
//中序遍历
void midOrder(BTN* tree);
//后序遍历
void postOrder(BTN* tree);
//二叉树节点的个数
int binaryTreeSize(BTN* tree);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTN* root);
// 求二叉树的高度
int BinaryTreeHeight(BTN* tree)
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTN* root, BTNDataType k);
// 二叉树查找值为x的节点
BTN* BinaryTreeFind(BTN* root, BTNDataType x);
// 二叉树的销毁
void BinaryTreeDestory(BTN* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTN* root);

//创建树节点
BTN* createNode(int x)
{
    BTN* node = (BTN*)malloc(sizeof(BTN));
    assert(node);

    node->data = x;
    node->leftTree = NULL;
    node->rightTree = NULL;

    return node;
}

//创建树
BTN* createTree()
{
    BTN* node1 = createNode(1);
    BTN* node2 = createNode(2);
    BTN* node3 = createNode(3);
    BTN* node4 = createNode(4);
    BTN* node5 = createNode(5);
    BTN* node6 = createNode(6);

    node1->leftTree = node2;
    node1->rightTree = node3;
    node2->leftTree = node4;
    node2->rightTree = node5;
    node5->leftTree = node6;

    return node1;
}

//层序遍历
void levelOrder(BTN* tree)
{
    //初始化队列
    Queue q;
    QueueInit(&q);

    //插入根节点
    QueuePush(&q, tree);

    //使用队列结构实现层序遍历
    while (!QueueEmpty(&q))
    {
        //记录当前的队列中的节点，该指针指向二叉树的节点，而不是队列的指针，即某一层的数据
        BTN* front = QueueFront(&q);
        //删除当前数据
        QueuePop(&q);
        if (front)
        {
            printf("%d ", front->data);
            //注意此处需要改变向队列中添加的数据，此时不能在使用根节点的指针
            //找到左子树节点并插入
            QueuePush(&q, front->leftTree);
            //找到右子树节点并插入
            QueuePush(&q, front->rightTree);
        }
    }

    //销毁队列
    QueueDestroy(&q);
}

//二叉树节点的个数
int binaryTreeSize(BTN* tree)
{
    //确定结束条件
    if (tree == NULL)
    {
        return 0;//节点为空时代表没有孩子节点
    }

    return binaryTreeSize(tree->leftTree) + binaryTreeSize(tree->rightTree) + 1;// +1代表左右孩子节点为空，但是存在自己即当前节点为叶子节点
}

// 二叉树叶子节点个数
int binaryTreeLeafSize(BTN* tree)
{
    //递归结束条件
    if (tree == NULL)
    {
        return 0;
    }

    //计算叶子节点个数
    if (tree->leftTree == NULL && tree->rightTree == NULL)
    {
        return 1;
    }

    return binaryTreeLeafSize(tree->leftTree) + binaryTreeLeafSize(tree->rightTree);
}

// 求二叉树的高度
int binaryTreeHeight(BTN* tree)
{
    //递归结束条件
    if (tree == NULL)
    {
        return 0;//注意此处不是返回1，因为下面的返回语句尽管为0时依旧会进行一次+1，若返回1则会多算1层
    }

    //获取左子树和右子树的高度并记录
    int leftTreeHeight = binaryTreeHeight(tree->leftTree);
    int rightTreeHeight = binaryTreeHeight(tree->rightTree);

    //找出较大的子树加1返回
    return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
}

// 二叉树第k层节点个数
int binaryTreeLevelKSize(BTN* tree, BTNDataType k)
{
    //确保k不为0
    assert(k > 0);

    //递归结束条件
    if (tree == NULL)
    {
        return 0;
    }

    //找到第k层开始计算
    if (k == 1)
    {
        return 1;
    }

    return binaryTreeLevelKSize(tree->leftTree, k - 1) + binaryTreeLevelKSize(tree->rightTree, k - 1);
}

// 二叉树查找值为x的节点
BTN* binaryTreeFind(BTN* tree, BTNDataType x)
{
    //递归结束条件
    if (tree == NULL)
    {
        return NULL;
    }

    //如果找到返回tree节点
    if (tree->data == x)
    {
        return tree;
    }

    //没找到时需要继续遍历左子树和右子树
    //如果在左子树找到，返回左子树的节点
    BTN* ret1 = binaryTreeFind(tree->leftTree, x);
    if (ret1)
    {
        return ret1;
    }

    BTN* ret2 = binaryTreeFind(tree->rightTree, x);
    if (ret2)
    {
        return ret2;
    }

    //注意还需要处理没有找到时返回的空结果
    return NULL;
}

// 二叉树的销毁
void BinaryTreeDestory(BTN* root)
{
    //使用后序遍历的思路进行销毁
    if (root == NULL)
    {
        return;
    }

    BinaryTreeDestroy(root->leftTree);
    BinaryTreeDestroy(root->rightTree);
    free(root);
}

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTN* root)
{
    Queue q = {0};
    QueueInit(&q);
    if (root == NULL)
    {
        return true;
    }

    //插入数据
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        //数据出队
        BTN* front = QueueFront(&q);
        QueuePop(&q);

        if (front == NULL)
        {
            break;
        }

        QueuePush(&q, front->leftTree);
        QueuePush(&q, front->rightTree);
    }

    //如果有空值时，则开始判断是否有非空值在空值之间
    while (!QueueEmpty(&q))
    {
        BTN* front = QueueFront(&q);
        QueuePop(&q);

        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }

    QueueDestroy(&q);
    //走到此位置代表为完全二叉树
    return true;
}

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef char BTNDataType;
typedef struct BinaryTreeNode
{
    BTNDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTN;

BTN* CreateSpace(BTNDataType x)
{
    BTN* root = (BTN*)malloc(sizeof(BTN));
    assert(root);
    root->data = x;
    root->left = root->right = NULL;

    return root;
}

//生成树
BTN* BinaryTreeCreate(BTNDataType* a, int* pi)
{
    if (a[*pi] == '#')
    {
        //注意更改pi的值，否则会导致pi始终指向第一次遇到空的位置
        (*pi)++;
        return NULL;
    }

    //开辟空间
    BTN* root = CreateSpace(a[(*pi)]);
    (*pi)++;

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

    return root;
}

//中序遍历
void InOrder(BTN* root)
{
    if (root == NULL)
    {
        return;
    }

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

int main() {
    //读取二叉树的数据
    char datac[100] = { 0 };
    scanf("%s", datac);
    //生成下标遍历数组
    int i = 0;
    BTN* root = BinaryTreeCreate(datac, &i);
    InOrder(root);
    return 0;
}