【技术积累】数据结构中的二叉树【一】
什么是二叉树
二叉树是一种树形数据结构，由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，每个节点的左子节点小于该节点的值，在该节点的右侧的子节点大于该节点的值。
二叉树的特点是易于搜索、插入和删除操作。
- 在搜索时，从根节点开始，如果被查找值等于当前节点的值，则搜索结束。
- 如果当前节点的值大于被查找值，则继续搜索左子节点；
- 如果当前节点的值小于被查找值，则继续搜索右子节点。
- 插入和删除节点的操作也类似。
二叉树可分为满二叉树、完全二叉树、平衡二叉树、二叉搜索树等多种类型，不同类型的二叉树有不同的特点和应用场景。
- 满二叉树是每个节点都有两个子节点的二叉树
- 完全二叉树则是除了最后一层节点之外，每一层节点都是满的，最后一层节点从左往右排列。
- 平衡二叉树是指左右子树高度差不超过1的二叉树。
- 二叉搜索树是按照特定规则构建的二叉树，每个节点的左子节点小于该节点的值，在该节点的右侧的子节点大于该节点的值。
二叉树在计算机科学领域中有广泛的应用，例如在搜索算法、编译器、数据库、操作系统等领域。
二叉树的高度，深度，宽度，平衡是什么
1. 二叉树的高度：
二叉树的高度是指从根节点到最深节点的距离，即根节点到最远叶子节点的最短路径。一般使用递归算法来计算二叉树的高度，即树的高度等于左子树高度和右子树高度中的较大值加一。
例如，对于下图所示的二叉树，其高度为4：
A
/ \
B C
/ \ \
D E F
\
G
2. 二叉树的深度：
二叉树的深度是指从根节点到某个节点的距离，即从根节点到该节点的路径上经过的节点数。如果该节点是根节点，则深度为0，否则深度等于其父节点的深度加一。
例如，对于上图中的节点B，其深度为1，节点G的深度为3。
3.二叉树的宽度：
二叉树的宽度指的是二叉树某一层中最多节点的个数。为了计算树的宽度，需要使用BFS（广度优先搜索）算法，从根节点开始逐层遍历二叉树，记录每一层中节点的个数（即该层宽度），然后取所有层宽度的最大值即可。
例如，对于下面这棵二叉树：
A
/ \
B C
/ \ \
D E F
如果从根节点开始遍历二叉树，每一层中节点的个数为：
* 第1层：1个节点
* 第2层：2个节点
* 第3层：3个节点
因此，这棵二叉树的宽度是3。
需要注意的是，如果二叉树的某一层节点数目很少，那么这一层的宽度可能会影响树的整体宽度。在实际应用中，通常会根据具体场景选择不同的度量标准，如节点数、边数、占用的存储空间等。
4. 平衡二叉树：
平衡二叉树是指一棵二叉树，其中任意节点的左右子树的深度差不超过1。在平衡二叉树中，所有节点的左右子树深度差别不大，能够保证树在查询、插入和删除操作时，均能保持较高的性能表现。
例如，下图所示的二叉树就是一棵平衡二叉树：
A
/ \
B C
/ \ / \
D E F G
左右子树的深度差不超过1，左子树深度为2，右子树深度为2，因此它是一棵平衡二叉树。
二叉树的节点数和高度与叶子节点数的关系是什么？
二叉树的节点数与高度的关系可以表示为：如果二叉树的高度为h，则节点总数为2^(h+1) - 1
叶子节点数与高度的关系可以表示为：如果二叉树的高度为h，则叶子节点总数最多为2^h，最少为2^(h-1)。
因此，叶子节点数的范围是 [2^(h-1), 2^h]，并且二叉树的叶子节点数和节点总数之间的关系是近似线性的。
二叉树前序遍历
1. 概念
前序遍历是二叉树遍历的一种方法，也叫做先根遍历。在前序遍历中，首先访问根节点，然后依次遍历其左子树和右子树。具体来说，在前序遍历中，每个节点的访问顺序为：根节点 → 左子树 → 右子树。
2. 步骤
前序遍历的步骤如下：
(1) 访问二叉树的根节点。
(2) 递归遍历左子树，直到左子树为空。
(3) 递归遍历右子树，直到右子树为空。
3. 伪代码
前序遍历的伪代码如下：
function preorderTraversal(root) {
if (root == null) {
return;
}
visit(root); // 访问根节点
preorderTraversal(root.left); // 遍历左子树
preorderTraversal(root.right); // 遍历右子树
}二叉树中序遍历
1. 概念
中序遍历是二叉树遍历的一种方法。在中序遍历中，二叉树的节点按照以下顺序依次遍历：左子树 → 根节点 → 右子树。
2. 步骤
中序遍历的步骤如下：
(1) 递归遍历左子树，直到左子树为空。
(2) 访问二叉树的根节点。
(3) 递归遍历右子树，直到右子树为空。
3. 伪代码
中序遍历的伪代码如下：
function inorderTraversal(root) {
if (root == null) {
return;
}
inorderTraversal(root.left); // 遍历左子树
visit(root); // 访问根节点
inorderTraversal(root.right); // 遍历右子树
}二叉树后续遍历
1. 概念
后序遍历是二叉树遍历的一种方法。在后序遍历中，二叉树的节点按照以下顺序依次遍历：左子树 → 右子树 → 根节点。
2. 步骤
后序遍历的步骤如下：
(1) 递归遍历左子树，直到左子树为空。
(2) 递归遍历右子树，直到右子树为空。
(3) 访问二叉树的根节点。
3. 伪代码
后序遍历的伪代码如下：
function postorderTraversal(root) {
if (root == null) {
return;
}
postorderTraversal(root.left); // 遍历左子树
postorderTraversal(root.right); // 遍历右子树
visit(root); // 访问根节点
}二叉树查找操作复杂度
二叉搜索树中查找某个元素的步骤如下：
1. 从二叉搜索树的根节点开始遍历。
2. 如果当前节点为空，则返回null；如果当前节点的值等于目标值，则返回当前节点。
3. 如果当前节点的值大于目标值，则以当前节点的左子树为目标继续查找；如果当前节点的值小于目标值，则以当前节点的右子树为目标继续查找。
4. 重复执行第2和第3步，直到找到目标节点或者遍历至叶子节点为止。
伪代码如下所示：
function search(root, target):
if (root == null) return null // 如果根节点为空，则直接返回null
if (root.value == target) return root // 如果根节点的值等于目标值，则返回根节点
if (root.value > target) // 如果根节点的值大于目标值，则在左子树中查找
return search(root.left, target)
else // 如果根节点的值小于目标值，则在右子树中查找
return search(root.right, target)二叉搜索树中查找某个元素的时间复杂度是O(log N)，其中N为二叉搜索树中节点的数量。这是因为每次查找都会将搜索区域缩小一半，因此查找的次数最多是二叉树深度的两倍，而二叉树深度是log N级别的。
二叉树插入操作
1. 概念
二叉搜索树是一种特殊的二叉树，它满足以下性质：对于每个节点，它的左子树的所有节点的值小于该节点的值，它的右子树的所有节点的值大于该节点的值。
插入操作是指向二叉搜索树中添加新节点的过程，使得二叉搜索树仍然保持其有序性。
2. 步骤
二叉搜索树的插入操作步骤如下：
(1) 从根节点开始查找，比较当前节点的值和待插入节点的值。
(2) 如果当前节点为空，则将待插入节点插入到该位置，完成插入操作。
(3) 如果待插入节点的值小于当前节点的值，则在左子树中继续查找。
(4) 如果待插入节点的值大于当前节点的值，则在右子树中继续查找。
(5) 对查找到的节点重复上面的操作，直到找到合适的位置将待插入节点插入到树中。
3. 伪代码
二叉搜索树的插入操作的伪代码如下：
function insert(root, val) {
if (root == null) {
root = new TreeNode(val);
return root;
}
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
return root;
}二叉树的删除操作
1. 概念
二叉搜索树的删除操作是指从二叉搜索树中删除一个节点的过程，同时保证删除后的二叉搜索树仍然满足其有序性质。
2. 步骤
二叉搜索树的删除操作步骤如下：
(1) 如果待删除节点为叶子节点，则直接删除该节点。
(2) 如果待删除节点只有一个子节点，则将该子节点替换到待删除节点的位置。
(3) 如果待删除节点有两个子节点，则先找到右子树的最小值节点，使用该节点替换待删除节点，并递归删除右子树中的最小值节点。
3. 伪代码
二叉搜索树的删除操作的伪代码如下：
function deleteNode(root, key) {
if (root === null) {
return null;
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left === null && root.right === null) {
root = null;
} else if (root.left === null) {
root = root.right;
} else if (root.right === null) {
root = root.left;
} else {
let minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
}
return root;
}
function findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}二叉树的遍历可以用来做什么
1. 二叉树的中序遍历可以用来做什么？
二叉树的中序遍历方法是先访问左子树，再访问根节点，最后访问右子树；因此，中序遍历可以帮助我们实现以下操作：
（1）从小到大遍历二叉搜索树：因为按照中序遍历的顺序，所有节点的值都会按从小到大的顺序输出，所以可以用中序遍历将二叉搜索树中的节点从小到大遍历。
（2）创建二叉搜索树：可以通过将节点按照中序遍历的顺序依次插入二叉搜索树来创建一颗新的二叉搜索树。
（3）查找二叉搜索树中的节点：通过进行中序遍历，可以找到指定值的节点。
2. 二叉树的后序遍历可以用来做什么？
二叉树的后序遍历方法是先访问左子树，再访问右子树，最后访问根节点；因此，后序遍历可以帮助我们实现以下操作：
（1）计算二叉树表达式：可以通过后序遍历以及栈的数据结构来计算二叉树表达式。
（2）释放二叉树节点：通过后序遍历的方式释放二叉树的每一个节点。
（3）构建二叉树的镜像：通过后序遍历的方式，可以先构建出原二叉树的镜像的右子树，再构建出镜像的左子树，最后创建根节点，获得二叉树的镜像树。
3. 二叉树的前序遍历可以用来做什么？
二叉树的前序遍历方法是先访问根节点，再访问左子树，最后访问右子树；因此，前序遍历可以帮助我们实现以下操作：
（1）序列化二叉树：可以按照前序遍历的顺序将二叉树转换为字符串，从而进行序列化操作。
（2）还原二叉树：通过前序遍历和中序遍历的结果，可以还原出原二叉树的结构。
（3）构建二叉搜索树：可以通过前序遍历的顺序依次插入节点来构建二叉搜索树。