当前位置： 首页 > article >正文

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

article 2025/2/2 0:04:07

目录

一、简介

二、二叉树的类型

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);
            }
        }
        else
            return;
        //递归左右时深度记得加1
        traverse(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;
    }
}

http://www.kler.cn/a/527790.html

相关文章：

  • C语言--数据在内存中的存储
  • 【Block总结】动态蛇形卷积，专注于细长和弯曲的局部结构|即插即用
  • AI在自动化测试中的伦理挑战
  • Java---入门基础篇(上)
  • 1.五子棋对弈python解法——2024年省赛蓝桥杯真题
  • Kafka 消费端反复 Rebalance: `Attempt to heartbeat failed since group is rebalancing`
  • 笔记：电机及控制器的功率测量是怎么进行的？
  • 服务器架构设计大全及其优缺点概述
  • 长尾关键词在SEO提升网站流量中的关键角色与应用技巧分析
  • AVL树介绍
  • Java设计模式：行为型模式→观察者模式
  • LeetCode-180. 连续出现的数字
  • 吉首市城区地图政府附近1公里范围高清矢量pdf\cdr\ai内容测评
  • TCP三次握手和四次挥手面试题
  • WordPress eventon-lite插件存在未授权信息泄露漏洞(CVE-2024-0235)
  • DFS（深度优先搜索）与回溯算法详解
  • LLMs之WebRAG：STORM/Co-STORM的简介、安装和使用方法、案例应用之详细攻略
  • 芯片AI深度实战：给vim装上AI
  • Vue 3 30天精进之旅：Day 10 - Vue Router
  • 计算机毕业设计Python+CNN卷积神经网络考研院校推荐系统 考研分数线预测 考研推荐系统 考研爬虫 考研大数据 Hadoop 大数据毕设 机器学习
  • LeetCode--84. 柱状图中最大的矩形【单调栈】
  • OpenCV：闭运算
  • C++11（中）
  • 5 长度和距离计算模块（length.rs）
  • 《苍穹外卖》项目学习记录-Day7导入地址簿模块功能代码
  • SSM开发(十) SSM框架协同工作原理