C语言实现基础数据结构——二叉树（二叉树基础部分）

二叉树的概念和结构

二叉树的性质

二叉树的性质基础练习

二叉树的存储结构

二叉链式二叉树的基本功能实现

二叉链式二叉树的结构定义

主要实现功能

创建树节点

创建树

前序遍历、中序遍历、后序遍历以及层序遍历

基础选择练习

二叉树的节点个数

二叉树叶子节点的个数

求二叉树的高度

二叉树第k层节点个数

二叉树查找值为x的节点

二叉树的销毁

判断是否是完全二叉树

项目文件

二叉树的概念和结构

一棵二叉树是结点的一个有限集合，该集合为空或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树的特点：

二叉树不存在度大于2的结点（但是可以存在空节点或者1个节点）
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

特殊的二叉树：

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是个，则它就是满二叉树
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树，并且完全二叉树节点个数范围为[，]（最少时即为K层只有一个节点，最多时为完全二叉树）

📌

完全二叉树最后一层可以不满，但是必须从左到右连续

二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{i-1}$ 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 $2^h-1$ .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 $n_0$ , 度为2的分支结点个数为 $n_2$ ,则有 $n_0=n_2+1$

一个树是由度为0的节点一次一次构建出来的，当出现度为1的节点时，肯定伴随着一个度为0的节点减少，但是同时也会增加一个度为0的节点，故此时度为0的节点还是1个，而度为1的节点从原来的0个变为现在的1个，同理可得度为2的节点，因为一个节点想从度为0变为度为2，则需要先变为度为1的节点，再成为度为2的节点，当一个节点度为2时，那么伴随着的就是两个度为0的节点，即度为0的节点从1变成了2，度为2的节点从原来的0变为了现在1，故有等式 $n_0=n_2+1$

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= $log_2{(n+1)}$ . (ps：是log以2

为底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

二叉树的性质基础练习

1.一棵完全二叉树的节点数为531个，那么这棵树的高度为

A 11

B 10

C 8

D 12

答案：B

解析：

因为完全二叉树最少的节点为 $2^h$ 个，最多为 $2^{(h-1)}$ 个，故当节点数为531个时，最少满足层数为9层（至少有512个节点），最多满足层数为十层（至多为1024个节点），故当前树的高度为10

2.一个具有767个节点的完全二叉树，其叶子节点个数为

A 383

B 384

C 385

D 386

答案：B

解析：

假设度为0的节点有n个，度为1的节点有k个，度为2的节点有i个，那么有等式n+k+i = 767，因为n = i +1，故原式化为n-1+k+n = 767，即2n+k=768，因为节点个数肯定为整数，故当节点总数为奇数时，肯定不存在度为1的节点，反之最多存在一个度为1的节点，故得度为0的节点的个数n = 384

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为

A n

B n+1

C n-1

D n/2

答案：A

解析：

本题与上题思路类似，假设度为0的节点m个，度为1的节点有k个，度为2的节点有i个，故有等式m+k+i = 2n，化简得2m-1+k=2n，因为节点个数为偶数个，则至多存在一个度为1的节点，则2m-1+1=2n，即m = n，故叶子节点个数为n

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链

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 frontOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    printf("%d ", tree->data);
    frontOrder(tree->leftTree);
    frontOrder(tree->rightTree);
}

//中序遍历
void midOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    midOrder(tree->leftTree);
    printf("%d ", tree->data);
    midOrder(tree->rightTree);
}

//后序遍历
void postOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    postOrder(tree->leftTree);
    postOrder(tree->rightTree);
    printf("%d ", tree->data);
}

以前序遍历进行递归分析图如下：

层序遍历思路分析：

//层序遍历
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);
}

基础选择练习

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为

A E

B F

C G

D H

答案： A

解析：

先序遍历的顺序为：根左子树右子树，故可以通过前序遍历确定二叉树的根节点为E

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。

A adbce

B decab

C debac

D abcde

答案：D

解析：

本题与上题类似，因为后序遍历的顺序为：左子树右子树根，由此可以确定二叉树的根节点为a，而因为中序遍历为badce，故可以a为界限，分出根节点的左子树b和右子树dce，同样根据后序遍历中dec的位置，可以判断出c为根节点，则右子树dce中d为左子树，c为根节点，e为右子树，故前序遍历为abcde

二叉树的节点个数

计算二叉树的节点个数时，可以采用分治的思想来进行计算，即由每一个子树计算自己所含有的节点个数，最后所有子树的个数及根节点相加得出节点个数

而所谓分治的思想，可以一个现实中的管理实例来分析：

对于统计节点个数，分析如下：

//二叉树节点的个数
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层节点个数

求二叉树第k层节点个数，首先就是找到第k层，而在递归中，定义一个变量和k比较的方式并不合适，但是根据递归的特点，只要每一次递归的函数中的k为上一次的k-1，即可实现k减小，当k为1时即可找到所谓的第k层

📌

注意，在二叉树层数定义中，建议第一层为1，第二层为2，以此类推

// 二叉树第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);
}

二叉树第k层节点个数的递归分析图

二叉树查找值为x的节点

二叉树中查找某个值时，遍历二叉树即可，注意此处需要处理好返回值的问题，具体过程分析如下

// 二叉树查找值为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);
}

判断是否是完全二叉树

判断一个树是否是完全二叉树一定不能直接按照数量来判断，因为完全二叉树除了数量上有规定，还必须满足按顺序排列每一层的节点，考虑下面的思路：

使用层序遍历查看二叉树，如果遇到队列中的某一元素为空时，终止遍历二叉树，接着遍历队列剩余的内容，如果在NULL与NULL之间有非NULL的内容，则不是完全二叉树，否则是完全二叉树

// 判断二叉树是否是完全二叉树
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;
}

项目文件

//头文件
#pragma once

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

//定义二叉树的数据类型
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);
//层序遍历
void levelOrder(BTN* tree);
//二叉树节点的个数
int binaryTreeSize(BTN* tree);
// 二叉树叶子节点个数
int binaryTreeLeafSize(BTN* tree);
// 求二叉树的高度
int binaryTreeHeight(BTN* tree);
// 二叉树第k层节点个数
int binaryTreeLevelKSize(BTN* root, BTNDataType k);
// 二叉树查找值为x的节点
BTN* binaryTreeFind(BTN* root, BTNDataType x);
// 二叉树的销毁
void BinaryTreeDestroy(BTN* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTN* root);

//实现文件
#define _CRT_SECURE_NO_WARNINGS 1

#include "BinaryTree.h"
#include "queue.h"

//创建树节点
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 frontOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    printf("%d ", tree->data);
    frontOrder(tree->leftTree);
    frontOrder(tree->rightTree);
}

//中序遍历
void midOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    midOrder(tree->leftTree);
    printf("%d ", tree->data);
    midOrder(tree->rightTree);
}

//后序遍历
void postOrder(BTN* tree)
{
    if (tree == NULL)
    {
        printf("N ");
        return;
    }

    postOrder(tree->leftTree);
    postOrder(tree->rightTree);
    printf("%d ", tree->data);
}

//层序遍历
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 "BinaryTree.h"

void Test()
{
    BTN* tree = createTree();
    //前序遍历
    frontOrder(tree);
    printf("\n");
    //中序变量
    midOrder(tree);
    printf("\n");
    //后序遍历
    postOrder(tree);
    printf("\n");
    //层序遍历
    levelOrder(tree);
    printf("\n");
    //求二叉树节点个数
    printf("%d\n", binaryTreeSize(tree));
    //求二叉树叶子节点的个数
    printf("%d\n", binaryTreeLeafSize(tree));
    //求二叉树的高度
    printf("%d\n", binaryTreeHeight(tree));
    //二叉树第k层节点个数
    printf("%d\n", binaryTreeLevelKSize(tree, 1));
    //二叉树查找值为x的节点
    BTN* node = binaryTreeFind(tree, 5);
    if (node == NULL)
    {
        printf("查无此数");
    }
    else
    {
        printf("%d\n", node->data);
    }

    if (BinaryTreeComplete(tree))
    {
        printf("完全二叉树");
    }
    else
    {
        printf("非完全二叉树");
    }

    BinaryTreeDestroy(tree);
}

int main()
{
    Test();

    return 0;
}