C语言 超详细总结讲解二叉树的概念与使用

目录
  • 1.二叉树的概念及结构
  • 2.二叉树链式结构的实现

1.二叉树的概念及结构

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

②二叉树的特点：

  • 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。（度最多为2）
  • 二叉树的子树有左右之分，其子树的次序不能颠倒。

③现实中的二叉树：

当一名普通的人看到这样一颗树，可能会想：好标准的一棵树

当一个程序猿看到这样一棵树，可能会想：好像数据结构中的二叉树，并且还是颗满二叉树

④数据结构中的二叉树：

注：二叉树最多有两个度

⑤特殊的二叉树：

  • 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉 树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
  • 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对 于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉 树。

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

⑦二叉树的性质：

  • 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
  • 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
  • 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2 +1
  • 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log₂n+1

⑧练习题

2.二叉树链式结构的实现

①二叉树链式结构的遍历 ：

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访 问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行 其它运算之基础。

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

  • 前序（先根）：先访问根节点，然后访问左子树，最后访问右子树
  • 中序（中根）：先访问左节点，然后访问根节点，最后访问右子树
  • 后序（后根）：先访问左节点，然后访问右子树，最后访问根节点

先定一个结构体类型：

typedef char BTDataType;
typedef struct BinarytreeNode
{
	BTDataType data;
	struct BinarytreeNode* left;
	struct BinarytreeNode* right;
}BTNode;

前序：

void Preamble(BTNode* p)//前序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", p->data);
	Preamble(p->left);
	Preamble(p->right);
}

中序：

void Morder(BTNode* p)//中序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Morder(p->left);
	printf("%c ", p->data);
	Morder(p->right);
}

后序：

void Porder(BTNode* p)//后序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Porder(p->left);
	Porder(p->right);
	printf("%c ", p->data);
}

求二叉树结点的个数：

int treeSize(BTNode* p)//结点个数
{
	return p == NULL ? 0 : treeSize(p->left) + treeSize(p->right)+1;
}

求叶子结点的个数：

int treeLeafSize(BTNode* p)//叶子结点个数
{
	if (p == NULL)
	{
		return 0;
	}
	if (p->left == NULL&&p->right == NULL)
	{
		return 1;
	}

	return treeLeafSize(p->left) + treeLeafSize(p->right);
}

到此这篇关于C语言 超详细总结讲解二叉树的概念与使用的文章就介绍到这了,更多相关C语言 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,￥不能直接得到节点在遍历中的前驱和后继￥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言 数据结构平衡二叉树实例详解

    C语言 数据结构平衡二叉树实例详解

    数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

  • C语言 超详细总结讲解二叉树的概念与使用

    C语言 超详细总结讲解二叉树的概念与使用

    目录 1.二叉树的概念及结构 2.二叉树链式结构的实现 1.二叉树的概念及结构 ①概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成. ②二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点.(度最多为2) 二叉树的子树有左右之分,其子树的次序不能颠倒. ③现实中的二叉树: 当一名普通的人看到这样一颗树,可能会想:好标准的一棵树 当一个程序猿看到这样一棵树,可能会想:好像数据结构中的二叉树,并且还是颗满二叉树 ④数据结

  • C语言超详细i讲解双向链表

    C语言超详细i讲解双向链表

    目录 一.双向链表的概念 二.双向链表的实现 三.链表与顺序表的差别 四.链表oj 总结 一.双向链表的概念 1.概念:概念:双向链表是每个结点除后继指针外还有⼀个前驱指针.双向链表也有带头结点结构和不带头结点结构两种,带头结点的双向链表更为常用:另外,双向链表也可以有循环和非循环两种结构,循环结构的双向链表更为常用. 二.双向链表的实现 头文件List.h #pragma once #include<stdio.h> #include<assert.h> #include<

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言超详细讲解排序算法上篇

    C语言超详细讲解排序算法上篇

    目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序 进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序 基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集

  • C语言 超详细讲解链接器

    C语言 超详细讲解链接器

    目录 1 什么是链接器 2 声明与定义 3 命名冲突 3.1 命名冲突 3.2 static修饰符 4 形参.实参.返回值 5 检查外部类型 6 头文件 1 什么是链接器 典型的链接器把由编译器或汇编器生成的若干个目标模块,整合成一个被称为载入模块或可执行文件的实体–该实体能够被操作系统直接执行. 链接器通常把目标模块看成是由一组外部对象组成的.每个外部对象代表着机器内存中的某个部分,并通过一个外部名称来识别.因此,==程序中的每个函数和每个外部变量,如果没有被声明为static,就都是一个外部

  • C语言 超详细讲解库函数

    目录 1 返回整数的getchar函数 2 更新顺序文件 3 缓冲输出与内存分配 4 库函数 练习 1 返回整数的getchar函数 代码: #include<stdio.h> int main() { char c; while((c = getchar())!=EOF)//getchar函数的返回值为整型 putchar(c); return 0; } 上述代码有三种可能: 某些合法的输入字符在被"截断"后使得c的取值与EOF相同,程序将在复制的中途停止. c根本不可能

  • C语言超详细讲解字符串相乘

    C语言超详细讲解字符串相乘

    目录 前言 一. 分析思路 二.使用步骤 1.代码如下 2.memset函数 三.总结 前言 我们已经知道,正常的两位整形数据通过*相乘,C语言中int为4字节,32bit(字节),其机器码第一位为符号位,余下31位表示数字,表示范围:-2^31(-2147483648)~2^31-1(2147483647),但超过了这个范围我们该如何做呢? 提示:将数字以字符串的形式进行操作 一. 分析思路 示例: 我们把每一个数都看成是一个字符串,每一个元素为十进制数字所对应的字 符,由于是后面的元素先进行

  • C语言超详细讲解栈与队列实现实例

    C语言超详细讲解栈与队列实现实例

    目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用

  • C语言超详细讲解轮转数组

    C语言超详细讲解轮转数组

    目录 题目描述 实例 解题思路 1. 先整体逆转 2.逆转子数组[0, k - 1] 3.逆转子数组[k, numsSize - 1] 易错点 代码 题目描述 给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数.OJ链接 实例 1.实例1 输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7

  • C语言超详细讲解数据结构中双向带头循环链表

    C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

随机推荐