04树 + 堆 + 优先队列 + 图（D1_树（D2_二叉树（BT）（D1_基础学习）））

news/2025/3/10 6:15:24/

目录

一、简介

二、二叉树的类型

1. 严格二叉树

2. 满二叉树

3. 完全二叉树

三、二叉树的性质

四、二叉树的结构

五、二叉树的操作

1. 基本操作

2. 辅助操作

六、二叉树的应用

七、二叉树的遍历

1. 简介

2. 遍历方式

3. 遍历的分类：4类

3.1. 前序遍历

1> 递归前序遍历

2> 非递归前序遍历

3.2. 中序遍历

1> 递归中序

2> 非递归中序

3.3. 后序遍历

1> 递归后序

2> 非递归后序

3.4. 层次遍历

1> 递归层次

2> 非递归层次

一、简介

如果一棵树中的每个结点有0、1或者2个孩子结点，那么这棵树就称为二叉树。

空树也是一棵有效的二叉树。

一棵二叉树可以看作由根结点和两棵不相交的子树(分别称为左子树和右子树)组成。

如下图所示：

二、二叉树的类型

1. 严格二叉树

严格二叉树：二叉树中的每个结点要么有两个孩子结点，要么没有孩子结点。

2. 满二叉树

满二叉树：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层。

3. 完全二叉树

完全二叉树：在定义完全二叉树之前，假定二叉树的高度为h。

对于完全二叉树，如果将所有结点从根结点开始从左至右，从上至下，依次编号(假定根结点的编号为1)，

那么将得到从1~n(n 为结点总数)的完整序列。

在遍历过程中对于空指针也应赋予编号。

如果所有叶子结点的深度为h或h一1，且在结点编号序列中没有漏掉任何数字，那么这样的二叉树叫作完全

二叉树。

三、二叉树的性质

为了讨论二叉树的下述性质，假定树的高度为h，且根结点的深度为0。

四、二叉树的结构

接下来定义二叉树的结构。为了简单起见，假定结点的数据为整数。

表示一个结点(包含数据)的方法之一是定义两个指针，一个指向左孩子结点，另一个指向右孩子结点，中间

为数据字段(如下图所示)。

在树中，默认的流向是从双亲结点指向孩子结点，但并不强制表示为有向边。

如下两种表示方法相同：

五、二叉树的操作

1. 基本操作

2. 辅助操作

六、二叉树的应用

七、二叉树的遍历

1. 简介

为了对树结构进行处理，需要一种机制来遍历树中的结点。访问树中所有结点的过程叫作树遍历。

在遍历过程中，每个结点只能被处理一次，尽管其有可能被访问多次。

我们已经知道，在线性数据结构(例如，链表、栈、队列)中，数据元素是以顺序方式被访问的。

但是，在树结构中，有多种不同的方式。

树遍历类似于在树中进行搜索操作，遍历的目标是按某种特定的顺序访问树的所有结点，

且遍历过程中所有的结点均需要处理，而搜索操作在找到指定结点时就会停止。

2. 遍历方式

从二叉树的根结点开始遍历，需要执行3个主要步骤。

这3个步骤执行的不同顺序定义了树的不同遍历类型。

这3个步骤是：

  1. 在当前结点上执行一个动作(对应于访问当前结点，用符号“D”表示);
  2. 遍历该结点的左子树(用符号“L”表示);
  3. 遍历该结点的右子树(用符号“R”表示)。这个过程很容易利用递归来实现。

基于以上定义，有6种可能方法来实现树的遍历

  • LDR：先遍历左子树，访问当前结点，再遍历右子树。
  • LRD：先遍历左子树，再遍历右子树，访问当前结点。
  • DLR：访问当前结点，遍历左子树，再遍历右子树。
  • DRL：访问当前结点，遍历右子树，遍历左子树。
  • RDL：遍历右子树，访问当前结点，遍历左子树。
  • RLD：遍历右子树，遍历左子树，访问当前结点。

3. 遍历的分类：4类

根据实体(结点)处理顺序的不同，可以定义不同的遍历方法。

遍历分类可以根据当前结点被处理的顺序来划分：

如果基于当前结点(D)来分类，假设D出现在中间，那么不管L在D的左边还是R在D的左边，D都是在中间处理。

同样，不管L在 D的右边还是R在D的右边。

基于此，6种可能情况减少到了3种，分别是:

  1. 前序遍历(DLR)。
  2. 中序遍历(LDR)。
  3. 后序遍历(LRD)。

还有一种遍历方法，它不需要依赖上述顺序，即

  1. 层次遍历：这种方法从图的广度优先遍历方法启发得来。

后续讨论以下图所示的树为例。

3.1. 前序遍历

1> 递归前序遍历
  1. 访问根结点。
  2. 按前序遍历方式遍历左子树。
  3. 一般规定先遍历左子树，然后才遍历右子树，即L总在R的前面。
import java.util.*;
public class Solution {public void preorder(List<Integer> list, TreeNode root){//遇到空节点则返回if(root == null)return;//先遍历根节点list.add(root.val);//再去左子树preorder(list, root.left);//最后去右子树preorder(list, root.right);}public int[] preorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList();//递归前序遍历preorder(list, root);//返回的结果int[] res = new int[list.size()];for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}
2> 非递归前序遍历
import java.util.*;
public class Solution {public int[] preorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList(); Stack<TreeNode> s = new Stack<TreeNode>();//空树返回空数组if(root == null) return new int[0];//根节点先进栈s.push(root); while(!s.isEmpty()){//每次栈顶就是访问的元素TreeNode node = s.pop(); list.add(node.val);//如果右边还有右子节点进栈if(node.right != null) s.push(node.right);//如果左边还有左子节点进栈if(node.left != null) s.push(node.left);}//返回的结果int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}

3.2. 中序遍历

1> 递归中序
import java.util.*;
public class Solution {public void inorder(List<Integer> list, TreeNode root){//遇到空节点则返回if(root == null) return;//先去左子树inorder(list, root.left); //再访问根节点list.add(root.val); //最后去右子树inorder(list, root.right); }public int[] inorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList(); //递归中序遍历inorder(list, root); //返回的结果int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}
2> 非递归中序
import java.util.*;
public class Solution {public int[] inorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList(); Stack<TreeNode> s = new Stack<TreeNode>();//空树返回空数组if(root == null) return new int[0];//当树节点不为空或栈中有节点时while(root != null || !s.isEmpty()){ //每次找到最左节点while(root != null){ s.push(root);root = root.left;}//访问该节点TreeNode node = s.pop(); list.add(node.val); //进入右节点root = node.right; }//返回的结果int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}

3.3. 后序遍历

1> 递归后序
import java.util.*;
public class Solution {public void postorder(List<Integer> list, TreeNode root){//遇到空节点则返回if(root == null) return;//先去左子树postorder(list, root.left); //再去右子树postorder(list, root.right); //最后访问根节点list.add(root.val); }public int[] postorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList(); //递归后序遍历postorder(list, root); //返回的结果int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}
2> 非递归后序
import java.util.*;
public class Solution {public int[] postorderTraversal (TreeNode root) {//添加遍历结果的数组List<Integer> list = new ArrayList(); Stack<TreeNode> s = new Stack<TreeNode>();TreeNode pre = null;while(root != null || !s.isEmpty()){ //每次先找到最左边的节点while(root != null){ s.push(root);root = root.left;}//弹出栈顶TreeNode node = s.pop(); //如果该元素的右边没有或是已经访问过if(node.right == null || node.right == pre){ //访问中间的节点list.add(node.val); //且记录为访问过了pre = node; }else{//该节点入栈s.push(node); //先访问右边root = node.right; }}//返回的结果int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++)res[i] = list.get(i);return res;}
}

3.4. 层次遍历

1> 递归层次
import java.util.*;
public class Solution {public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {ArrayList<ArrayList<Integer> > res = new ArrayList();if(root == null)//如果是空，则直接返回空数组return res; //队列存储，进行层次遍历Queue<TreeNode> q = new ArrayDeque<TreeNode>(); q.add(root);while(!q.isEmpty()){//记录二叉树的某一行ArrayList<Integer> row = new ArrayList();  int n = q.size();//因先进入的是根节点，故每层节点多少，队列大小就是多少for(int i = 0; i < n; i++){TreeNode cur = q.poll();row.add(cur.val);//若是左右孩子存在，则存入左右孩子作为下一个层次if(cur.left != null)q.add(cur.left);if(cur.right != null)q.add(cur.right);}//每一层加入输出res.add(row); }return res;}
}
2> 非递归层次
import java.util.*;
public class Solution {//记录输出ArrayList<ArrayList<Integer> > res = new ArrayList(); void traverse(TreeNode root, int depth) {if(root != null){//新的一层if(res.size() < depth){  ArrayList<Integer> row = new ArrayList(); res.add(row);row.add(root.val);//读取该层的一维数组，将元素加入末尾}else{ ArrayList<Integer> row = res.get(depth - 1);row.add(root.val);}}elsereturn;//递归左右时深度记得加1traverse(root.left, depth + 1); traverse(root.right, depth + 1);}public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {if(root == null)//如果是空，则直接返回return res; //递归层次遍历 traverse(root, 1); return res;}
}
文章来源:https://blog.csdn.net/qq_51226710/article/details/145402637
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ppmy.cn/news/1568730.html

相关文章

HTML一般标签和自闭合标签介绍

HTML一般标签和自闭合标签介绍

在HTML中&#xff0c;标签用于定义网页内容的结构和样式。标签通常分为两类&#xff1a;一般标签&#xff08;也称为成对标签或开放闭合标签&#xff09;和自闭合标签&#xff08;也称为空标签或自结束标签&#xff09;。 以下是这两类标签的详细说明&#xff1a; 一、一般标…
阅读更多...
代码随想录算法训练营第三十九天-动态规划-337. 打家劫舍 III

代码随想录算法训练营第三十九天-动态规划-337. 打家劫舍 III

老师讲这是树形dp的入门题目解题思路是以二叉树的遍历&#xff08;递归三部曲&#xff09;再结合动规五部曲dp数组如何定义&#xff1a;只需要定义一个二个元素的数组&#xff0c;dp[0]与dp[1] dp[0]表示不偷当前节点的最大价值dp[1]表示偷当前节点后的最大价值这样可以把每个节…
阅读更多...
61.异步编程1 C#例子 WPF例子

61.异步编程1 C#例子 WPF例子

和普通的任务绑定不太相同的部分如下&#xff1a; public MainWindowViewModel(){FetchUserInfoCommand new RelayCommand(async (param) > await FetchUserInfoAsync());}private async Task FetchUserInfoAsync(){// 模拟异步操作&#xff0c;比如网络请求await Task.Del…
阅读更多...
无线通信与人工智能技术与发展年度总结

无线通信与人工智能技术与发展年度总结

2024年&#xff0c;无线通信与人工智能技术取得了显著的进步和突破&#xff0c;这些技术的革新不仅推动了行业的数字化转型&#xff0c;还为全球经济的持续发展注入了新的活力。以下是对无线通信与人工智能技术在这一年发展的详细总结。 #### 无线通信技术的飞速演进 无线通信…
阅读更多...
深入MapReduce——从MRv1到Yarn

深入MapReduce——从MRv1到Yarn

引入 我们前面篇章有提到&#xff0c;和MapReduce的论文不太一样。在Hadoop1.0实现里&#xff0c;每一个MapReduce的任务并没有一个独立的master进程&#xff0c;而是直接让调度系统承担了所有的worker 的master 的角色&#xff0c;这就是Hadoop1.0里的 JobTracker。在Hadoop1…
阅读更多...
【Linux网络编程】数据链路层

【Linux网络编程】数据链路层

前言&#xff1a; 数据链路层非常简单&#xff0c;对于程序员来说&#xff0c;这里只需要大致了解即可&#xff0c;本篇文章不做重点说明。 数据链路层介绍 数据链路层是OSI位于物理层之上和网络层之下&#xff0c;这一层的报文叫做帧。它的主要任务是确保数据从一个节点可靠地…
阅读更多...
go变量、打印、注释

go变量、打印、注释

Go 语言定义变量 变量&#xff1a;程序运行过程中的数据都是保存在内存中&#xff0c;我们想要在代码中操作某个数据时就需要去内存上找到这个变量&#xff0c;但是如果我们直接在代码中通过内存地址去操作变量的话&#xff0c;代码的可读性会非常差而且还容易出错&#xff0c;…
阅读更多...
【JavaWeb06】Tomcat基础入门：架构理解与基本配置指南

【JavaWeb06】Tomcat基础入门：架构理解与基本配置指南

文章目录 &#x1f30d;一. WEB 开发❄️1. 介绍 ❄️2. BS 与 CS 开发介绍 ❄️3. JavaWeb 服务软件 &#x1f30d;二. Tomcat❄️1. Tomcat 下载和安装 ❄️2. Tomcat 启动 ❄️3. Tomcat 启动故障排除 ❄️4. Tomcat 服务中部署 WEB 应用 ❄️5. 浏览器访问 Web 服务过程详…
阅读更多...
最新文章

Copyright @ 2022~2023