二叉树入门必看二叉树基础

目录一、什么是二叉树二、概念2.1、核心术语2.2、核心公式2.2.1通用二叉树公式2.2.2完全二叉树专用公式2.2.3满二叉树公式2.3、性质总结2.3.1普通二叉树性质2.3.2完全二叉树性质2.3.3满二叉树性质三、二叉树的存储介绍四、总结一、什么是二叉树树是一种非线性结构由 n 个有限的结点组成一个有层次关系的集合二叉树是树的一种特殊形式其结构像一棵倒挂的树 —— 根节点在最顶层叶子节点在最下层且每个节点最多有两个子节点左、右子树。二、概念在二叉树当中子树有严格的左右之分称为左树和右树左孩子和右孩子。2.1、核心术语先来看一张深度为3的二叉树节点树上的一个元素包含数据和指向子节点的指针根节点最顶层的节点只有一个没有父节点父节点 / 子节点上层节点与下层节点的关系叶子节点没有子节点的节点深度层数/高度根节点在第 1 层也有从 0 开始算的往下依次递增2.2、核心公式2.2.1通用二叉树公式第 i 层最多有多少节点2^(i-1)i 从 1 开始深度为 k 的二叉树最多有多少节点2^k-1满二叉树时取到最大值叶子节点数 度为 2 的节点数n0​n2​1n0​叶子节点度为 0n2​有两个孩子的节点度为 2总节点数nn0​n1​n2​n1​只有一个孩子的节点度为 1除此之外还有两种特殊的二叉树分别是完全二叉树和满二叉树这其中满二叉树其实又是一种特殊的完全二叉树完全二叉树1.除了最后一层上面所有层都满2.最后一层的节点靠左排满右边可以空3.中间不能跳着空节点而满二叉树顾名思义就是一棵全部满的树1.每一层的节点都满了2.所有叶子都在最下面一层3.没有任何一个节点缺孩子4.深度为 k总结点数 2^k-1下面放两张图片展示一下两种树一句话区别1.满二叉树完美无缺2.完全二叉树只允许最后一层右边缺2.2.2完全二叉树专用公式已知总节点 n求深度 kk⌊log2​n⌋1父节点与子节点下标下标1开始节点 i 的左孩子2i、节点 i 的右孩子2i1、节点 i 的父节点⌊i/2⌋下标0开始节点 i 的左孩子2i1、节点 i 的右孩子2i2、节点 i 的父节点⌊i-1/2⌋4.最后一个非叶子节点下标1开始⌊n/2⌋0开始⌊n/2⌋ − 12.2.3满二叉树公式1.深度 k2.总节点2^k-13.叶子节点2^(k-1)4.没有度为 1 的节点n1​02.3、性质总结2.3.1普通二叉树性质二叉树第 i 层上最多有 2^(i-1)个节点。层数越往下最多能存在的节点数量成倍增加。深度为 k 的二叉树所有层都满的情况下总节点数最多能达到 2^k−1 个。叶子节点数 n0​ 与度为 2 的节点数 n2​ 满足固定关系n0​n2​1。简单理解叶子节点永远比有两个孩子的节点多一个。二叉树的总节点数由三类节点共同组成总节点数 nn0​n1​n2​。一棵非空二叉树如果统计所有节点的度数之和结果一定等于总节点数减 1。2.3.2完全二叉树性质除最后一层外上面每一层的节点数量都达到最大值结构非常规整。最后一层的节点只允许在右侧空缺并且必须靠左连续排列中间不能有空位。叶子节点只会出现在最下面一层或倒数第二层不会出现在更上层。整棵树中度为 1 的节点最多只会出现一个并且这个节点一定只有左孩子。相同节点数量下完全二叉树的高度是所有二叉树里最小的。非常适合用数组顺序存储空间利用率高不会出现大量空位浪费。已知总节点数可以直接算出这棵树的深度不需要遍历。2.3.3满二叉树性质每一层的节点数量都达到最大值是最 “完美” 的二叉树形态。所有叶子节点都集中在最底层其他层没有任何叶子。不存在只有一个孩子的节点所有非叶子节点都有两个孩子。深度固定时满二叉树的总节点数、叶子节点数都是确定且最大的。满二叉树是一种特殊的完全二叉树但完全二叉树不一定是满二叉树。三、二叉树的存储介绍二叉树有两种存储方法一个是孩子表示法另一个是孩子双亲表示法这两种方法的区别在于孩子表示法只存了数据域和左右孩子的引用而孩子双亲表示法在这个基础上还加上了当前节点的父节点下面用代码演示// 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 }// 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的父节点 }下面展示一下使用// 孩子表示法 实例 Node root new Node (); root.val 1; // 根节点数据 root.left new Node (); // 创建左孩子 root.left.val 2; root.right new Node (); // 创建右孩子 root.right.val 3;四、总结本文主要围绕二叉树基础知识点展开从最直观的 “倒挂的树” 入手讲解了二叉树的核心概念、关键术语明确了二叉树子树有严格左右之分的核心特点。我们重点介绍了两种特殊的二叉树 —— 完全二叉树和满二叉树理清了二者的区别与关联满二叉树是特殊的完全二叉树并用通俗的语言和公式总结了普通二叉树、完全二叉树、满二叉树的核心公式与性质方便大家理解和记忆。此外还简单介绍了二叉树的两种常用存储方式孩子表示法和孩子双亲表示法通过简单的代码演示让大家直观了解两种存储方式的差异 —— 核心区别在于是否存储当前节点的父节点引用。二叉树是数据结构的基础也是后续学习更复杂树形结构如二叉搜索树、红黑树的前提掌握本文中的术语、公式和性质就能轻松入门二叉树为后续的学习和刷题打下坚实的基础。下一期我将会讲解二叉树的基本操作先声明将会使用孩子表示法