数据结构与算法 - 系列文章的索引

💘 数据结构01 - 数据结构的基本概念
💘 数据结构02 - 顺序表
💘 数据结构03 - 链表
💘 数据结构04 - 栈
💘 数据结构05 - 队列
💘 数据结构06 - 二叉树基本概念

👉 我是喜欢佳美宝贝，喜欢编程，喜欢动漫，喜欢健身的吴小哲同学 👉 👉 欢迎您阅读我的博客 👉 👉 您的评论点赞收藏是对我创作最大的鼓励和帮助~ 👉

文章目录

• 数据结构与算法 - 系列文章的索引
• 前言
• 1 二叉树的概念
• • 1.1 基本概念
  • 1.2 特殊的二叉树
  • • 1.2.1 满二叉树
    • 1.2.2 完全二叉树
• 2 二叉树的存储结构
• • 2.1 二叉树的顺序存储
  • 2.2 二叉树的链式存储
• // 后记

前言

💘 Lesson06 主要讲解二叉树的一些基本概念
💘 本章属于过渡章节，为下两篇的顺序存储实现以及链式存储实现做铺垫

1 二叉树的概念

1.1 基本概念

🏃 二叉树是一种特殊的树形结构
🏃 其特点是每个结点最多只有两颗子树，并且子树有左右之分，不能颠倒

💘 结构图如下：

🏃 根据跟结点的状态，可以将二叉树分为以下五种状态：

1.2 特殊的二叉树

1.2.1 满二叉树

🏃 高度是 h，且含有 2^h-1 个结点的二叉树
🏃 其实就是每一层的结点数都是满的二叉树

1.2.2 完全二叉树

🏃 完全二叉树是由满二叉树引申出来的，其特点是，树中的每一个结点都和其高度相等的满二叉树的结点一一对应

2 二叉树的存储结构

2.1 二叉树的顺序存储

🏃 顺序存储就是用一组连续的存储单元依次自上而下、自左向右地存储完全二叉树上的每一个结点

🏃 从父节点的下标 i ，我们可以迅速访问到左孩子: 2×i+1，右孩子: 2×i+2
🏃 从孩子结点的下标 i ，我们可以迅速访问到父亲结点: （ i - 1 )% 2

🏃 当不是完全二叉树时，就将空出来的结点所对应的存储单元也空出来即可

🏃 由上面两个图对比可知，完全二叉树非常适合顺序存储
🏃 因为结点能和数组一一对应，并且没有空间的浪费
🏃 但是非完全二叉树的顺序存储存在空间的浪费，如果结点非常少，浪费的就更严重

2.2 二叉树的链式存储

🏃 链式存储就是用链表来存储二叉树
🏃 通常的方法就是，链表的每一个结点由三个域构成，分别是：指向左孩子的指针，指向右孩子的指针，存储结点信息的数据域。

🏃 链式存储的优点在于找左右孩子非常方便
🏃并且有二叉树有多少个结点，对应的存储结构中就有多少个节点，没有空间的浪费
🏃 但是，如果想从孩子结点去找双亲，就非常麻烦

💘 以上就是二叉树的基本概念，文章图片里的细节很多，希望大家能够认真观看

// 后记

🏃 以后每周会更新两到三篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。