ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据结构与算法 | 二叉树(Binary Tree) [打印本页]

作者: 八卦阵 时间: 2023-11-14 11:27
标题: 数据结构与算法 | 二叉树(Binary Tree)
二叉树(Binary Tree)

二叉树（Binary Tree）是一种树形数据结构，由节点构成，每个节点最多有两个子节点：一个左子节点和一个右子节点。

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}

复制代码

基本概念

"二叉树"（Binary Tree）这个名称的由来是因为二叉树的每个节点最多有两个子节点，一个左子节点和一个右子节点。其中，“二叉”指的是两个，因此“二叉树”表示每个节点最多可以分支成两个子节点。基本定义：

每个节点包含一个值（或数据），另外最多有两个子节点。
左子节点和右子节点的顺序是固定的，左边的子节点是左子节点，右边的子节点是右子节点。
一个节点可以没有子节点（叶节点），也可以有一个子节点或两个子节点（内部节点）。

相关基本概念：

根节点（Root）：二叉树的顶部节点称为根节点，是树的起始点。
节点（Node）：二叉树的基本构建单元。每个节点包含一个值（或数据）以及指向左子节点和右子节点的指针。
父节点（Parent Node）：一个节点的直接上级节点，如果存在的话。例如，一个节点的左子节点的父节点是该节点本身。
叶节点（Leaf Node）： 没有子节点的节点称为叶节点，即左子节点和右子节点都为空。
子树（Subtree）：以某个节点为根的树，它包括该节点及其所有后代节点。
高度（Height）：从某个节点到其最远叶节点的最长路径上的边数，也称为节点的层数。叶节点的高度为0。

在二叉树基本定义上，加上一些规则，可以衍生出更多种类的二叉树。比如：
二叉搜索树（Binary Search Tree，BST）：一种特殊的二叉树，满足以下性质：对于树中的每个节点，其左子树中的值都小于该节点的值，而其右子树中的值都大于该节点的值。BST通常用于实现有序数据集合。
完全二叉树（Complete Binary Tree）：一个二叉树，其所有层次（深度）除了最后一层外，都是完全填充的，且最后一层的节点从左到右填充，没有空隙。
平衡二叉树（Balanced Binary Tree）：一种高度平衡的二叉树，其中每个节点的两棵子树的高度差不超过1。平衡二叉树通常用于提高查找、插入和删除操作的性能。
预备基础算法 —— 递归（Recursion）

下一部分要写的是二叉树基本遍历代码实现其实可以有多种，思量后用递归实现应该是初接触者比较简洁好理解的方式。为此，在写二叉树下一部分内容之前简单写下基础递归算法，以保证本系列文章承前启后。
递归(Recursion),在数学与计算机科学中对其描述的说法有很多，比如：

指在函数的定义中使用函数自身的方法；
指一种通过重复将问题分解为同类的子问题而解决问题的方法；
（PS：这里同类子问题对于于上一种说法就是函数自身）
指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
（PS：这里描述的基本情况对应于第一种说法中的函数自身了）

当然本文非学术著作"哪种描述比较合适"在此不多做分析，从编码实践的角度第一种说法更为地气一点。
“将问题分解为同类的子问题” 这一点是用递归的方式来解题的关键，这里用个简单的累加和的例子:

设计一个函数，输入参数为 n ，返回 1+2+...n 的和。

public int sum(int n){
int result = 0;
for (int i = 1; i <= n ; i++) {
result = result + i;
}
return result;
}

复制代码

可以看到递归的代码实现上是不是非常简洁。大部分初学者思考上比较习惯于递推，如果第一次接触递归角度思考会有些不适应（或者无法独立分析出来递归）也是正常。当慢慢熟悉后，会发现用递归的思路解决某些算法问题往往会非常简单（在本篇接下来的内容中就能发现这点）。
在初学递归过度到熟悉递归这个阶段，笔者建议可以考虑把一些用递推已经解决了的问题用递归的思路尝试解决，习惯递归思路后会打开一片新世界。
基本遍历（Traversal）

二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。在二叉树中，有三种常见的遍历方式，它们分别是前序遍历、中序遍历和后序遍历。
先序遍历（Preorder Traversal）

从根节点开始，首先访问根节点，然后按照前序遍历的方式依次访问左子树和右子树。前序遍历通常用于复制一棵树或计算表达式的值。
访问顺序：根节点 -> 左子树 -> 右子树
Leetcode 144. 二叉树的前序遍历【简单】

给你二叉树的根节点 root ，返回它节点值的前序遍历。

中序遍历（Inorder Traversal）

从根节点开始，首先按照中序遍历的方式访问左子树，然后访问根节点，最后访问右子树。中序遍历通常用于访问二叉搜索树中的节点，以升序或降序访问节点值。
访问顺序：左子树 -> 根节点 -> 右子树
Leetcode 94. 二叉树的中遍历【简单】

给定一个二叉树的根节点 root ，返回它的中序遍历。

针对后序遍历（Postorder Traversal）从根节点开始，首先按照后序遍历的方式访问左子树，然后访问右子树，最后访问根节点。后序遍历通常用于释放二叉树的内存，或计算表达式的值。访问顺序：左子树 -> 右子树 -> 根节点，在此不过多描述相信一定能够完成编码。
反向构建

Leetcode 105. 从前序与中序遍历序列构造二叉树【中等】

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

综合应用

本系列文章中已经介绍了链表、递归、二叉树，解决算法问题往往会需要综合应用。不妨来看下下面这个问题：
Leetcode 114. 二叉树展开为链表【中等】

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

总结下

介绍了二叉树的的一些基本概念包括：根节点、叶子节点、高度等等；
介绍了基础算法递归的思想：“重复将问题分解为同类的子问题而解决问题的方法”；
介绍了基本的二叉树遍历和反向构建的相关思路；
结合本系列先前文章内容，解决综合链表、递归、二叉树的问题，灵活处理使用数据结构的特征是关键。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)