【数据结构】一文带你掌握二叉树的构造与应用

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

PS: 前面我们已经详细介绍了二叉树的概念以及二叉树的遍历的概念等,一些详细概念知识点可以在下面链接中的博客查看。本文主要需要使用代码自己实现二叉树及应用。
二叉树的概念及遍历

1. 构造二叉树

二叉树是由一个节点一个个连接而成的,每个节点最多连接两个节点,所以每个节点需要有一个数据元素和两个指向左右子树的指针,当没有左右子树时,可以为null。

public class MyTreeNode {
    public int val;
    public MyTreeNode left,right;
    public MyTreeNode(int val){
        this.val = val;
    }
    public MyTreeNode(){}
}    

因为编译器本身并不会自动构造二叉树,所以我们要编写程序来构造一个二叉树,并通过一个节点root记录根节点。

    //构造Tree
    public MyTreeNode root;
    public MyTreeNode createTree(){
        MyTreeNode node1 = new MyTreeNode(1);
        MyTreeNode node2 = new MyTreeNode(2);
        MyTreeNode node3 = new MyTreeNode(3);
        MyTreeNode node4 = new MyTreeNode(4);
        MyTreeNode node5 = new MyTreeNode(5);
        MyTreeNode node6 = new MyTreeNode(6);

        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
        return root;
    }

如图
接下来应用将围绕此树进行。
【数据结构】一文带你掌握二叉树的构造与应用

2. 前序遍历

前序遍历的遍历顺序:访问根结点—>根的左子树—>根的右子树。
遍历结果:123456

2.1 前序遍历递归

参数root是当前节点,如果为null说明已经到叶子节点,直接返回。否则,我们先输出当前节点的值,然后递归遍历左子树,最后递归遍历右子树。

    // 前序遍历递归
    public void preOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

2.2 前序遍历非递归

我们使用一个栈来辅助遍历。首先将根节点压入栈中,然后每次从栈中弹出一个节点,并输出它的值。如果该节点有右子树,我们就将右子树压入栈中,因为左子树后遍历,为了后遍历左子树,我们将左子树后入栈,所以先遍历右子树。如果该节点有左子树,我们就将左子树压入栈中,因为下一步要遍历左子树。这样,我们就依次访问了整个二叉树节点。

    //前序遍历非递归
    public void norPreOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        Stack<MyTreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            MyTreeNode cur = stack.pop();
            System.out.print(cur.val + " ");
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
    }

3. 中序遍历

根的左子树—>根节点—>根的右子树。
遍历结果:321546

3.1 中序遍历递归

用递归实现,先递归遍历左子树,遍历完后将节点值加入结果列表中,然后再递归遍历右子树。

    // 中序遍历递归
    public void inOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

3.2 中序遍历非递归

借助辅助栈实现非递归中序遍历,首先检查当前节点是否为空以及是否有左子节点,如果有则将节点入栈,并将当前节点指向左子节点,继续进入循环,直到左子树遍历完毕,然后将节点出栈并添加到结果列表中,将当前节点指向右子节点,继续遍历。

    //中序遍历非递归
    public void norInOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        Stack<MyTreeNode> stack = new Stack<>();
        MyTreeNode curr = root;
        while(curr != null || !stack.empty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            System.out.print(curr.val + " ");
            curr = curr.right;
        }
    }

4. 后序遍历

根的左子树—>根的右子树—>根节点。
遍历结果:325641

4.1 后序遍历递归

用递归实现后序遍历,先递归遍历左子树,然后递归遍历右子树,最后将当前节点的值添加到结果列表中。

    // 后序遍历递归
    public void postOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

4.2 后序遍历非递归

用辅助栈实现后序遍历,首先将根节点入栈,然后定义一个辅助栈,将根节点出栈并压入辅助栈中。然后依次将当前节点的左孩子和右孩子入栈,但先入右孩子再入左孩子,因为要保证左孩子后访问。重复这个过程直到栈为空,然后从辅助栈依次将节点的值添加到结果列表中。

	//后序遍历非递归
    public void norPostOrder(MyTreeNode root) {
        if (root == null) {
            return;
        }

        Stack<MyTreeNode> stack1 = new Stack<>();
        Stack<MyTreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            MyTreeNode cur = stack1.pop();
            stack2.push(cur);
            if (cur.left != null) {
                stack1.push(cur.left);
            }
            if (cur.right != null) {
                stack1.push(cur.right);
            }
        }

        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }

5. 层序遍历

从根节点一层一层的遍历,借助队列的先进先出的特性实现.

    //层序遍历
    public void levelOrder(MyTreeNode root){
        if(root == null){
            return;
        }
        Queue<MyTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            MyTreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

6. 节点个数

6.1 所有节点个数

直接递归,遍历整个树,递归一次加1.

    // 获取树中节点的个数
    public int size(MyTreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + root.size(root.right) + 1;
    }

6.2 获得叶子节点个数

利用递归直接遍历,左右节点为null,则为叶子节点,加1.

    // 获取叶子节点的个数
    //叶子个数
    static int countLeaf = 0;
    public int sizeLeaf(MyTreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            countLeaf++;
        }
        sizeLeaf(root.left);
        sizeLeaf(root.right);
        return countLeaf;
    }

7. 检测值为value的元素是否存在

遍历,寻找

    // 检测值为value的元素是否存在
    public MyTreeNode find(MyTreeNode root, int val) {
        if(root == null) {
            return null;
        }
        if(root.val == val){
            return root;
        }
        MyTreeNode left = find(root.left,val);
        if(left != null){
            return left;
        }
        MyTreeNode right = find(root.right,val);
        if(right != null){
            return right;
        }
        return null;
    }

8.总结

这些实现都是经典的,类似这种可太多,我们平常可以多刷刷题,提升自己的代码能力,这样也可以更好的提升自己的代码能力.
大家可以也关注我的刷题集,每周更新经典好题,瑞思拜!
数据结构刷题集文章来源地址https://www.toymoban.com/news/detail-479016.html

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

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

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

相关文章

  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(46)
  • C/C++【数据结构】一文秒懂二叉树

     个人主页:仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏:数据结构_仍有未知等待探索的博客-CSDN博客 树形结构是一类非常重要的非线性结构。树形结构是节点之间有分支,并且具有层次关系的结构,它类似于自然界中的树。 就比如说:电脑中磁盘中的

    2024年02月05日
    浏览(46)
  • 数据结构|二叉树的三种遍历方式,你掌握了几种?

    目录 1、遍历方式 2、前序遍历 3、中序遍历 学习二叉树的结构,最简单的方式就是遍历二叉树。遍历二叉树就是 通过某条线路对二叉树的各个结点进行一次访问 ,访问的方法有三种分为前序遍历、中序遍历、后续遍历,层序遍历它们的遍历顺序如下所示: 前序遍历: 根节点

    2023年04月16日
    浏览(49)
  • 由浅入深带你了解数据结构中的二叉树

    1.树的概念及结构 1.1树的概念   树是一种非线性的数据结构,它是由n(n=0)个有限节点组成一个具有层次关系的集合。它的形状像一颗倒挂的树,因此我们把它叫做树 。其特点如下所示:   1.有一个特殊的节点,称为根节点,根节点没有前驱节点   2.除根节点外,其余节点被

    2024年04月26日
    浏览(37)
  • 数据结构与算法——二叉树+带你实现表达式树(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:king南星 📖

    2024年01月25日
    浏览(50)
  • 二叉树详解:带你掌握二叉树

    因为二叉树是一种特殊的树,所以想要学习好二叉树,必须了解树型结构,知道树的基本概念。所以正式开始学习之前,在前面为大家引入了树的概念。 1. 1 树的概念 树是一种 非线性 的数据结构,它是有n个节点构成的集合,把它称为树,是因为这种结构看起来就像一个 倒

    2024年02月08日
    浏览(30)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包