数据结构与算法:二叉树(Binary Tree)
haoteby 2025-09-27 23:20 24 浏览
树（Tree）结构应该算得上是数据结构中非常重要的一种了，
它被广泛应用于数据的底层存储，像集合类Set、Map用到了红黑树、数据库索引使用了平衡树。
今天我们来探索树（Tree）的入门类型：二叉树（Binary Tree）
初识
就像认识人一样，我们先看一下二叉树的"五官"
- 层：从根节点算起，1起始，向下累加
- 节点：图中每一个单位叫做一个节点，最上层的叫做根节点，没有子节点的叫做叶子节点。
- 深度：从根节点算起，0起始，向下累加
- 高度：从底层算起，0起始，向上累加
- 二叉：所谓二叉树，即每个节点下层最多有两个子节点。
在了解了基本概念之后，我们来认识一下不同类型的"二叉树"
满二叉树
通过这个对比应该很好理解，满二叉树，即叶子节点都在最底层，且除叶子节点外，每个节点的子节点都是两个，也就是子节点是满的。
完全二叉树
依然通过对比来感受一下
相比于满二叉树，完全二叉树难理解一些，所以这里举了多个例子对比。
总结一下完全二叉树的特点：
- 除最下层以外，上层是一个满二叉树
- 最下层的叶子节点从右侧向左看起，没有空缺节点
细品一下其实满二叉树属于特殊的完全二叉树。
在了解了基本的二叉树之后，我们来深入探寻一下二叉树的实现方式：
基于链表：链式存储
关于链表回顾：
链表的每个节点分别存有指向左右子节点的指针，这样我们就可以顺着指针找到二叉树的所有数据。
基于数组：顺序存储
数组实现二叉树的思路是：通过计算公式，将二叉树的所有节点转换成数组下标，并按顺序存储。
我们试着摸索一下这个计算公式：
可以看到，我将二叉树做编号对应成了数组的下标，为了方便计算通常从数组下标为1的位置开始存放。
如果我们的当前节点在根节点1，那么左侧的子节点就是：2 * 1 = 2
右侧子节点就是：2 * 1 + 1 = 3
由此可以推出计算公式：
- 当前节点下标：i
- 左侧子节点下标：2 * i
- 右侧子节点下标：2 * i + 1
这样一来就轻松的实现了数组方式存储二叉树。
相比于链式存储，以数组方式存储二叉树更为节省内存，因为链式存储需要额外开辟内存来存放指向左右子节点的指针。
回看完全二叉树
我将顺序存储的图片再贴一次：
你应该不难发现这是一个完全二叉树，在使用完全二叉树作顺序存储时，数组只浪费了一块内存，也就是下标0。
如果是非完全二叉树呢？
显而易见，非完全二叉树无法更好的利用数组的空间，会造成空间浪费。
所以完全二叉树最适合使用顺序存储。
今天我们了解了不同类型的二叉树以及二叉树的实现方式，下一期我们来继续探索二叉树的增删改查。
相关推荐
- 如何为MySQL服务器和客户机启用SSL?
-
用户想要与MySQL服务器建立一条安全连接时，常常依赖VPN隧道或SSH隧道。不过，获得MySQL连接的另一个办法是，启用MySQL服务器上的SSL封装器(SSLwrapper)。这每一种方法各有其...
- k8s 证书问题排查_k8s dashboard 证书
-
从去年开始一些老项目上陆陆续续出现一些列的证书问题，（证书原理这里就不说了，官方文档一堆）多数刚开始的表现就是节点的kubelet服务起不来，节点状态NotReady表现日志如下failed...
- 企业级网络互通方案:云端OpenVPN+爱快路由器+Win11互联实战
-
企业级网络互通方案：OpenVPN搭建公有云+爱快路由器+Win11三地互联实战指南「安全高效」三地局域网秒变局域网实施环境说明...
- OpenV** Server/Client配置文件详解
-
Server配置详解...
- 接口基础认知:关键信息与合规前提
-
1.核心技术参数（必记）...
- S交换机通过SSH登录设备配置示例(RADIUS认证+本地认证独立)
-
说明：●本示例只介绍设备的认证相关配置，请同时确保已在RADIUS服务器上做了相关配置，如设备地址、共享密钥、创建用户等配置。●通过不同的管理域来实现RADIUS认证与本地认证两种方式同时使用，两...
- SSL证书如何去除私钥密码保护_ssl证书怎么取消
-
有时候我们在生成证书的时候可以加入了密码保护。然后申请到证书安装到了web服务器。但是这样可能会带来麻烦。每次重启apache或者nginx的时候，都需要输入密码。那么SSL证书如何去除私钥密码保护。...
- SSL证书基础知识与自签名证书生成指南
-
一、证书文件类型解析...
- S交换机通过SSH登录设备配置示例(RADIUS认证)
-
说明：本示例只介绍设备的认证相关配置，请同时确保已在RADIUS服务器上做了相关配置，如设备地址、共享密钥、创建用户等配置。假设已在RADIUS服务器上创建了用户名yc123，密码test#123。对...
- HTTPS是什么?加密原理和证书。SSL/TLS握手过程
-
秘钥的产生过程非对称加密...
- HTTPS TLS握手流程_进行tls握手
-
1.客户端向服务器发送`ClientHello`消息，包括支持的TLS版本、加密套件、随机数等信息。2.服务器收到`ClientHello`消息后，解析其中的信息，并根据配置选择一个加密套件。3....
- Spring Boot 单点登录(SSO)实现_spring boot 单点登录jwt
-
SpringBoot单点登录（SSO）实现全指南单点登录（SingleSign-On,SSO）是一种身份验证机制，允许用户使用一组凭证登录多个相关但独立的系统。在微服务架构和企业级系统中，SS...
- 源码分享:在pdf上加盖电子签章_pdf如何加盖电子公章
-
在pdf上加盖电子签章，并不是只是加个印章图片，。而是要使用一对密钥中的私钥对文件进行签字。为啥要用私钥呢？很简单，因为公钥是公开的，其他人才可以用公钥为你证明，这个文件是你签的。这就是我们常说的：私...
- 微信支付商户API证书到期 怎么更换
-
微信支付商户API证书到期更换是一个非常重要的操作，需要仔细按照流程进行。如果证书过期，所有通过API的支付、退款等操作都会失败，将直接影响您的业务。请按照以下详细步骤进行操作：重要前提：分清...