代码随想录算法训练营第十一天 | 二叉树基础

2024-01-26 06:12
文章标签 算法 基础 随想录 代码 二叉树 训练营 第十一天

本文主要是介绍代码随想录算法训练营第十一天 | 二叉树基础，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第十一天 | 二叉树基础

文章目录

  • 代码随想录算法训练营第十一天 | 二叉树基础
    • 1 二叉树的理论基础
      • 1.1 二叉树的类型
      • 1.2 二叉树的存储方式
      • 1.3 二叉树的遍历方式
      • 1.4 二叉树的定义
    • 2 二叉树的递归遍历
      • 2.1 前序遍历
      • 2.2 中序遍历
      • 2.3 后序遍历
    • 3 二叉树的迭代遍历
      • 3.1 前序遍历
      • 3.2 中序遍历
      • 3.3 后序遍历
    • 4 二叉树的统一迭代法
      • 4.1 中序遍历
      • 4.2 前序遍历
      • 4.3 后序遍历

1 二叉树的理论基础

二叉树作为408的高频考点，不管是考试还是面试我们都要好好学习一下有关二叉树的相关知识。

1.1 二叉树的类型

（1）普通二叉树

普通二叉树是最基本的二叉树结构，每个节点最多有两个子节点，分别是左子节点和右子节点，它不强制要求每个节点都有子节点，因此可能呈现出不平衡的状态。

（2）满二叉树

满二叉树是一种特殊的二叉树，每一层的节点数都达到了可能的最大值，换句话说，除了叶子节点外，每个节点都有两个子节点。一棵高度为h的满二叉树，含有 2 h − 1 2^h-1 2h−1个节点，可以对满二叉树按层序编号：约定编号从根结点(根结点编号为1)起，自上而下，自左向右。这样每个结点对应一个编号，对于编号为i的结点，若有双亲，则其双亲为i/2」,若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。

在这里插入图片描述

（3）完全二叉树

完全二叉树类似于满二叉树，但最后一层的节点可以不完全填满，并且所有节点都靠左排列，它是堆结构的基础。

完全二叉树其特点如下：

①若i≤Ln/2]，则结点i为分支结点，否则为叶结点。

②叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。

③若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征)。

④按层序编号后，一旦出现某结点（编号为i）为叶结点或只有左孩子，则编号大于i的结点均为叶结点。

⑤若n为奇数，则每个分支结点都有左孩子和右孩子;若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

在这里插入图片描述

（4）二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，它对节点的排列有严格要求：任一节点的左子树只包含比该节点小的值，右子树只包含比该节点大的值，这一特性使得二叉搜索树在查找数据时非常高效。

（5）平衡二叉树（AVL树）

AVL树是一种自平衡的二叉搜索树，它要求任何节点的左右子树的高度差不能超过1，这种严格的平衡要求保证了树的查找效率。

（6）红黑树

红黑树（408考试目前还没有考察过，但估计很快就会考察简单的概念题目）是一种自平衡的二叉搜索树，它通过确保任何一条从根到叶子的路径不会包含两个连续的红色节点来保持平衡，红黑树在计算机科学中广泛应用，特别是在数据结构如map和set中。

1.2 二叉树的存储方式

（1）顺序存储

顺序存储意味着将二叉树的节点数据存放在数组中，对于完全二叉树，这种方法非常高效，数组的索引和树的节点之间有直接的关系：对于索引i的节点，其左子节点的索引是2*i + 1，右子节点的索引是2*i + 2。

在这里插入图片描述

（2）链式存储

在链式存储中，每个节点包含三部分：值、指向左子节点的指针和指向右子节点的指针，这是二叉树最常见的存储方式，因为它能有效地表示树的结构，即使是对于不完全的二叉树。

在这里插入图片描述

1.3 二叉树的遍历方式

（1）前序遍历

前序遍历首先访问根节点，然后递归地进行左子树的前序遍历，接着是右子树的前序遍历。

在这里插入图片描述

（2）中序遍历

中序遍历首先递归地进行左子树的中序遍历，然后访问根节点，最后是右子树的中序遍历，对于二叉搜索树，中序遍历可以按升序访问所有节点。

在这里插入图片描述

（3）后序遍历

后序遍历首先递归地进行左子树的后序遍历，然后是右子树的后序遍历，最后访问根节点。

在这里插入图片描述

（4）层序遍历

层次遍历按照树的层次进行，从根节点开始，然后是第二层，以此类推，通常使用队列来辅助实现这种遍历方式。

在这里插入图片描述

1.4 二叉树的定义

（1）顺序存储定义

  • Python代码定义（在Python中，顺序存储通常使用列表（数组）实现）

    class BinaryTree:def __init__(self, size):self.array = [None] * sizedef insert(self, value, index):if index < len(self.array):self.array[index] = valueelse:print("Index out of range.")bt = BinaryTree(10) # 创建一个大小为10的二叉树
bt.insert(1, 0)     # 在根位置插入1
bt.insert(2, 1)     # 在左子节点位置插入2
bt.insert(3, 2)     # 在右子节点位置插入3

  • C++代码定义（在C++中，顺序存储可以使用数组或标准模板库（STL）中的vector实现）

    #include <vector>
#include <iostream>class BinaryTree {
public:std::vector<int> array;BinaryTree(int size) {array.resize(size, -1); // 初始化为-1，代表空节点}void insert(int value, int index) {if (index < array.size()) {array[index] = value;} else {std::cout << "Index out of range." << std::endl;}}
};int main() {BinaryTree bt(10);bt.insert(1, 0);  // 在根位置插入1bt.insert(2, 1);  // 在左子节点位置插入2bt.insert(3, 2);  // 在右子节点位置插入3return 0;
}

（2）链式存储定义

  • Python代码定义

    class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneclass BinaryTree:def __init__(self, root=None):self.root = rootroot = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
bt = BinaryTree(root)

  • C++代码定义

    #include <iostream>struct TreeNode {int value;TreeNode *left, *right;TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};class BinaryTree {
public:TreeNode *root;BinaryTree() : root(nullptr) {}
};int main() {BinaryTree bt;bt.root = new TreeNode(1);bt.root->left = new TreeNode(2);bt.root->right = new TreeNode(3);return 0;
}

2 二叉树的递归遍历

2.1 前序遍历

（1）Python版本代码

# 前序遍历-递归-LC144_二叉树的前序遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []left = self.preorderTraversal(root.left)right = self.preorderTraversal(root.right)return  [root.val] + left +  right

（2）C++版本代码

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

下面是王道数据结构上面的二叉树前序遍历代码：

在这里插入图片描述

2.2 中序遍历

（1）Python版本代码

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

（2）C++版本代码

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右
}

下面是王道数据结构上面的二叉树中序遍历代码：

在这里插入图片描述

2.3 后序遍历

（1）Python版本代码

# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []left = self.postorderTraversal(root.left)right = self.postorderTraversal(root.right)return left + right + [root.val]

（2）C++版本代码

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 中
}

下面是王道数据结构上面的二叉树后序遍历代码：

在这里插入图片描述

下面是王道数据结构上面树这一章中关于二叉树的递归算法实现的介绍：

下面用带箭头的虚线表示了这三种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回; ,虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问根结点时输出的信息。例如，由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前进行的，则带圆形的字符标在向左递归返回和向右递归调用之间。由此，只要沿虚线从1出发到2结束，将沿途所见的三角形(或圆形或方形)内的字符记下，便得到遍历二叉树的先序(或中序或后序）序列。例如在下图中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为DEBCA。

在这里插入图片描述

3 二叉树的迭代遍历

3.1 前序遍历

在前序遍历中，我们首先访问根节点，然后左节点，最后右节点。使用栈来实现时，我们首先将根节点放入栈中，然后循环直到栈为空，在每次循环中，我们取出栈顶元素，访问它，然后先将其右子节点压入栈（如果有），再将左子节点压入栈（如果有）。

（1）Python版本代码

def preorder_traversal(root):if not root:return []stack, output = [root, ], []while stack:node = stack.pop()  # 弹出栈顶元素if node:output.append(node.value)  # 访问节点if node.right:  # 如果存在右子节点，先压入栈stack.append(node.right)if node.left:  # 如果存在左子节点，后压入栈stack.append(node.left)return output

（2）C++版本代码

vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (!root) return result;stack<TreeNode*> stack;stack.push(root);while (!stack.empty()) {TreeNode* node = stack.top(); stack.pop(); // 弹出栈顶元素if (node) {result.push_back(node->value); // 访问节点if (node->right) stack.push(node->right); // 先将右子节点压入栈if (node->left) stack.push(node->left); // 再将左子节点压入栈}}return result;
}

3.2 中序遍历

在中序遍历中，我们首先访问最左侧节点，然后根节点，最后右节点。使用栈实现时，我们从根节点开始，首先将所有左侧节点压入栈中，然后弹出栈顶元素访问，再处理这个节点的右子树。

（1）Python版本代码

def inorder_traversal(root):stack, output = [], []current = rootwhile current or stack:while current:stack.append(current)  # 将左子节点压入栈current = current.leftcurrent = stack.pop()  # 弹出栈顶元素output.append(current.value)  # 访问节点current = current.right  # 转到右子树return output

（2）C++版本代码

vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> stack;TreeNode* current = root;while (current || !stack.empty()) {while (current) {stack.push(current); // 将左子节点压入栈current = current->left;}current = stack.top(); stack.pop(); // 弹出栈顶元素result.push_back(current->value); // 访问节点current = current->right; // 转到右子树}return result;
}

3.3 后序遍历

后序遍历的顺序是先左节点，然后右节点，最后根节点。其非递归的实现是三种遍历方法中最难的，因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根节点，我们使用栈实现时，我们可以利用前序遍历的顺序，首先访问根节点，然后右节点，最后左节点，并将结果逆序输出。

（1）Python版本代码

def postorder_traversal(root):if not root:return []stack, output = [root, ], []while stack:node = stack.pop()  # 弹出栈顶元素if node:output.append(node.value)  # 访问节点if node.left:  # 如果存在左子节点，先压入栈stack.append(node.left)if node.right:  # 如果存在右子节点，后压入栈stack.append(node.right)return output[::-1]  # 反转输出结果

（2）C++版本代码

vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if (!root) return result;stack<TreeNode*> stack;stack.push(root);while (!stack.empty()) {TreeNode* node = stack.top(); stack.pop(); // 弹出栈顶元素if (node) {result.push_back(node->value); // 访问节点if (node->left) stack.push(node->left); // 先将左子节点压入栈if (node->right) stack.push(node->right); // 再将右子节点压入栈}}reverse(result.begin(), result.end()); // 反转输出结果return result;
}

在这些实现中，我们使用栈来模拟递归过程，栈的特性（后进先出）允许我们以非递归的方式来实现树的深度优先遍历，对于前序和后序遍历，我们都是先处理右子树，以确保左子树先被处理。对于中序遍历，我们首先迭代地将所有左子树压入栈中，然后处理节点，并转向右子树。

4 二叉树的统一迭代法

因为统一风格的迭代法并不好理解，而且在面试中也不好直接写，不如递归法简单，所以在这里我就不做过多的研究，感兴趣的可以去卡哥的代码随想录：二叉树的统一迭代法去看看，这里我就只贴出卡哥的代码。

4.1 中序遍历

中序遍历代码如下：（详细注释）

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.top();    // 重新取出栈中元素st.pop();result.push_back(node->val); // 加入到结果集}}return result;}
};

4.2 前序遍历

迭代法前序遍历代码如下： (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right);  // 右if (node->left) st.push(node->left);    // 左st.push(node);                          // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

4.3 后序遍历

后序遍历代码如下： (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();st.push(node);                          // 中st.push(NULL);if (node->right) st.push(node->right);  // 右if (node->left) st.push(node->left);    // 左} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

这篇关于代码随想录算法训练营第十一天 | 二叉树基础的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/645874。

相关文章

python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中，<trim>元素用于动态地添加SQL语句的一部分，例如SET或W
阅读更多...
使用C#代码计算数学表达式实例

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长，因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
python多进程实现数据共享的示例代码

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架，使用的是
阅读更多...
SpringBoot生成和操作PDF的代码详解

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成，并下载完全基于代码生成，并保存合并P
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置（Maven）application.yml 配置表结构设计demo_st
阅读更多...
SpringCloud集成AlloyDB的示例代码

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么？AlloyDB 的工作原理2.搭建测试环境3.代码工程1.
阅读更多...
Java调用Python代码的几种方法小结

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2