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

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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2