【数据结构和算法15】二叉树的实现

这篇具有很好参考价值的文章主要介绍了【数据结构和算法15】二叉树的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子

重要的二叉树结构

  • 完全二叉树(complete binary tree)是一种二叉树结构,除最后一层以外,每一层都必须填满,填充时要遵从先左后右

  • 平衡二叉树(balance binary tree)是一种二叉树结构,其中每个节点的左右子树高度相差不超过 1

1、存储

存储方式分为两种

  1. 定义树节点与左、右孩子引用(TreeNode)

  2. 使用数组,前面讲堆时用过,若以 0 作为树的根,索引可以通过如下方式计算

    • 父 = floor((子 - 1) / 2)

    • 左孩子 = 父 * 2 + 1

    • 右孩子 = 父 * 2 + 2

二叉树的节点结构

/**
 * 二叉树节点
 *
 * @author zjj_admin
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
​
    public TreeNode(int val) {
        this.val = val;
    }
​
    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }
}

2、遍历

遍历也分为两种

  1. 广度优先遍历(Breadth-first order):尽可能先访问距离根最近的节点,也称为层序遍历

  2. 深度优先遍历(Depth-first order):对于二叉树,可以进一步分成三种(要深入到叶子节点)

    1. pre-order 前序遍历,对于每一棵子树,先访问该节点,然后是左子树,最后是右子树

    2. in-order 中序遍历,对于每一棵子树,先访问左子树,然后是该节点,最后是右子树

    3. post-order 后序遍历,对于每一棵子树,先访问左子树,然后是右子树,最后是该节点

2.1、广度优先

【数据结构和算法15】二叉树的实现,满老师小课堂,算法,数据结构,深度优先

 

本轮开始时队列 本轮访问节点
[1] 1
[2, 3] 2
[3, 4] 3
[4, 5, 6] 4
[5, 6] 5
[6, 7, 8] 6
[7, 8] 7
[8] 8
[]
  1. 初始化,将根节点加入队列

  2. 循环处理队列中每个节点,直至队列为空

  3. 每次循环内处理节点后,将它的孩子节点(即下一层的节点)加入队列

注意

  • 以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树

  • 对于数组表现的二叉树,则直接遍历数组即可,自然为层序遍历的顺序

2.2、深度优先遍历

深度优先遍历有前序遍历、中序遍历和后续遍历三种

  1. 前序遍历: 先输出父节点,再遍历左子树和右子树

  2. 中序遍历: 先遍历左子树,再输出父节点,再遍历右子树

  3. 后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点

  • 小结: 看输出父节点的顺序,就确定是前序,中序还是后序

前,中,后序遍历详解

  1. 创建一颗二叉树

  2. 前序遍历 2.1 先输出当前节点(初始的时候是root节点) 2.2 如果左子节点不为空,则递归继续前序遍历 2.3 如果右子节点不为空,则递归继续前序遍历

  3. 中序遍历 3.1 如果当前节点的左子节点不为空,则递归中序遍历 3.2 输出当前节点 3.3 如果当前节点的右子节点不为空,则递归中序遍历

  4. 后序遍历 4.1 如果当前节点的左子节点不为空,则递归后序遍历 4.2 如果当前节点的右子节点不为空,则递归后序遍历 4.3 输出当前节点文章来源地址https://www.toymoban.com/news/detail-604971.html

2.3、递归实现深度优先遍历
/**
 * 前序遍历,继续递归实现
 *
 * @param root
 */
static void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + "\t");
    preOrder(root.left);
    preOrder(root.right);
}
​
​
/**
 * 中序遍历
 *
 * @param root
 */
static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    System.out.print(root.val + "\t");
    inOrder(root.right);
}
​
​
/**
 * 后续遍历
 *
 * @param root
 */
static void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + "\t");
}
2.4、非递归实现深度优先遍历
   /**
     * 前序遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String preOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                res.append(curr.val).append(" ");
                stack.push(curr);
                curr = curr.left;
            } else {
                //弹栈
                TreeNode pop = stack.pop();
                curr = pop.right;
            }
        }
        return res.toString();
    }
​
​
    /**
     * 中序遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String inOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //弹栈
                TreeNode pop = stack.pop();
                res.append(pop.val).append(" ");
                curr = pop.right;
            }
        }
        return res.toString();
    }
​
​
    /**
     * 后续遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String postOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    //弹栈
                    pop = stack.pop();
                    res.append(pop.val).append(" ");
                } else {
                    curr = peek.right;
                }
            }
        }
        return res.toString();
    }
2.5、在一个方法中实现二叉树的三种深度优先遍历(前序、中序和后续)
/**
 * 使用非递归的方式求解,在一个方法中实现
 * 实现前序遍历,中序遍历和后续遍历
 *
 * @param root
 */
static List<String> order(TreeNode root) {
    TreeNode curr = root;
    StringBuilder pre = new StringBuilder("preOrder:");
    StringBuilder in = new StringBuilder("inOrder:");
    StringBuilder post = new StringBuilder("postOrder:");
    //定义一个栈,用于存储当前节点的父节点
    LinkedList<TreeNode> s = new LinkedList();
    TreeNode pop = null;
    while (curr != null || !s.isEmpty()) {
        if (curr != null) {
            s.push(curr);
            pre.append(curr.val + " ");
            //依次向左边遍历
            curr = curr.left;
        } else {
            TreeNode peek = s.peek();
            if (peek.right == null) {
                in.append(peek.val + " ");
                //当没有右节点时
                pop = s.pop();
                //这一行打印的是中序遍历的结果
                post.append(pop.val + " ");
            } else if (peek.right == pop) {
                //当右节点已经遍历结束时
                pop = s.pop();
                //这一行打印的是中序遍历的结果
                post.append(pop.val + " ");
            } else {
                //右节点不为空并且没有遍历
                in.append(peek.val + " ");
                curr = peek.right;
            }
        }
    }
    return List.of(pre.toString(), in.toString(), post.toString());
}

到了这里,关于【数据结构和算法15】二叉树的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】二叉树的知识讲解

    目录  一,二叉树的结构深入认识  二,二叉树的遍历  三,二叉树的基本运算 3-1,计算二叉树的大小 3-2,统计二叉树叶子结点个数 3-3,计算第k层的节点个数 3-4,查找指定值的结点         二叉树是不可随机访问的,二叉树的结构是通过双亲结点与孩子结点之间的连接进

    2024年02月08日
    浏览(39)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(43)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(40)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(63)
  • 【数据结构与算法】力扣:二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 来源:力扣(LeetCode) 链接:https://leetcode.cn/p

    2024年02月13日
    浏览(44)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)
  • 【数据结构】二叉树的实现

    一棵二叉树是结点的一个有限集合,该集合分为两点: 一是为空和二是由一个根节点加上两棵别称为左子树和右子树的二叉树组成从图上看出有2个性质: 二叉树不存在度大于2的结点 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树 对于任意的二叉树都是由以下

    2024年02月02日
    浏览(38)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包