11. 数据结构之二叉树

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

前言

上一节,简单概述了树这种数据结构,以及树结构向下,具有某些一些特征的树,比如二叉树,B树,B+树,堆等。其中,二叉树是一个很重要的模块。也是在一些技术面试中,可能会问到的问题。本节,我们就二叉树,做详细介绍。

1. 存储

二叉树是一个逻辑结构底层可以用数组或者链表存储

1.1 数组存储

使用数组存储时,会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺,则数组的相应位置也空出来。
11. 数据结构之二叉树
由此,可以得出结论:在用数组存储时,

  1. 一个父节点的下标是n,那么它的左孩子节点下标就是2×n+1、右孩子节点下标就是2x(n+1)
  2. 对于一个稀疏的二叉树(孩子不满)来说,用数组表示法是非常浪费空间的
  3. 所以二叉树一般用链表存储实现。(二叉堆除外,因为二叉堆是一个完全二叉树,节点基本都是满的

1.2 链表存储

在使用链表存储时,二叉树的每个节点至少包含三部分:

  1. 存储数据的data变量
  2. 指向左孩子的left指针
  3. 指向右孩子的right指针

如下图所示:
11. 数据结构之二叉树

2. 遍历

二叉树,是典型的非线性数据结构,遍历时需要把非线性关联的节点转化成一个线性的序列,以不同的方式来遍历,遍历出的序列顺序也不同。

2.1 深度优先遍历

所谓深度优先,就是偏向于纵深,“一头扎到底”的访问方式。

2.1.1 前序遍历

二叉树的前序遍历,输出顺序是根节点、左子树、右子树
11. 数据结构之二叉树
步骤如下:

  1. 首先输出的是根节点1
  2. 由于根节点1存在左孩子,输出左孩子节点2
  3. 由于节点2也存在左孩子,输出左孩子节点4
  4. 节点4既没有左孩子,也没有右孩子,那么回到节点2,输出节点2的右孩子节点5
  5. 节点5既没有左孩子,也没有右孩子,那么回到节点1,输出节点1的右孩子节点3
  6. 节点3没有左孩子,但是有右孩子,因此输出节点3的右孩子节点6
    到此为止,所有的节点都遍历输出完毕

2.1.2 中序遍历

二叉树的中序遍历,输出顺序是左子树、根节点、右子树。
11. 数据结构之二叉树
步骤如下:

  1. 首先访问根节点的左孩子,如果这个左孩子还拥有左孩子,则继续深入访问下去,一直找到不再有左孩子 的节点,并输出该节点。显然,第一个没有左孩子的节点是节点4
  2. 依照中序遍历的次序,接下来输出节点4的父节点2
  3. 再输出节点2的右孩子节点5
  4. 以节点2为根的左子树已经输出完毕,这时再输出整个二叉树的根节点1
  5. 由于节点3没有左孩子,所以直接输出根节点1的右孩子节点3
  6. 最后输出节点3的右孩子节点6
    到此为止,所有的节点都遍历输出完毕

2.1.3 后序遍历

二叉树的后序遍历,输出顺序是左子树、右子树、根节点
11. 数据结构之二叉树
步骤如下:

  1. 首先访问根节点的左孩子,如果这个左孩子还拥有左孩子,则继续深入访问下去,一直找到不再有左孩子 的节点,并输出该节点。显然,第一个没有左孩子的节点是节点4
  2. 输出右节点5
  3. 输出节点4的父节点2
  4. 以节点2为根的左子树已经输出完毕,这时再输出整个二叉树的右子树
  5. 访问根节点的右孩子,如果这个右孩子拥有左孩子,则继续深入访问下去,一直找到不再有左
    孩子 的节点,如果没有左孩子则找右孩子,并输出该节点6
  6. 输出节点6的父节点3
    到此为止,所有的节点都遍历输出完毕。

2.2 广度优先遍历

也叫层序遍历,顾名思义,就是二叉树按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点。
11. 数据结构之二叉树
二叉树同一层次的节点之间是没有直接关联的,利用队列可以实现

2.3 遍历代码实现

2.3.1 定义树节点

package org.wanlong.tree;

/**
 * @author wanlong
 * @version 1.0
 * @description: 树节点定义
 * @date 2023/6/1 11:22
 */
public class TreeNode<T> {
    //数据
    T data;
    //左孩子
    TreeNode left;
    //右孩子
    TreeNode right;


    public TreeNode(T data) {
        this.data = data;
    }
}

2.3.2 定义树节点维护方法

package org.wanlong.tree;

/**
 * @author wanlong
 * @version 1.0
 * @description: 二叉树
 * @date 2023/6/1 11:24
 */
public class BinaryTree {

    TreeNode root;

    public void insertNode(int data) {
        root = insert(root, data);
    }

    /**
     * @param node: 基准节点
     * @param data: 待插入数据
     * @return org.wanlong.tree.TreeNode
     * @Description:往一个节点下面插入data数据
     * @Author: wanlong
     * @Date: 2023/6/1 11:28
     **/
    public TreeNode insert(TreeNode<Integer> node, Integer data) {
        //如果基准节点为空,创建新的节点插入
        if (node == null) {
            return new TreeNode(data);
        }
        //如果待插入数据小于当前节点,插入左子树
        if (data < node.data) {
            //递归确定插入左子树的位置,插入后,返回左子树指针
            node.left = insert(node.left, data);
            //如果待插入节点大于当前节点,插入右子树
        } else if (data > node.data) {
            node.right = insert(node.right, data);
        } else {
            node.data = data;
        }
        return node;
    }
}

2.3.3 前序遍历代码实现

/**
 * @param node:
 * @return void
 * @Description: 前序遍历节点 先根,再左再右
 * @Author: wanlong
 * @Date: 2023/6/1 11:38
 **/
public void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.data);
    preOrder(node.left);
    preOrder(node.right);
}

2.3.4 中序遍历代码实现

/**
 * @param node:
 * @return void
 * @Description:中序遍历 先左 再根 再右
 * @Author: wanlong
 * @Date: 2023/6/1 11:41
 **/
public void middleOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    middleOrder(node.left);
    System.out.println(node.data);
    middleOrder(node.right);
}

2.3.5 后序遍历代码实现

/**
 * @param node:
 * @return void
 * @Description:后序遍历 先左,再右,再根
 * @Author: wanlong
 * @Date: 2023/6/1 15:21
 **/
public void postOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.data);
}

2.3.6 广度优先遍历代码实现

广度优先遍历可用节点入队出队的方式便捷实现,具体代码实现如下

/**
 * @Description: 广度优先遍历
 * @Author: wanlong
 * @Date: 2023/6/1 15:29
 * @param root:
 * @return void
 **/
public void wideOrder(TreeNode root){
    //广度优先遍历可用队列出队入队的方式快速实现
    LinkedList<TreeNode> queue = new LinkedList<>();
    //根节点入队
    queue.offer(root);
    while (!queue.isEmpty()){
        //队列头节点出队
        TreeNode node = queue.poll();
        //打印数据
        System.out.println(node.data);
        //左右节点入队
        if (node.left!=null){
            queue.offer(node.left);
        }
        if (node.right!=null){
            queue.offer(node.right);
        }
    }
}

2.3.7 遍历结果测试

package org.wanlong.tree;

import org.junit.BeforeClass;
import org.junit.Test;

/**
 * @author wanlong
 * @version 1.0
 * @description: 测试树的遍历
 * @date 2023/6/1 15:15
 */
public class Client {

    static BinaryTree btt = new BinaryTree();

    @BeforeClass
    public static void init() {
        btt.insertNode(10);
        btt.insertNode(8);
        btt.insertNode(11);
        btt.insertNode(7);
        btt.insertNode(9);
        btt.insertNode(12);

    }

    @Test
    public void testpre() {
        btt.preOrder(btt.root);
        //10
        //8
        //7
        //9
        //11
        //12
    }

    @Test
    public void testMiddle() {
        btt.middleOrder(btt.root);
        //7
        //8
        //9
        //10
        //11
        //12
    }

    @Test
    public void testpost() {
        btt.postOrder(btt.root);
        //7
        //9
        //8
        //12
        //11
        //10
    }

    @Test
    public void testwide(){
        btt.wideOrder(btt.root);
    }
    //10
    //8
    //11
    //7
    //9
    //12
}

以上,本人菜鸟一枚,如有错误,请不吝指正。文章来源地址https://www.toymoban.com/news/detail-468655.html

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

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

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

相关文章

  • 数据结构之二叉树简介

    二叉树是一种非线性数据结构,代表“祖先”与“后代”之间的派生关系,体现了“一分为二”的分治逻辑。与链表相似,二叉树的基本单元是节点,每个节点包含值,左子节点的索引,右子节点的索引 当给定一个二叉树的节点时,我们将该节点的左子节点及其以下节点形成

    2024年02月01日
    浏览(42)
  • 《数据结构与算法》之二叉树(补充树)

    二叉搜索树,也称二叉排序树或二叉查找树 二叉搜索树:一棵二叉树,可以为空,如果不为空,应该满足以下性质: 非空左子树的所有结点小于其根结点的键值 非空右子树的所有结点大于其根结点的键值 左右子树都是二叉搜索树 对于二叉树的查找,其实沿用的是分治法的

    2024年02月08日
    浏览(46)
  • 数据结构之二叉树的实现

    目录 前言 1. 二叉树的遍历 1.1二叉树的前、中、后序遍历 1.2 层序遍历 2.二叉树的实现 2.1 二叉树的结构 2.2构建二叉树  2.2 前序遍历的实现 2.3 中序遍历的实现 2.4 后序遍历的实现 2.5 计算树的节点个数 2.6 计算树的深度 2.7 计算叶子节点个数 2.8 计算树第k层的节点数 2.9 以内容

    2023年04月10日
    浏览(45)
  • 数据结构之二叉树的性质与存储结构

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月21日
    浏览(46)
  • 数据结构奇妙旅程之二叉树初阶

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年01月19日
    浏览(62)
  • 数据结构之二叉树的数组表示

    若某节点的索引为 i ,则该节点的左子节点的索引为 2i+1 ,右子节点的索引为 2i+2 给定某节点,获取它的左右字节点,父节点 获取前序遍历,中序遍历,后序遍历,层序遍历

    2024年01月18日
    浏览(48)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(45)
  • 数据结构之二叉树(C语言附详细代码)

    目录 一,树和二叉树 1.树 ①定义 ②关于树的一些概念 2.二叉树 ①定义 ②特殊的二叉树 ③二叉树的性质 ④二叉树的存储结构(顺序结构,只适用于完全二叉树) ⑤二叉树的遍历 二,二叉树操作代码 1.头文件 2.函数代码 ①创建二叉树 ②前序遍历二叉树 ③中序遍历二叉树 ④后序

    2024年02月01日
    浏览(32)
  • 数据结构初阶之二叉树的详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言  2.二叉树各个功能代码实现 2.1二叉树结构体 2.2二叉

    2024年02月05日
    浏览(38)
  • 数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

    二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 描述 就 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1 示例 2 提示 树中节点数的范围在 [0, 1 0 5 10^5 1 0 5 ] 内

    2024年02月06日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包