数据结构：二叉树详解 c++信息学奥赛基础知识讲解

2024-06-24 09:04
文章标签 二叉树 c++ 讲解 详解 数据结构 基础知识 奥赛 信息学

本文主要是介绍数据结构：二叉树详解 c++信息学奥赛基础知识讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、二叉树的定义

二、二叉树的形态

三、二叉树的性质

四、二叉树的存储

五、二叉树的创建与遍历（递归）

六、二叉树实现

创建二叉树

展示二叉树

1、计算数的高度

2、计算数的叶子数量

3、计算数的宽度

4、层次遍历

5、前序遍历

递归写法

非递归写法

6、中序遍历

递归写法

非递归写法

7、后序遍历

递归写法

非递归写法

8、输出根节点到所有叶子节点的路径(递归)

递归写法

非递归写法

一、二叉树的定义

二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0)，n=0时为空树，n>0时为非空树。对于非空树T TT：

  • 有且仅有一个根结点；
  • 除根结点外的其余结点又可分为两个不相交的子集TL 和TR，分别称为T的左子树和右子树，且TL和TR 本身又都是二叉树。

很明显该定义属于递归定义，所以有关二叉树的操作使用递归往往更容易理解和实现。

从定义也可以看出二叉树与一般树的区别主要是两点，一是每个结点的度最多为2；二是结点的子树有左右之分，不能随意调换，调换后又是一棵新的二叉树。

二、二叉树的形态

五种基本形态

从上面二叉树的递归定义可以看出，二叉树或为空，或为一个根结点加上两棵左右子树，因为两棵左右子树也是二叉树也可以为空，所以二叉树有5种基本形态：


三种特殊形态

三、二叉树的性质

  1. 任意二叉树第 i 层最大结点数为2^{i-1}。 ( i ≥ 1 ) 
  2. 深度为 k 的二叉树最大结点总数为2^{k}-1。 ( k ≥ 1 )
  3. 对于任意二叉树，用n0 , n1 , n2分别表示叶子结点，度为1的结点，度为2的结点的个数，则有关系式n0 = n2 + 1
  4. n个结点完全二叉树深度为⌊log2^{n} ⌋ + 1

四、二叉树的存储

存储的目的是为了取，而取的关键在于如何通过父结点拿到它的左右子结点，不同存储方式围绕的核心也就是这。

顺序存储

使用一组地址连续的存储单元存储，例如数组。为了在存储结构中能得到父子结点之间的映射关系，二叉树中的结点必须按层次遍历的顺序存放。具体是：

  • 对于完全二叉树，只需要自根结点起从上往下、从左往右依次存储。
  • 对于非完全二叉树，首先将它变换为完全二叉树，空缺位置用某个特殊字符代替（比如#），然后仍按完全二叉树的存储方式存储。

假设将一棵二叉树按此方式存储到数组后，左子结点下标=2倍的父结点下标+1，右子节点下标=2倍的父结点下标+2（这里父子结点间的关系是基于根结点从0开始计算的）。若数组某个位置处值为#，代表此处对应的结点为空。

可以看出顺序存储非常适合存储接近完全二叉树类型的二叉树，对于一般二叉树有很大的空间浪费，所以对于一般二叉树，一般用下面这种链式存储。

链式存储

对每个结点，除数据域外再多增加左右两个指针域，分别指向该结点的左孩子和右孩子结点，再用一个头指针指向根结点。对应的存储结构：

五、二叉树的创建与遍历（递归）

二叉树由三个基本单元组成：根结点，左子树，右子树，因此存在6种遍历顺序，若规定先左后右，则只有以下3种：
1.先序遍历
若二叉树为空，则空操作；否则：
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树

2.中序遍历
若二叉树为空，则空操作；否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树

3.后序遍历
若二叉树为空，则空操作；否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点

从上可以看出先中后其实是相对根结点来说。

对于下面这棵二叉树，其遍历顺序：
先序：ABDEHCFIG
中序：DBHEAFICG
后序：DHEBIFGCA

下面是将以下二叉树的顺序存储[A,B,C,D,E,F,G,#,#,H,#,#,I]转换为链式存储的代码，结点不存在用字符#表示，并分别遍历。

六、二叉树实现

我们的二叉树的是以链式结构建立的，下面通过c++实现二叉树的相关操作。链式结构的每个节点都用BT结构体表示，这个结构体的data代表树的该节点存储的数据（此处为了方便使用char作为存储数据，实际使用时，可以使用各种各样的数据类型代表这个data，甚至在BT下挂载多个数据也是没问题的）。*left和*right分别代表指向该节点的左节点和右节点的指针。

#include <iostream>
#include <cstring>
#define N 100
using namespace std;typedef struct node
{char data;struct node *left, *right;
}BT;BT *createbt(char *in, char *pre, int k);	// 根据输入二点中序表达式和前序表达式创建一颗二叉树
void showBt(BT *T);		// 展示一颗二叉树，以A(B, C(D, E))这样加了括号的前序遍历来实现
int height(BT *T);		// 计算树的高度
int leaf(BT *T);	// 计算叶子的数量
int width(BT *T);		// 计算树的宽度
void layer(BT *T);		// 层次遍历
void preorder(BT *T);	// 前序遍历
void inorder(BT *T);	// 中序遍历
void postorder(BT *T);	// 后序遍历	
void getPath(BT *T, BT **path, int top)		// 输出根节点到所有叶子节点的路径(递归)
void getPath(BT *T);	// 输出根节点到所有叶子节点的路径(非递归)

创建二叉树

为了方便，此处使用前序遍历和中序遍历的表达式递归地创建一颗二叉树。

BT *createbt(char *in, char *pre, int k)
{if (k <= 0)return NULL;else{BT *node = new BT;node->data = pre[0];	// 前序表达地第一个元素就是这颗子树地根节点int i;for (i = 0; in[i] != pre[0]; ++ i);		// 根据一个计数器i获取中序表达式中node->data的位置node->left = createbt(in, pre + 1, i);node->right = createbt(in + i + 1, pre + i + 1, k - i - 1);return node;}
}

展示二叉树

展示一棵二叉树。它的顺序和前序遍历是一样的，只是我们给他们加上括号

很显然，它的前序表达式为ABCDE，那么我们的展示函数就在前序表达式的基础上加上括号来代表其层次关系：A(B,C(D,E))。

void showBt(BT *T)
{if (T){cout << T->data << " ";if (T->left || T->right)	// 判断一下当前递归到的节点有没有字节点，如果没有子节点，我们就不需要打上括号了{cout << "(";showBt(T->left);cout << ",";showBt(T->right);cout << ")";}}
}

1、计算数的高度

树的高度可以认为是层数，也就是根节点到叶子节点中路径最长的那条路径包含的节点数量。此后通过递归实现：

int height(BT *T)
{if (!T)return 0;elsereturn max(height(T->left) + 1, height(T->right) + 1);
}

2、计算数的叶子数量

思路和计算树的高度差不多，不过需要额外判断一下叶子节点的情况：

int leaf(BT *T)
{if (!T)		return 0;else if (!T->left && !T->right)	// 当前节点为叶子，那么叶子的数量当然是1return 1;elsereturn leaf(T->left) + leaf(T->right);
}

3、计算数的宽度

树的宽度定义为含有节点为最多节点的那一层所含有的节点数，比如下面这幅图：

上面这幅图中DEFG这层有的节点数量最多，为4个，因此这颗二叉树的宽度为4。

很明显，我们是通过比较层的节点数量来确定宽度，因此我们需要通过层次遍历来获取宽度。不过不同于一般的层次遍历的写法，我们需要统计完一层的节点树，然后直接把这一层的节点全部弹出，然后把它们的子节点入队。

我们记答案为max_wid，每层的节点数为count，很明显count = rear - front，那么我们通过count这个值做count次出队，入队操作就可以把第n层的节点全部弹出，把n+1层的节点全部入队

int width(BT *T)
{BT *q[N], *p;int front, rear;front = rear = 0;q[rear ++] = T;int max_wid = 0;while (front != rear){int count = rear - front;	// 通过队列的front和rear直接得出当前层的节点数量max_wid = max(max_wid, count);	// 更新当前的最大宽度while (count --)	// 根据count将当前层的所有节点弹出，把它们的子节点入队，完成层次遍历的队列更新{p = q[front ++];if (p->left)q[rear ++] = p->left;if (p->right)q[rear ++] = p->right;}}return max_wid;
}

4、层次遍历

层次遍历通过队列是实现，每出队一个元素，就将它的左子节点和右子节点入队（如果有的话）。

void layer(BT *T)
{BT *q[N], *p;int front, rear;front = rear = 0;q[rear ++] = T;while (front != rear){p = q[front ++];	// 队首元素出队cout << p->data << " ";// 将出队的元素的子节点入队if (p->left)q[rear ++] = p->left;if (p->right)q[rear ++] = p->right;}
}

5、前序遍历

递归写法

前序的递归写法非常直观：

void preorder(BT *T)	// 前序遍历 
{if (T){cout << T->data << " ";preorder(T->left);preorder(T->right);}
}

非递归写法

前序遍历的非递归通过栈来实现，要先输出的元素后入栈，要后输出的元素先入栈：

void preorder(BT *T)
{BT *s[N], *p;int top = 0;s[top] = T;while (top >= 0){// 首元素的栈筛比较简单，就是直接输出就完事儿p = s[top --];cout << p->data << " ";// 后续要递归的栈筛入栈if (p->right)s[++ top] = p->right;if (p->left)s[++ top] = p->left;}
}

6、中序遍历

递归写法

void inorder(BT *T)	// 中序遍历 
{if (T){preorder(T->left);cout << T->data << " ";preorder(T->right);}
}

非递归写法

中序遍历的非递归还是通过栈来实现的，只不过与前序遍历相比，我们的根节点不能直接输出，所以我们需要额外的栈筛来保存中间输出的各个子树的根节点，这个节点为p：

void inorder(BT *T)
{BT *s[N], *p = T;int top = -1;while (top >=0 || p){while (p)	// 由于中序遍历需要将所有的左子树输出，所以首先将左子树的栈筛入栈{s[++ top] = p;p = p->left;}p = s[top --];cout << p->data << " ";p = p->right;	// 如果该节点有右节点，则根据中序遍历的规则进入右子树（该节点被当作局部子树的根节点）；如果没有右节点，根据代码结构，打印上一层的节点（该节点被当作局部子树的左节点）}
}

7、后序遍历

递归写法

void postorder(BT *T)	// 后序遍历 
{if (T){preorder(T->left);preorder(T->right);cout << T->data << " ";}
}

非递归写法

后续遍历的非递归写法也是通过栈来实现的，因为此时的各个子树的根节点是在最后才输出的，所以我们需要保存左子树的栈筛和右子树的栈筛。我们还需要一个临时变量来指明当前遍历到的节点的右子节点是否被访问过。

void postorder(BT *T)
{BT *s[N], *p = T, *last;	// last变量用来判断当前访问的节点的右子节点是否被访问过int top = -1;do{while (p)	// 左子树的栈筛全部{s[++ top] = p;p = p->left;}last = NULL;while (top >= 0)	// 遍历打印没有右节点的根节点，或者访问没有访问过的右子树{p = s[top];if (p->right == last){top --;cout << p->data << " ";last = p;}else{p = p->right;break;}}	}while (top >= 0);
}

8、输出根节点到所有叶子节点的路径(递归)

递归写法没什么好说的=_=，还是很简单的。注意在主函数中调用该函数时，需要额外传入一个存储参数的path数组，起始填入的top为-1。

递归写法

void getPath(BT *T, BT **path, int top)
{	if (!T)return;else if (!T->left && !T->right){for (int i = 0; i <= top; ++ i)cout << path[i]->data << " ";cout << T->data << endl;}else{path[++ top] = T;getPath(T->left, path, top);getPath(T->right, path, top);}
}

非递归写法

此处一定记住，只要是涉及到输出路径输出，一定是优先考虑后序遍历，因为后序遍历是左子树->右子树->根节点的顺序，这就使得使用后序遍历访问到一个元素时，栈中剩余元素恰为根节点到该元素的路径，所以我们只要将后序遍历中的cout改成一个判断：若当前元素是叶子，则将栈中元素依次输出。

void getPath(BT *T)
{BT *s[N], *p = T, *last;int top = -1;do{while (p){s[++ top] = p;p = p->left;}last = NULL;while (top >= 0){p = s[top];if (p->right == last){top --;if (!p->left && !p->right)	// 判断当前访问的节点是否为叶子节点，若是，则输出栈内元素{for (int i = 0; i <= top; ++ i)cout << s[i]->data << " ";cout << p->data << endl;}last = p;}else{p = p->right;break;}}}while(top >= 0);
}

这篇关于数据结构：二叉树详解 c++信息学奥赛基础知识讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1089707。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
linux-基础知识3

linux-基础知识3

打包和压缩 zip 安装zip软件包 yum -y install zip unzip 压缩打包命令: zip -q -r -d -u 压缩包文件名 目录和文件名列表 -q:不显示命令执行过程-r:递归处理，打包各级子目录和文件-u:把文件增加/替换到压缩包中-d:从压缩包中删除指定的文件 解压:unzip 压缩包名 打包文件 把压缩包从服务器下载到本地 把压缩包上传到服务器(zip
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
计组基础知识

计组基础知识

操作系统的特征 并发共享虚拟异步 操作系统的功能 1、资源分配，资源回收硬件资源 CPU、内存、硬盘、I/O设备。2、为应⽤程序提供服务操作系统将硬件资源的操作封装起来，提供相对统⼀的接⼝（系统调⽤）供开发者调⽤。3、管理应⽤程序即控制进程的⽣命周期：进程开始时的环境配置和资源分配、进程结束后的资源回收、进程调度等。4、操作系统内核的功能（1）进程调度能⼒： 管理进程、线
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2