【数据结构】二叉爆炸

2024-04-14 20:36
文章标签 数据结构 二叉 爆炸

本文主要是介绍【数据结构】二叉爆炸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【数据结构】二叉爆炸

按照惯例整点抽象的，贴上这篇博客的名字由来：

image-20240413233154850

言归正传，本篇博客介绍二叉树的构造方式、前中后序遍历、层序遍历以及代码随想录中二叉树章节的相关题目：

代码随想录 (programmercarl.com)

一、啥是二叉树

1.二叉树是什么？

百度百科上的解释是这样的：

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

太长不看，简单来说，二叉树就是这个：

image-20240414004106540

单亲爸爸带俩娃（划掉），一个根节点带着俩孩子。左边的孩子是“左子树”，右边的孩子是“右子树”。

下面是一些二叉树相关的定义，下面关于二叉树的算法题中可能会用到：

①节点：包含一个数据元素及若干指向子树分支的信息。

②节点的度：一个节点拥有子树的数目称为节点的度。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。

⑤树的度：树中所有节点的度的最大值。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。

⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。

⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。

⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

2.二叉树有啥用？

  1. 数据存储和检索：二叉搜索树（BST）是一种常见的数据结构，用于存储和检索数据。在BST中，每个节点的左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点，这使得查找、插入和删除操作的平均时间复杂度为O(log n)，其中n是树中节点的数量。
  2. 数据库索引：许多数据库系统使用二叉树或其变种（如B树、B+树）来加速数据检索。这些树结构允许在大量数据中快速找到所需的记录。
  3. 文件系统：许多操作系统使用树状结构来组织文件和目录。文件系统中的每个目录都可以视为一个节点，其中包含文件和其他子目录。
  4. 图形用户界面（GUI）：许多GUI工具包使用树形结构来组织用户界面元素。例如，菜单和文件资源管理器通常使用树形结构来表示层级结构。

3.特殊的二叉树！

满二叉树

所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树。

这张图上的树就是一棵满二叉树。

image-20240414004106540

完全二叉树

在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树。即最后一层所有节点靠左的二叉树。

如图所示：

image-20240414005958254

二、咋遍历二叉树？

1. 深度优先搜索（前，中，后序遍历）

从根节点开始，沿着树的深度尽可能远的搜索树的分支。当达到树的最深处时，再回溯到上一级节点继续搜索，直到遍历完整棵树。

  1. 前序遍历（Preorder Traversal）：以根节点、左子树、右子树的顺序遍历二叉树。
  2. 中序遍历（Inorder Traversal）：以左子树、根节点、右子树的顺序遍历二叉树。
  3. 后序遍历（Postorder Traversal）：以左子树、右子树、根节点的顺序遍历二叉树。

接下来我们就看看前中后序遍历的代码实现，此处均以leetcode上题目为模板。

前序遍历

image-20240414140805767

递归遍历：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}

迭代法遍历：

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

image-20240414140825676

递归遍历：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);             // 注意这一句inorder(root.right, list);}
}

迭代法遍历：

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

image-20240414140838854

递归遍历：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val);             // 注意这一句}
}

迭代法遍历：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}
如何从中序和后序倒推出二叉树

先别急着看层序遍历，既然二叉树可以用这几种方式遍历，那么一定可以从这几种方式中倒推出二叉树的构造！

来看看这道题目：

image-20240414133320316

首先复习一下中序遍历与后序遍历的遍历方式：

中序：左中右

后序：左右中

如果光看中序遍历数组，无法找到中间节点，光看后序遍历的数组，无法分割左右孩子，于是将两

种遍历方式结合起来，先从后序中找到中间节点的值，再将中序数组的左右孩子分开。

思路大概是：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中

序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

接下来出场的是递归三部曲：

  1. 首先确定递归函数返回值和参数：返回treenode，参数为两个数组及其区间。

  2. 而后确定递归终止条件：当后序数组为空时，证明已经没有新的中间节点了，则返回空。

  3. 最后确定单层递归逻辑：

在本题的单层递归中，我们需要做的事情稍显复杂：

  1. 首先，我们需要从后序数组中找到最后一个值，即当前子树的根节点。
  2. 而后，在中序数组中找到该节点，并保存其索引mid。
  3. 以mid分割中序数组，找到左子树和右子树。
  4. 分割后序数组，找到中序数组中左子树与右子树对应的左子树和右子树区间。
  5. 将计算好的值传入下层递归中。
  6. 最后返回根节点。

AC代码如下：

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length == 0 || inorder.length == 0)return null;return Build(inorder, 0, inorder.length, postorder, 0, postorder.length);}public TreeNode Build(int[] inorder, int inStart, int inEnd, int[] postorder, int posStart, int posEnd){if(posStart == posEnd){return null;}//后序遍历的最后一个值，即为当前子树的根节点int rootVal = postorder[posEnd - 1];TreeNode root = new TreeNode(rootVal);int mid;//从中序遍历数组中找到root结点for (mid = inStart; mid < inEnd; mid++){if(inorder[mid] == rootVal){break;}}//分割中序数组int lInStart = inStart; int lInEnd = mid;int rInStart = mid + 1;int rInEnd = inEnd;//分割后序数组int lPosStart = posStart;int lPosEnd = posStart + (mid - inStart);int rPosStart = lPosEnd;int rPosEnd = posEnd - 1;//传入下层递归root.left = Build(inorder, lInStart, lInEnd,  postorder, lPosStart, lPosEnd);root.right = Build(inorder, rInStart, rInEnd, postorder, rPosStart, rPosEnd);return root;}  
}

2. 广度优先搜索（层序遍历）

从根节点开始，沿着树的宽度遍历树的节点。首先访问根节点，然后依次访问与根节点相邻的节点，直到遍历完整层的节点后再继续向下一层移动。

借用队列Queue来实现层序遍历，将每一层的内容放入队列中，在下一次遍历时，对队列中从头到

尾的每个元素进行检查，如果存在左右子节点，则入队，依次进行下去即可完成层序遍历。

例：对于如下二叉树，某一次的出队入队过程如下：

image-20240414140709491

示例代码如下：

class Solution {public List<List<Integer>> ans = new LinkedList<>();public List<List<Integer>> levelOrder(TreeNode root) {if(root == null){return ans;}Queue<TreeNode> que = new LinkedList<>();que.add(root);while(!que.isEmpty()){int len = que.size();List<Integer> ls = new LinkedList<>();while(len > 0){TreeNode temp = que.poll();ls.add(temp.val);if(temp.left != null){que.add(temp.left);}if(temp.right != null){que.add(temp.right);}len--;}ans.add(ls);}return ans;}
}

学完层序遍历可以一口气A完以下10题：

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的层序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

我们选取一道典型的题目来看看：

image-20240414141141829

这个题和116. 填充每个节点的下一个右侧节点指针两道题，用同一套代码直接解决了…

层序遍历真好用（喜）

用队列来进行层序遍历，再用一个list维护每一层的代码，在遍历完某一层后链接该层的next指针即可。

值得一提的是链接时用的while代码块，单独掏出来看看：

while(ls.size() > 1){Node pf = ls.removeLast();Node pb = ls.getLast();pb.next = pf;
}

首先把最后的节点保存，然后在get到倒数第二个节点，因为下一次遍历仍然会用到倒数第二个节

点，故而不能remove掉，再进行连接，结束条件是list中只剩下一个节点。

AC代码如下：

class Solution {public Node connect(Node root) {if(root == null){return root;}Queue<Node> que = new LinkedList<>();List<Node> ls = new LinkedList<>();que.add(root);while(!que.isEmpty()){int len = que.size();ls.clear();while(len > 0){Node tmp = que.poll();ls.add(tmp);if(tmp.left != null) que.add(tmp.left);if(tmp.right != null) que.add(tmp.right);len--;}while(ls.size() > 1){Node pf = ls.removeLast();Node pb = ls.getLast();pb.next = pf;}}return root;}
}

这个代码使用了List进行辅助，导致时间和空间都变得复杂了，唯一的好处是好理解，接下来登场的是优化代码~

public Node connect(Node root) {if(root == null){return root;}Queue<Node> que = new LinkedList<>();que.add(root);while (!que.isEmpty()) {int len = que.size();//前一个节点Node pre = null;while(len > 0){//出队Node node = que.poll();//如果pre为空就表示node节点是这一行的第一个，//没有前一个节点指向他，否则就让前一个节点指向他if (pre != null) {pre.next = node;}//然后再让当前节点成为前一个节点pre = node;//左右子节点如果不为空就入队if (node.left != null) que.add(node.left);if (node.right != null) que.add(node.right);len--;}}return root;
}

将内层的循环拿出来看：

定义一个pre节点，用于保存每次的节点，依次向后遍历，将每次出队的节点保存为node，若首次

插入，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();
//前一个节点
Node pre = null;
while(len > 0){//出队Node node = que.poll();//如果pre为空就表示node节点是这一行的第一个，//没有前一个节点指向他，否则就让前一个节点指向他if (pre != null) {pre.next = node;}//再让当前节点成为前一个节点pre = node;if (node.left != null) que.add(node.left);if (node.right != null) que.add(node.right);len--;
}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();
//前一个节点
Node pre = null;
while(len > 0){//出队Node node = que.poll();//如果pre为空就表示node节点是这一行的第一个，//没有前一个节点指向他，否则就让前一个节点指向他if (pre != null) {pre.next = node;}//再让当前节点成为前一个节点pre = node;if (node.left != null) que.add(node.left);if (node.right != null) que.add(node.right);len--;
}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

代码随想录 (programmercarl.com)

这篇关于【数据结构】二叉爆炸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2