【C语言】手撕二叉树

ops/2024/9/23 11:15:36/

标题：【C语言】手撕二叉树

@水墨不写bug

正文开始：

        二叉树是一种基本的树形数据结构，对于初学者学习树形结构而言较容易接受。二叉树作为一种数据结构，在单纯存储数据方面没有  顺序表，链表，队列等线性结构  有优势，但是二叉树的搜索功能十分强大——高阶数据结构比如红黑树，B树等的基础就是搜索二叉树。

        二叉树的基本知识讲解：二叉树讲解

        对于初学者，首先学习二叉树的存储结构对于理解二叉树的本质结构非常有效。

（一）头文件

        本文不加解释的给出二叉树的头文件：

        Bitree.h

        并根据头文件来实现二叉树数据结构的相关功能。包括：二叉树的（前序）构建，二叉树的销毁，二叉树节点个数，二叉树叶子节点个数，二叉树第K层节点个数，二叉树查找值为x的节点，二叉树前序遍历，二叉树中序遍历，二叉树后序遍历，层序遍历，判断二叉树是否是完全二叉树等共11个功能。

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>//节点数据类型
typedef char BiTreeDataType;//二叉树节点
typedef struct BiTreeNode
{BiTreeDataType _val;struct BiTreeNode* _left;struct BiTreeNode* _right;
}BTNode;// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BiTreeDataType* a, int* pi);// 二叉树销毁
void BinaryTreeDestory(BTNode* root);// 二叉树节点个数
int BinaryTreeSize(BTNode* root);// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BiTreeDataType x);// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

（二）功能实现

        本文的二叉树是通过递归实现的，想要写好递归，需要注意一下几点：

        递归首先要有递归出口：

        确保递归函数的每一步都朝着基本情况靠近：在写递归函数时，确保每一步递归调用都是在缩小问题规模的基础上进行的。如果递归函数每一步都朝着基本情况靠近，那么递归一定会终止；

        写递归要有的思路：

        只考虑两层情况，即  本层递归  和  下一层递归  ，根据本层递归与下一层递归的关系，来写递归的逻辑；

        写递归要相信自己的函数：

        在写递归的时候，我们使用的下一层递归函数通常是一个黑盒，但是我们要相信递归函数一定完成任务。

（1）前序遍历

        首先判断此节点是否是空节点，若是，则退出递归。（这就是递归的出口）

        接下来访问此节点：printf（）函数的调用代表访问节点。

        最后递归访问此节点的左子树和右子树。


// 二叉树前序遍历 root + left + right
void BinaryTreePrevOrder(BTNode* root)
{//递归出口if (root == NULL)return;printf("%d", root->_val);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}

（2）中序遍历

        首先判断此节点是否是空节点，若是，则退出递归。（这就是递归的出口）

        然后递归访问次节点的左子树。

        接下来访问此节点：printf（）函数的调用代表访问节点。

        最后递归访问此节点的右子树。


// 二叉树中序遍历 left + root + right
void BinaryTreeInOrder(BTNode* root)
{//递归出口if (root == NULL)return;BinaryTreePrevOrder(root->_left);printf("%d", root->_val);BinaryTreePrevOrder(root->_right);
}

（3）后序遍历

        首先判断此节点是否是空节点，若是，则退出递归。（这就是递归的出口）

        然后递归访问次节点的右子树。

        接下来访问此节点：printf（）函数的调用代表访问节点。

        最后递归访问此节点的左子树。


// 二叉树后序遍历 left + root + right
void BinaryTreePostOrder(BTNode* root)
{//递归出口if (root == NULL)return;BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);printf("%d", root->_val);
}

（4）二叉树的（前序）构建

       前序构建的思路就是前序遍历的思路：先完成对根节点的访问，再递归构建左右子树。

访问根节点：

        根据字符串的当前的字符来决定：如果当前字符为‘#’，返回NULL表示空节点；如果不是‘#’，则创建新节点，并将此字符存入新节点。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树  pi的作用计数，便于填充数组
// 接受一个字符串，‘#’ 表示 空节点。
BTNode* BinaryTreeCreate(BiTreeDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->_val = a[(*pi)++];root->_left = BinaryTreeCreate(a,pi);root->_right = BinaryTreeCreate(a,pi);return root;
}

（5）二叉树的销毁

        递归销毁，如果此节点为空，此时不能访问此节点，直接返回即可，目的是返回到上一层来销毁；（也就是递归出口的定义）

        之后再递归销毁左子树和右子树，最后释放此节点。


// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);//要在外部将root置空
}

（6）二叉树节点个数

        递归计数，如果此节点为空，返回0，不计数。

        否则返回左子树的计数结果和右子树的计数结果 + 1（此节点的计数）。


// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

（7）二叉树叶子节点个数

        叶子节点有一个特征：左子树和右子树都为空。

        如果遇到这样的节点，计数+1；

        最后返回左子树与右子树的计数结果之和。


// 二叉树 叶子节点 个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->_left == NULL && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

（8）二叉树第K层节点个数

       模拟递归：

        想象一下：在一个楼层中，假如你要下降K层，如何计数呢？

        在这里我们需要定义一个变量k作为标牌，标识还需要下降的层数。由于本层默认标定为1，所以当k==1时，计数+1；

        最后返回递归左子树和和右子树的结果。


// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (NULL == root)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);
}

（9）二叉树查找值为x的节点

         查找思路：

        首先判断根节点是否为空，若为空，表示访问到叶子节点的左右节点，返回空表示没有找到。（另一种情况根节点为空表示整棵树都为空，也返回空表示没有找到）

        如果找到x返回这个节点的地址，表示找到了。

        接下来递归访问左右子树：

        需要注意的是：

        创建一个临时变量ret_l(ret_r)来接收在左右子树查找的结果，如果找到（ret_l(ret_r)不为空）则返回左(右)子树返回的结果；

        如果左右子树都没有找到，则返回空。


// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BiTreeDataType x)
{if (root == NULL)return NULL;if (root->_val == x)return root;BTNode* ret_l = BinaryTreeFind(root->_left, x);if (ret_l)return ret_l;BTNode* ret_r = BinaryTreeFind(root->_right, x);if (ret_r)return ret_r;return NULL;
}

（10）层序遍历

        思路：（不使用递归，通过一个循环和数据结构队列来实现。）

        初始时进一个根节点，接下来出一进二，从队头出一个数据同时压入两个数据——出根节点的同时进左子节点和右子节点，直到把队列出为空。

        printf（）代表了对此节点的遍历。


// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue queue;Qinit(&queue);if (root != NULL)Qpush(&queue, root);while (!Qempty(&queue)){BTNode* front = Qfront(&queue);//队列先进先出Qpop(&queue);printf("%d", front->_val);if (front->_left)Qpush(&queue,front->_left);if (front->_right)Qpush(&queue,front->_right);}QDestroy(&queue);
}

（11）判断二叉树是否是完全二叉树

       

        思路：

        通过层序遍历来遍历二叉树。完全二叉树和非完全二叉树的区别就是完全二叉树的最后一个节点之前没有空节点。通过层序遍历来遍历二叉树，当找到空节点时，此时查找队列内是否有非空节点：

        如果都是空，此树是完全二叉树；

        如果有非空节点，此树不是完全二叉树。


// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue queue;Qinit(&queue);if (root != NULL)Qpush(&queue, root);while (!Qempty(&queue)){BTNode* front = Qfront(&queue);//队列先进先出Qpop(&queue);if (front == NULL)break;Qpush(&queue, front->_left);Qpush(&queue, front->_right);}//如果队列里剩下的全是NULL，则是完全二叉树；否则不是while (!Qempty(&queue)){BTNode* front = Qfront(&queue);//队列先进先出Qpop(&queue);if (front){QDestroy(&queue);return false;}}QDestroy(&queue);return true;
}

完~

未经作者同意禁止转载 


http://www.ppmy.cn/ops/11499.html

相关文章

记录：阿里云服务器网站搭建（4）

记录：阿里云服务器网站搭建（4）

Docker安装Nginx 现阶段主要目的是做一些静态资源路径的转发代理&#xff0c;相当于一个web服务器&#xff0c;tomcat也可以设置凡访问静态资源。但考虑到后续还需要作为代理服务器对域名等进行代理转发&#xff0c;所以使用nginx。 准备好要挂载的nginx配置目录 mkdir -p /m…
阅读更多...
TS学习3-枚举

TS学习3-枚举

目录 1&#xff0c;枚举2&#xff0c;定义枚举3&#xff0c;枚举的规则1&#xff0c;枚举的值可以是字符串或数字&#xff0c;分别称为字符串枚举、数字枚举2&#xff0c;数字枚举的值会自增3&#xff0c;枚举会出现在编译结果中&#xff0c;并且数字枚举和字符串枚举&#xff…
阅读更多...
淘宝扭蛋机小程序开发：开启幸运与惊喜的新篇章

淘宝扭蛋机小程序开发：开启幸运与惊喜的新篇章

在移动互联网时代&#xff0c;小程序以其便捷、快速和轻量级的特点&#xff0c;正迅速成为用户日常生活中的重要一环。为了满足广大用户对新鲜、有趣体验的追求&#xff0c;淘宝扭蛋机小程序应运而生&#xff0c;为用户带来一场充满惊喜和乐趣的幸运之旅。 淘宝扭蛋机小程序的…
阅读更多...
Collections.singletonList

Collections.singletonList

1、Collections.singletonList public static <T> List<T> singletonList(T o) {return new SingletonList<>(o); } 列表只有一个元素&#xff0c;节省内存&#xff0c;返回列表不可以改变。 2、Arrays.asList public static <T> List<T> asL…
阅读更多...
MongoDB学习【一】MongoDB简介和部署

MongoDB学习【一】MongoDB简介和部署

MongoDB简介 MongoDB是一种开源的、面向文档的、分布式的NoSQL数据库系统&#xff0c;由C语言编写而成。它的设计目标是为了适应现代Web应用和大数据处理场景的需求&#xff0c;提供高可用性、横向扩展能力和灵活的数据模型。 主要特点&#xff1a; 文档模型&#xff1a; Mon…
阅读更多...
十几个好用的学习以及AI网站

十几个好用的学习以及AI网站

目录 1.识典古籍 2.华文慕课 3.历代人物 4.北大出版社电子书架 5.WaytoAGI 6.W3Schools 7.AI帮个忙 8.InsCode 9.文心一格 10.即使设计 11.AI绘画 12.无界AI 13.Midjourney中文站 14.其它 1.识典古籍 地址&#xff1a;识典古籍-古籍在线阅读平台 “识典古籍”是…
阅读更多...
C语言指针+-整数、指针-指针、指针关系运算、指针和数组、二级指针、指针数组

C语言指针+-整数、指针-指针、指针关系运算、指针和数组、二级指针、指针数组

文章目录 前言一、指针 - 整数二、指针 - 指针三、指针的关系运算四、指针和数组五、二级指针六、指针数组指针数组可以将几个一维数组模拟成二维数组 总结 前言 C语言指针整数、指针-指针、指针关系运算、指针和数组、二级指针、指针数组等介绍&#xff0c;还包括指针数组将几…
阅读更多...
k8s的资源对象Deployment该如何使用？

k8s的资源对象Deployment该如何使用？

k8s的资源对象Deployment该如何使用&#xff1f; Kubernetes&#xff08;k8s&#xff09;是一个开源的容器编排系统&#xff0c;用于自动化应用程序部署、扩展和管理。在k8s中&#xff0c;Deployment是管理Pod副本的一种方式&#xff0c;它确保了指定数量的Pod副本始终运行。本…
阅读更多...
最新文章

Copyright @ 2022~2023