【数据结构】二叉树(c语言)(附源码)

简介: 本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。

前言

       之前我们已经学习了树和二叉树的概念,以及二叉树的顺序实现方式--堆,今天我们尝试以链式结构实现二叉树的一些功能(前中后序遍历、层序遍历、统计节点个数和树的高度,以及判断是否为完全二叉树等)。


一、节点的定义

       以链式结构实现二叉树,即使用类似链表的方式,将数据存放于一个节点中,该节点的指针域存放指向左孩子和右孩子节点的指针。节点的定义如下:

typedef int BTDataType;
 
//定义二叉树节点
typedef struct BinaryTreeNode
{
    BTDataType data;//存放的数据
    struct BinaryTreeNode* leftchild;//指向左孩子的指针
    struct BinaryTreeNode* rightchild;//指向右孩子的指针
}BTNode;

二、创建一棵二叉树

       由于目前我们所学习的二叉树结构并非是自平衡的,使用固定方法插入数据的意义不大,所以我们就来手动创建一棵二叉树,后续针对这棵二叉树,验证我们实现的方法


1. 创建新节点

       创建新节点的方式与链表相同。注意新节点的两指针都制为空:

//创建新节点
BTNode* BTBuyNode(BTDataType n)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间
    if (newnode == NULL)//内存申请失败,则直接退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->leftchild = newnode->rightchild = NULL;
    return newnode;
}

2. 手动创建二叉树

       接下来,我们创建一些节点,然后将这些节点连接起来,形成一颗二叉树。

//手动创建二叉树
BTNode* CreateTree()
{
    //创建6个节点
    BTNode* n1 = BTBuyNode(1);
    BTNode* n2 = BTBuyNode(2);
    BTNode* n3 = BTBuyNode(3);
    BTNode* n4 = BTBuyNode(4);
    BTNode* n5 = BTBuyNode(5);
    BTNode* n6 = BTBuyNode(6);
 
    //连接节点
    n1->leftchild = n2;
    n1->rightchild = n3;
    n2->leftchild = n4;
    n2->rightchild = n5;
    n3->rightchild = n6;
 
    //返回根节点
    return n1;
}

       二叉树已经创建好了,我们画一下它的逻辑结构图



三、方法的声明

       关于二叉树我们要实现的方法声明如下:

//前序遍历
void PreOrder(BTNode* root);
 
//中序遍历
void InOrder(BTNode* root);
 
//后序遍历
void PostOrder(BTNode* root);
 
//层序遍历
void LevelOrder(BTNode* root);
 
//二叉树节点个数
int BTSize(BTNode* root);
 
//叶子节点个数
int BTLeafSize(BTNode* root);
 
//第K层节点个数
int BTLevelKSize(BTNode* root, int k);
 
//二叉树高度
int BTDepth(BTNode* root);
 
//查找
BTNode* BTFind(BTNode* root, BTDataType n);
 
//判断是否为完全二叉树
bool BTComplete(BTNode* root);
 
//销毁二叉树
void BTDestroy(BTNode** proot);

四、方法的实现

       接下来,我们一一介绍并尝试实现这些方法。


1. 前、中、后序遍历

       前、中、后序遍历是二叉树最常见、最重要的遍历方式。这三种遍历方式都将二叉树分为三个部分:根节点、左子树、右子树。理解这三种遍历方式,会加深我们对函数递归的理解。接下来我们一一讲解。


1.1 前(先)序遍历

       所谓前序遍历,指的是在遍历二叉树时,访问根节点的操作发生在左右子树之前。它的访问顺序是:


根节点-->左子树-->右子树


当访问到每一棵子树时,这棵子树也可以再分为根节点、左子树、右子树,然后继续遵循这一套访问方式。不难发现,这是一个递归的过程。递归结束的条件是访问到空指针,意味着该节点的左子树或右子树不存在


       我们就刚才创建好的那个二叉树,分析一下对其前序遍历的结果:



       遍历逻辑看似十分复杂,但是它的代码写起来却非常简单。接下来我们实现前序遍历

//前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)//访问到空指针就停止遍历
    {
        return;
    }
    printf("%d ", root->data);//打印根节点数据
    PreOrder(root->leftchild);//遍历左子树
    PreOrder(root->rightchild);//遍历右子树
}

代入测试:

int main()
{
    BTNode* root = CreateTree();
    PreOrder(root);
    return 0;
}

运行结果:



1.2 中序遍历

       中序遍历指的是访问根节点的操作发生在左右子树之中。它的遍历顺序是:


左子树-->根节点-->右子树


对于左右子树,它的访问逻辑与前序遍历相同,也是递归的。接下来我们分析中序遍历结果:



       当然,它的代码也十分简单:

//中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)//访问到空指针就停止遍历
    {
        return;
    }
    InOrder(root->leftchild);//遍历左子树
    printf("%d ", root->data);//打印根节点数据
    InOrder(root->rightchild);//遍历右子树
}

测试结果:



1.3 后序遍历

       后序遍历的含义是访问根节点的操作发生在其左右子树之后。它的遍历顺序是:


左子树-->右子树-->根节点


它的递归遍历逻辑不言而喻。遍历分析如下:



代码一如既往的简单:

//后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    PostOrder(root->leftchild);//遍历左子树
    PostOrder(root->rightchild);//遍历右子树
    printf("%d ", root->data);//打印根节点数据
}

测试结果:



2. 层序遍历

       所谓层序遍历,通俗地讲,就是从上到下,从左到右逐层遍历。对于我们创建的二叉树,它的遍历结果应该是:1,2,3,4,5,6


       进行层序遍历操作,需要借助数据结构“队列”来实现。关于队列,在博主的另一篇文章中有所实现:


https://developer.aliyun.com/article/1634734?spm=a2c6h.13262185.profile.33.2ca12c70iTcquf


在实现层序遍历时,队列相关函数我们就直接调用了,不再重复实现(注意将队列的数据元素类型调整为二叉树的节点指针类型)。接下来讲讲层序遍历的方法


1.首先将头节点存放于队列当中。


2.如果队列不为空,则读取一个节点的数据,并让该节点出队。


3.读取一个节点的数据之后,若该节点有左子节点,则将左子节点入队;有右子节点,则将右子节点入队。


4.重复第2步,直到队列为空为止。


我们画图表示一下遍历过程:



不难发现,从上到下出队的数据依次排成了1,2,3,4,5,6。接下来,我们尝试写代码实现该过程:

//层序遍历
void LevelOrder(BTNode* root)
{
    Queue q;//创建队列
    QInit(&q);//初始化队列
    QPush(&q, root);//根节点入队
    while (!QEmpty(&q))//队列不为空,进入循环
    {
        BTNode* front = QFront(&q);//记录队头数据
        printf("%d ", front->data);//读数据
        QPop(&q);//出队
        if (front->leftchild != NULL)
        {
            QPush(&q, front->leftchild);//若左孩子不为空,则左孩子入队
        }
        if (front->rightchild != NULL)
        {
            QPush(&q, front->rightchild);//若右孩子不为空,则右孩子入队
        }
    }
    QDestroy(&q);//销毁队列
}

测试结果:



3. 二叉树节点个数

       接下来,我们写一个函数统计二叉树节点个数。它的实现方法十分简单,当一个节点有效时,返回1,之后递归判断该节点的左右孩子是否有效......最后将这些“1”相加即可。代码如下:

//二叉树节点个数
int BTSize(BTNode* root)
{
    if (root == NULL)//访问到空指针,则结束
    {
        return 0;
    }
    return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效,返回1,再与左右孩子的判断结果相加
}

递归示意图:



测试结果:



4. 叶子节点个数

       在统计叶子节点时,需要注意:叶子节点是度为0的节点。所以我们在做节点判断时,要判断该节点的左右孩子是否为空。如果都为空,则它是一个叶子节点。实现代码如下:

//叶子节点个数
int BTLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件,返回1
    {
        return 1;
    }
    return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加
}

递归示意图:



测试结果:



5. 第K层节点个数

       在统计第K层节点的个数时,我们不仅需要判断节点的有效性,而且需要确定该节点所在的层数。至于层数该怎么确定呢?


       首先来看一段代码:

int main()
{
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    int k = 5;
    int i = 0;
    while (k != 1)
    {
        k--;
        i++;
    }
    printf("%d\n", arr[i]);
    return 0;
}

运行结果:



在这里,我们使用了一种特殊的方式访问数组中的第五个元素。我们循环使k自减,当k的值为1时,下标 i 就走到了第五个元素的位置处。而对于二叉树第k层节点的统计,也是这个原理。在使用递归时,每次遍历下一层(左右孩子)并传入k-1这个值,当k值为1时,再做统计,就实现了统计第k层节点的功能。代码实现:

//第K层节点个数
int BTLevelKSize(BTNode* root, int k)
{
    if (root == NULL)//访问到空,返回0
    {
        return 0;
    }
    if (k == 1)//k值为1,做统计
    {
        return 1;
    }
    return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子(下一层)
}

递归示意图:



测试代码与结果:

int main()
{
    BTNode* root = CreateTree();
    int k = 0;
    scanf("%d", &k);
    printf("第%d层节点个数为:%d\n", k, BTLevelKSize(root, k));
}


6. 二叉树高度

       二叉树的高度计算原理十分简单,和之前节点个数的统计相似,当访问了一个有效节点之后,说明层数至少为1。之后再去访问它的左子树和右子树是否有效...这里需要注意:有时候二叉树的左子树和右子树高度不相同,需要将最高的那棵子树计入到高度当中


代码实现:

//二叉树高度
int BTDepth(BTNode* root)
{
    if (root == NULL)//根节点为空则为0层
    {
        return 0;
    }
    int leftDepth = BTDepth(root->leftchild);//统计左子树高度
    int rightDepth = BTDepth(root->rightchild);//统计右子树高度
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度,再与根节点层数相加
}

递归示意图:



测试结果:



7. 查找

       查找的思路也比较简单,只需要遍历根节点、左子树、右子树,若找到相应的值,则将该节点返回即可。代码如下:

//查找
BTNode* BTFind(BTNode* root, BTDataType n)
{
    if (root == NULL)//访问到空则停止
    {
        return NULL;
    }
    if (root->data == n)//找到了,返回该节点
    {
        return root;
    }
    BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树
    if (leftFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回
    {
        return leftFind;
    }
    BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树
    if (rightFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回
    {
        return rightFind;
    }
}

测试代码及结果:

int main()
{
    BTNode* root = CreateTree();
    int x = 0;
    while (1)
    {
        scanf("%d", &x);
        if (BTFind(root, x) != NULL)
        {
            printf("找到了\n");
        }
        else
        {
            printf("找不到\n");
        }
        printf("\n");
    }
}


8. 判断是否为完全二叉树

       我们在进行层序遍历二叉树时,是按照从上到下,从左到右的顺序进行的。由于完全二叉树最后一层的节点需要从左到右依次排列,我们就可以对这棵二叉树进行层序遍历。        


       如果遍历结果当中有两个节点之间有空指针,就说明这两个节点不是从左到右依次排列的,这棵二叉树也就不是完全二叉树了;反之,如果节点之间没有空指针,则说明它就是一棵完全二叉树。这里需要注意:由于要判断空指针的存在,遍历时就需要将空指针也存入队列


我们针对创建好的二叉树,画个图演示一下执行流程:



代码实现:

//判断是否为完全二叉树
bool BTComplete(BTNode* root)
{
    Queue q;
    QInit(&q);//初始化队列
    QPush(&q, root);//根节点入队
    while (!QEmpty(&q))//队列不为空进入循环
    {
        BTNode* front = QFront(&q);//记录队头
        QPop(&q);//队头出队
        if (front == NULL)//当读取到空指针时,跳出循环
        {
            break;
        }
        QPush(&q, front->leftchild);//左孩子入队
        QPush(&q, front->rightchild);//右孩子入队
    }
 
    //此时,再次循环读取队头数据,若读取到非空节点,说明不是完全二叉树
    while (!QEmpty(&q))
    {
        BTNode* front = QFront(&q);//记录队头
        QPop(&q);//队头出队
        if (front != NULL)
        {
            //出现非空节点
            QDestroy(&q);//销毁队列
            return false;
        }
    }
 
    //读完了所有的空指针,还没有遇到非空节点,说明是完全二叉树
    QDestroy(&q);//销毁队列
    return true;
}

测试代码与结果:

int main()
{
    BTNode* root = CreateTree();
    if (BTComplete(root))
    {
        printf("是完全二叉树\n");
    }
    else
    {
        printf("不是完全二叉树\n");
    }
}


9. 销毁二叉树

       完成了这么多的工作之后,我们就要销毁这棵二叉树了。销毁二叉树的过程与后序遍历相似,先将左右子树销毁,然后销毁根节点。由于这里会改变根节点的值,所以需要传入二级指针


代码如下:

//销毁二叉树
void BTDestroy(BTNode** proot)
{
    if (*proot == NULL)//访问到空指针则回退
    {
        return;
    }
    BTDestroy(&((*proot)->leftchild));//销毁左子树(leftchild是一级指针,函数接收二级指针所以要取地址)
    BTDestroy(&((*proot)->rightchild));//销毁右子树(rightchild是一级指针,函数接收二级指针所以要取地址)
    free(*(proot));//销毁根节点
    *proot = NULL;
}

五、程序全部代码

辅助数据结构--队列:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef BTNode* QDataType;
 
//定义队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QNode;
 
typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;
 
//初始化
void QInit(Queue* pq);
 
//判空
bool QEmpty(Queue* pq);
 
//入队列
void QPush(Queue* pq, QDataType n);
 
//出队列
void QPop(Queue* pq);
 
//取队头数据
QDataType QFront(Queue* pq);
 
//取队尾数据
QDataType QBack(Queue* pq);
 
//获取队列有效元素个数
int QSize(Queue* pq);
 
//销毁
void QDestroy(Queue* pq);
 
//初始化
void QInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
 
//判空
bool QEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead == NULL && pq->ptail == NULL;
}
 
//入队列
void QPush(Queue* pq, QDataType n)
{
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->next = NULL;
    if (QEmpty(pq))
    {
        pq->phead = pq->ptail = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = pq->ptail->next;
    }
    pq->size++;
}
 
//出队列
void QPop(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    if (pq->phead == pq->ptail)
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else
    {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}
 
//取队头数据
QDataType QFront(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->phead->data;
}
 
//取队尾数据
QDataType QBack(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->ptail->data;
}
 
//获取队列有效元素个数
int QSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}
 
//销毁
void QDestroy(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;
}

二叉树:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int BTDataType;
 
//定义二叉树节点
typedef struct BinaryTreeNode
{
    BTDataType data;//存放的数据
    struct BinaryTreeNode* leftchild;//指向左孩子的指针
    struct BinaryTreeNode* rightchild;//指向右孩子的指针
}BTNode;
 
//前序遍历
void PreOrder(BTNode* root);
 
//中序遍历
void InOrder(BTNode* root);
 
//后序遍历
void PostOrder(BTNode* root);
 
//层序遍历
void LevelOrder(BTNode* root);
 
//二叉树节点个数
int BTSize(BTNode* root);
 
//叶子节点个数
int BTLeafSize(BTNode* root);
 
//第K层节点个数
int BTLevelKSize(BTNode* root, int k);
 
//二叉树高度
int BTDepth(BTNode* root);
 
//查找
BTNode* BTFind(BTNode* root, BTDataType n);
 
//判断是否为完全二叉树
bool BTComplete(BTNode* root);
 
//销毁二叉树
void BTDestroy(BTNode** proot);
 
//创建新节点
BTNode* BTBuyNode(BTDataType n)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间
    if (newnode == NULL)//内存申请失败,则直接退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->leftchild = newnode->rightchild = NULL;
    return newnode;
}
 
//手动创建二叉树
BTNode* CreateTree()
{
    //创建6个节点
    BTNode* n1 = BTBuyNode(1);
    BTNode* n2 = BTBuyNode(2);
    BTNode* n3 = BTBuyNode(3);
    BTNode* n4 = BTBuyNode(4);
    BTNode* n5 = BTBuyNode(5);
    BTNode* n6 = BTBuyNode(6);
 
    //连接节点
    n1->leftchild = n2;
    n1->rightchild = n3;
    n2->leftchild = n4;
    n2->rightchild = n5;
    n3->rightchild = n6;
 
    //返回根节点
    return n1;
}
 
//前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)//访问到空指针就停止遍历
    {
        return;
    }
    printf("%d ", root->data);//打印根节点数据
    PreOrder(root->leftchild);//遍历左子树
    PreOrder(root->rightchild);//遍历右子树
}
 
//中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)//访问到空指针就停止遍历
    {
        return;
    }
    InOrder(root->leftchild);//遍历左子树
    printf("%d ", root->data);//打印根节点数据
    InOrder(root->rightchild);//遍历右子树
}
 
//后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    PostOrder(root->leftchild);//遍历左子树
    PostOrder(root->rightchild);//遍历右子树
    printf("%d ", root->data);//打印根节点数据
}
 
//层序遍历
void LevelOrder(BTNode* root)
{
    Queue q;//创建队列
    QInit(&q);//初始化队列
    QPush(&q, root);//根节点入队
    while (!QEmpty(&q))//队列不为空,进入循环
    {
        BTNode* front = QFront(&q);//记录队头数据
        printf("%d ", front->data);//读数据
        QPop(&q);//出队
        if (front->leftchild != NULL)
        {
            QPush(&q, front->leftchild);//若左孩子不为空,则左孩子入队
        }
        if (front->rightchild != NULL)
        {
            QPush(&q, front->rightchild);//若右孩子不为空,则右孩子入队
        }
    }
    QDestroy(&q);//销毁队列
}
 
//二叉树节点个数
int BTSize(BTNode* root)
{
    if (root == NULL)//访问到空指针,则结束
    {
        return 0;
    }
    return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效,返回1,再与左右孩子的判断结果相加
}
 
//叶子节点个数
int BTLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件,返回1
    {
        return 1;
    }
    return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加
}
 
//第K层节点个数
int BTLevelKSize(BTNode* root, int k)
{
    if (root == NULL)//访问到空,返回0
    {
        return 0;
    }
    if (k == 1)//k值为1,做统计
    {
        return 1;
    }
    return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子(下一层)
}
 
//二叉树高度
int BTDepth(BTNode* root)
{
    if (root == NULL)//根节点为空则为0层
    {
        return 0;
    }
    int leftDepth = BTDepth(root->leftchild);//统计左子树高度
    int rightDepth = BTDepth(root->rightchild);//统计右子树高度
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度,再与根节点层数相加
}
 
//查找
BTNode* BTFind(BTNode* root, BTDataType n)
{
    if (root == NULL)//访问到空则停止
    {
        return NULL;
    }
    if (root->data == n)//找到了,返回该节点
    {
        return root;
    }
    BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树
    if (leftFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回
    {
        return leftFind;
    }
    BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树
    if (rightFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回
    {
        return rightFind;
    }
}
 
//判断是否为完全二叉树
bool BTComplete(BTNode* root)
{
    Queue q;
    QInit(&q);//初始化队列
    QPush(&q, root);//根节点入队
    while (!QEmpty(&q))//队列不为空进入循环
    {
        BTNode* front = QFront(&q);//记录队头
        QPop(&q);//队头出队
        if (front == NULL)//当读取到空指针时,跳出循环
        {
            break;
        }
        QPush(&q, front->leftchild);//左孩子入队
        QPush(&q, front->rightchild);//右孩子入队
    }
 
    //此时,再次循环读取队头数据,若读取到非空节点,说明不是完全二叉树
    while (!QEmpty(&q))
    {
        BTNode* front = QFront(&q);//记录队头
        QPop(&q);//队头出队
        if (front != NULL)
        {
            //出现非空节点
            QDestroy(&q);//销毁队列
            return false;
        }
    }
 
    //读完了所有的空指针,还没有遇到非空节点,说明是完全二叉树
    QDestroy(&q);//销毁队列
    return true;
}
 
//销毁二叉树
void BTDestroy(BTNode** proot)
{
    if (*proot == NULL)//访问到空指针则回退
    {
        return;
    }
    BTDestroy(&((*proot)->leftchild));//销毁左子树(leftchild是一级指针,函数接收二级指针所以要取地址)
    BTDestroy(&((*proot)->rightchild));//销毁右子树(rightchild是一级指针,函数接收二级指针所以要取地址)
    free(*(proot));//销毁根节点
    *proot = NULL;
}

总结

       今天,我们学习了二叉树链式结构相关功能的实现,如遍历、统计节点个数、查找、销毁等。这些功能的实现加深了我们对递归的理解,并且让我们学会了使用数据结构作为辅助来解决问题。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
49 8
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
36 7
|
6天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
18 1
|
算法 C语言
C语言数据结构(15)--二叉树的前序、中序、后序遍历
本文目录 1. 背景 2. 前序遍历 3. 中序遍历 4. 后序遍历 5. 层序遍历 6. 代码实现
355 0
C语言数据结构(15)--二叉树的前序、中序、后序遍历
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
33 3
|
6天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
21 6
|
25天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
34 10
|
19天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。