带你手撕链式二叉树—【C语言】

这篇具有很好参考价值的文章主要介绍了带你手撕链式二叉树—【C语言】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

带你手撕链式二叉树—【C语言】

 前言:

普通二叉树的增删查改没有意义?那我们为什么要先学习普通二叉树呢?

给出以下两点理由:

1.为后面学习更加复杂的二叉树打基础。(搜索二叉树、ALV树、红黑树、B树系列—多叉平衡搜索树)

2.有很多二叉树的OJ算法题目都是出在普通二叉树的基础上


让我们开始数据结构链式二叉树之旅吧!!!


1. 链式二叉树的遍历

1.1 前序、中序以及后序遍历概念

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。     访问顺序—— 根 —> 左子树—>右子树

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。

            访问顺序—— 左子树—>根 —>右子树

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

             访问顺序—— 左子树—>右子树—>根

 举例


带你手撕链式二叉树—【C语言】


带你手撕链式二叉树—【C语言】


1.2 前序、中序以及后序遍历代码实现

1.2.1创建二叉树节点

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left; //左子树
	struct BinaryTreeNode* right;//右子树
	BTDataType data;//数据
}BTNode;

1.2.2 手动搓出一颗二叉树

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatBinaryTree()  //搓树
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

void PreOrder(BTNode* root) //前序遍历
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

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

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL) {
		printf("# ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}


int main()
{
	BTNode* root = CreatBinaryTree();

	PreOrder(root);//前序遍历
	printf("\n");

	InOrder(root);//中序遍历
	printf("\n");

	PostOrder(root);//后序遍历
	printf("\n");

	return 0;
}

1.2.3 代码结果

带你手撕链式二叉树—【C语言】

1.2.4 递归展开图

(学习二叉树的链式结构,一定要学会画递归展开图)

注意:访问到空树的时候,return的时候不是结束递归,是返回到函数被调用的地方

下面是前序遍历的左子树的递归展开图(右子树原理同理) 》》》

带你手撕链式二叉树—【C语言】



2. 求二叉树节点的个数

2.1 全局count的方式(不推荐)

在写代码的过程中要尽量少使用全局变量,这里也是一样的,采用全局变量会有下面的问题:

我们在调用两次的情况下,count会加倍

代码实现

int count = 0;
void TreeSize1(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	++count;
	TreeSize1(root->left);
	TreeSize1(root->right);
}

带你手撕链式二叉树—【C语言】


2.2 采用分治的思路

将一颗二叉树分解为3个部分——根节点、左子树、右子树

代码实现:

int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

带你手撕链式二叉树—【C语言】

递归展开图

注意:这里的二叉树和上面的不一样(但是计算方式的大致一样的)


蓝色的数字是递归的次序

红色的数字1,表示返回节点的个数——最后是左子树返回3、右子树返回3、+1,一共是7个节点(可以看出,+1都是递归返回的时候加)

带你手撕链式二叉树—【C语言】



3. 求二叉树叶子节点的个数


带你手撕链式二叉树—【C语言】

思路分析

什么是叶子节点呢  ——> 左右孩子都是空的节点      像上面的二叉树节点个数就是3


怎么控制呢 ——> 1. 二叉树是空树的

                             2. 二叉树就一个根节点(也就是左右子树为空)

                             3. 到了第三点,那就直接递归到空,递归到空,就进入第二点,返回1

代码实现 

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left== NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}


4. 求二叉树第k层的节点数量


带你手撕链式二叉树—【C语言】


思路分析

方法:转换成最小规模的子问题

思路:求第k层的节点,转换成左子树的第k-1层+右子树的第k-1层

每递归一次,k都会-1,当k=1时,就会返回1(也可以看出k不可能减到0)


注意点1:这里的k不能写成k--的形式,递归左子树的时候就k--的话,会改变k,到递归右子树的时候就会出问题

注意点2:重要的事情说三遍!!!  return是返回函数被调用的地方,不是结束整个递归

代码实现

int TreeKLevel(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return TreeKLevel(root->left, k - 1)
		+ TreeKLevel(root->right, k - 1);
}

带你手撕链式二叉树—【C语言】

递归展开图(部分)

带你手撕链式二叉树—【C语言】



   链式二叉树的知识点比较多,小余在这里分成两部分来写,感兴趣的可以等我的下一期哦!!!

如果觉得文章不错,期待你的一键三连哦,你个鼓励是我创作的动力之源,让我们一起加油,顶峰相见!!!文章来源地址https://www.toymoban.com/news/detail-461087.html

到了这里,关于带你手撕链式二叉树—【C语言】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】---几分钟简单几步学会手撕链式二叉树(上)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:手撕链式二叉树 送给各位💌:我从没觉得孤独 说的浪漫点 我完全自由 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下

    2024年02月07日
    浏览(34)
  • 【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

    欢迎来到 Claffic 的博客  💞💞💞 “东风随春归,发我枝上花。” 前言:  排序是日常生活中极其常见的一种算法,它的功能很简单,就是将数字按照升序/降序排列,最终形成一组有序的数字,不过形成有序数字的过程有多种实现方式,它们各有好坏,接下来,由我带你手

    2023年04月19日
    浏览(44)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(43)
  • 二叉树的链式结构 - C语言(含有大量递归)

    目录: 🍔前言 🍔二叉树链式结构的实现 🍟基本构架 😍代码: 🍔二叉树的遍历 🍟前序遍历 🍟中序遍历 🍟后序遍历 🍟层序遍历 🔴层序遍历的思路及代码 🍔 构建二叉树  😍代码: 🍔二叉树销毁 😍代码:   🍔二叉树节点个数 😍代码: 🍔二叉树叶子节点个数

    2024年02月08日
    浏览(33)
  • 二叉树的链式结构 - 遍历 - C语言递归实现

    前序、中序以及后序遍历         二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次 。 按照规则,二叉树的遍历有: 前序/中序/后序 的递归结构遍历 : 1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结

    2024年02月15日
    浏览(32)
  • 【C语言】数据结构——链式二叉树实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表,顺序表,栈和队列,小堆。 今天我们来学习链式二叉树 关注博主或是订阅专栏,掌握第一消息。 链式二叉树(Linked Binary Tree)是一种基于链表实现的二叉树结构。

    2024年02月04日
    浏览(37)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(48)
  • 数据结构入门(C语言版)二叉树链式结构的实现

    简单回顾一下二叉树的 概念: ★ 空树 ★非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。 下面我们先看二叉树的结构体定义以及创建 首先结构体的定义是元素本身,以

    2023年04月23日
    浏览(46)
  • 数据结构入门(C语言版)一篇文章教会你手撕八大排序

    排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而

    2024年02月01日
    浏览(63)
  • 【链式二叉树】数据结构链式二叉树的(万字详解)

    前言: 在上一篇博客中,我们已经详解学习了堆的基本知识,今天带大家进入的是二叉树的另外一种存储方式----“链式二叉树”的学习,主要用到的就是“递归思想”!! 前情回顾: 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点

    2024年01月20日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包