【数据结构】实现二叉树的基本操作

目录

1. 二叉树的基本操作

2. 具体实现

2.1 创建BinaryTree类以及简单创建一棵树

2.2 前序遍历

2.3 中序遍历

2.4 后序遍历

2.5 层序遍历

2.6 获取树中节点的个数

2.7 获取叶子节点的个数

2.8 获取第K层节点的个数

2.9 获取二叉树的高度

2.10 检测值为val的元素是否存在

2.11 判断一棵树是不是完全二叉树

3. 整体代码 + 测试代码

测试结果:


上一篇已经了解了一些二叉树的基本内容,这篇来讲二叉树的基本操作。

1. 二叉树的基本操作

    // 前序遍历
    void preOrder(TreeNode root);  
    // 中序遍历
    void inOrder(TreeNode root);
    // 后序遍历
    void postOrder(TreeNode root);
    
    // 获取树中节点的个数:遍历思路
    public static int nodeSize;
    void size(TreeNode root);
 
    // 获取节点的个数:子问题的思路
    int size2(TreeNode root);
    //获取叶子节点的个数:遍历思路
    public static int leafSize = 0;
    void getLeafNodeCount1(TreeNode root);
 
    // 获取叶子节点的个数:子问题
    int getLeafNodeCount2(TreeNode root);
 
    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k);
 
    // 获取二叉树的高度,时间复杂度:O(N)
    int getHeight(TreeNode root);
 
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val);
 
    //层序遍历
    void levelOrder(TreeNode root);
 
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root);

2. 具体实现

2.1 创建BinaryTree类以及简单创建一棵树

public class MyBinTree {
    private class TreeNode {
        char val;
        TreeNode left;// 左孩子的引用,常常代表左孩子为根的整棵左子树
        TreeNode right;// 右孩子的引用,常常代表右孩子为根的整棵右子树
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode root = new TreeNode('A');
        TreeNode node1 = new TreeNode('B');
        TreeNode node2 = new TreeNode('C');
        TreeNode node3 = new TreeNode('D');
        TreeNode node4 = new TreeNode('E');
        TreeNode node5 = new TreeNode('F');
        TreeNode node6 = new TreeNode('G');
        TreeNode node7 = new TreeNode('H');
        TreeNode node8 = new TreeNode('I');
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node5;
        node2.right = node6;
        node3.left = node4;
        node5.left = node7;
        node5.right = node8;
        return root;
    }
}

2.2 前序遍历

"根左右":从树根开始,先遍历根节点,继续递归的遍历左子树,最后再递归的遍历右子树。

public void preOrder(TreeNode root) {
        // 1.base case
        if (root == null) {
            return;
        }
        // 根
        System.out.print(root.val + " ");
        // 左
        preOrder(root.left);
        //右
        preOrder(root.right);
    }

2.3 中序遍历

"左根右":先递归的访问左子树,然后访问根节点,最后递归的访问右子树。

// 中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先左子树的中序
        inOrder(root.left);
        // 根
        System.out.print(root.val + " ");
        // 再右子树的中序
        inOrder(root.right);
    }

2.4 后序遍历

"左右根":先递归的访问左子树,然后递归的访问右子树,最后访问根节点。

// 后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先左子树的后序
        postOrder(root.left);
        // 再右子树的后序
        postOrder(root.right);
        // 根
        System.out.print(root.val + " ");
    }

2.5 层序遍历

借助队列先进先出的特点来遍历节点:

void levelOrder(TreeNode root) {
        if (root == null){
            System.out.println("这是颗空树!!!");
            return;
        }
        // 借助队列来模拟层序遍历的过程
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 队列为空,表示所有元素访问完毕
        while (!queue.isEmpty()){
            TreeNode cur = queue.pop();
            System.out.print(cur.val + " ");
            // 依次将当前节点的左右子树依次入队
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

2.6 获取树中节点的个数

将问题拆分成根节点与左右子树的问题,解决根节点的问题再递归调用本方法解决左右子树的问题。

第一种:需要一个全局变量来保存节点的个数,每走到一个节点先判断它是否为空,为空返回,否则加上这个节点即nodeSize+1,然后再递归的访问它的左右子树。

第二种:每走到一个节点先判断它是否为空,为空返回,否则返回1 + 左子树的节点个数 + 右子树的节点个数。

    public static int nodeSize;
    /**
     * 获取树中节点的个数:遍历思路
     */
    void size(TreeNode root) {
        if (root == null){
            return;
        }
        nodeSize ++;
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数:子问题的思路
     */
    int size2(TreeNode root) {
        if (root == null) return 0;
        return size2(root.left) + size2(root.right) + 1;
    }

2.7 获取叶子节点的个数

与上一个的思路类似,也是拆分成根节点与左右子树的问题再递归调用本方法。

第一种:需要一个全局变量来保存叶子节点的个数,每走到一个节点先判断它是否为空,为空返回,再判断它是否为叶子节点(它的左右子树是否为空),是则leafSize+1,然后再递归的访问它的左右子树。

第二种:每走到一个节点先判断它是否为空,为空返回,再判断它是否为叶子节点(它的左右子树是否为空),是,返回1,否则返回左子树的叶子节点个数 + 右子树的叶子节点个数。

    /*
     获取叶子节点的个数:遍历思路
     */
    public static int leafSize = 0;
    void getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return;
        }
        if (root.left == null && root.right == null){
            leafSize ++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /*
     获取叶子节点的个数:子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

2.8 获取第K层节点的个数

(1)判断根节点是否为空或k是否合法,根节点为空或k不合法返回0

(2)再判断是否到了第k层(k == 1),是,返回1(第k层节点个数+1)

(3)否则(没到第k层)返回根节点的左右子树的叶子节点。

int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }

2.9 获取二叉树的高度

(1)判断根节点是否为空,根节点为空,直接返回0

(2)再判断根节点的左右子树是否为空(判断树是否只有一个节点),是,返回1

(3)返回 本层高度1 + 根节点的左右子树中高度较大的数(递归的交给getHeigth方法判断)

    /*
     获取二叉树的高度
     时间复杂度:O(N)
     */
    int getHeight(TreeNode root) {
        if (root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return 1 + Math.max(getHeight(root.left),getHeight(root.right));
    }

2.10 检测值为val的元素是否存在

前序遍历的思路

第一种:

(1)判断根节点是否为空,根节点为空,直接返回null(不存在)

(2)判断根节点的值是否等于val,是,说明找到了该元素,返回根节点

(3)判断左子树中是否存在val,存在,返回该节点;不存在,再到右子树中寻找。

第二种:

与第一种思路一致,但是返回值使用布尔值,代码更简洁了。

// 检测值为value的元素是否存在1
    TreeNode find(TreeNode root, char val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        TreeNode node = find(root.left,val);
        if (node != null){
            return node;
        }
        return find(root.right,val);
    }
// 检测值为value的元素是否存在2
    public boolean contains(TreeNode root,char val){
        if (root == null) {
            return false;
        }
        if (root.val == val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

2.11 判断一棵树是不是完全二叉树

按照层序遍历的方式遍历完全二叉树

step1:当前完全二叉树的每个节点都是度为2的节点,碰到第一个叶子节点或者只有左子树没有右子树的节点时转入step2;碰到第一个只有右子树没有左子树的节点直接返回false。

step2:当前完全二叉树全是叶子节点

boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isStep1 = true;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(isStep1){
                if(node.left != null && node.right != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else if (node.left != null) {
                    queue.offer(node.left);
                    isStep1 = false;
                } else if (node.right != null){
                    return false;
                }else {
                    isStep1 = false;
                }
            }else {
                if(node.left != null || node.right != null){
                    return false;
                }
            }
        }
        return true;
    }

3. 整体代码 + 测试代码

import java.util.Deque;
import java.util.LinkedList;

public class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode root = new TreeNode('A');
        TreeNode node1 = new TreeNode('B');
        TreeNode node2 = new TreeNode('C');
        TreeNode node3 = new TreeNode('D');
        TreeNode node4 = new TreeNode('E');
        TreeNode node5 = new TreeNode('F');
        TreeNode node6 = new TreeNode('G');
        TreeNode node7 = new TreeNode('H');
        TreeNode node8 = new TreeNode('I');
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node5;
        node2.right = node6;
        node3.left = node4;
        node5.left = node7;
        node5.right = node8;
        return root;
    }

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

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

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

    public static int nodeSize;

    /**
     * 获取树中节点的个数:遍历思路
     */
    void size(TreeNode root) {
        if (root == null){
            return;
        }
        nodeSize ++;
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数:子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if (root == null) return 0;
        return size2(root.left) + size2(root.right) + 1;
    }


    /*
     获取叶子节点的个数:遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return;
        }
        if (root.left == null && root.right == null){
            leafSize ++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /*
     获取叶子节点的个数:子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }

    /*
     获取二叉树的高度
     时间复杂度:O(N)
     */
    int getHeight(TreeNode root) {
        if (root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return 1 + Math.max(getHeight(root.left),getHeight(root.right));
    }


    // 检测值为value的元素是否存在1
    TreeNode find(TreeNode root, char val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        TreeNode node = find(root.left,val);
        if (node != null){
            return node;
        }
        return find(root.right,val);
    }
    //    检测树中值为val的元素是否存在2
    public boolean contains(TreeNode root,char val){
        if (root == null) {
            return false;
        }
        if (root.val == val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null){
            System.out.println("这是颗空树!!!");
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.pop();
            System.out.print(cur.val + " ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isStep1 = true;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(isStep1){
                if(node.left != null && node.right != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else if (node.left != null) {
                    queue.offer(node.left);
                    isStep1 = false;
                } else if (node.right != null){
                    return false;
                }else {
                    isStep1 = false;
                }
            }else {
                if(node.left != null || node.right != null){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode root = tree.createTree();
        System.out.println("前序遍历");
        tree.preOrder(root);
        System.out.println();
        System.out.println("中序遍历");
        tree.inOrder(root);
        System.out.println();
        System.out.println("后序遍历");
        tree.postOrder(root);
        System.out.println();
        System.out.println("层序遍历");
        tree.levelOrder(root);
        System.out.println();
        System.out.println("统计树的节点个数");
        tree.size(root);
        System.out.println(nodeSize);
        System.out.println("统计叶子节点个数");
        tree.getLeafNodeCount1(root);
        System.out.println(leafSize);
        System.out.println("树的高度");
        System.out.println(tree.getHeight(root));

        System.out.println("检测树中值为val的元素是否存在");
//        System.out.println(tree.find(root,'x').val);
        if (tree.find(root,'Q') == null){
            System.out.println("没有找到该元素");
        }else {
            System.out.println(tree.find(root,'x').val);
        }
        if (tree.find(root,'B') == null){
            System.out.println("没有找到该元素");
        }else {
            System.out.println(tree.find(root,'B').val);
        }
        System.out.println("获取第K层节点的个数");
        System.out.println(tree.getKLevelNodeCount(root,3));

        System.out.println("判断一棵树是不是完全二叉树");
        System.out.println(tree.isCompleteTree(root));
    }

}

测试结果:

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/3676.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Fiddler抓取https史上最强教程

有任何疑问建议观看下面视频 2023最新Fiddler抓包工具实战&#xff0c;2小时精通十年技术&#xff01;&#xff01;&#xff01;对于想抓取HTTPS的测试初学者来说&#xff0c;常用的工具就是fiddler。 但是初学时&#xff0c;大家对于fiddler如何抓取HTTPS难免走歪路&#xff…

使用stm32实现电机的PID控制

使用stm32实现电机的PID控制 PID控制应该算是非常古老而且应用非常广泛的控制算法了&#xff0c;小到热水壶温度控制&#xff0c;大到控制无人机的飞行姿态和飞行速度等等。在电机控制中&#xff0c;PID算法用的尤为常见。 文章目录使用stm32实现电机的PID控制一、位置式PID1.计…

史诗级详解面试中JVM的实战

史诗级详解面试中JVM的实战 1.1 什么是内存泄漏?什么是内存溢出?1.2 你们线上环境的JVM都设置多大?1.3 线上Java服务器内存飙升怎么回事?1.4 线上Java项目CPU飙到100%怎么排查?1.5 线上Java项目OOM了,怎么回事?1.1 什么是内存泄漏?什么是内存溢出? 内存溢出:OutOfMe…

JavaScript中的for in和for of的区别(js的for循环)

简述&#xff1a;js中的for循环大家都知道&#xff0c;今天来分享下for in和for of在使用时区别和注意事项&#xff0c;顺便做个笔记&#xff1b; 测试数据 //数组const arr [1, 2, 3, 4, 5]//对象const obj {name: "小李",color: ["plum", "pink&q…

【巨人的肩膀】JAVA面试总结(七)

&#x1f4aa;MyBatis 1、谈谈你对MyBatis的理解 Mybatis是一个半ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;它内部封装了JDBC&#xff0c;加载驱动、创建连接、创建statement等繁杂的过程&#xff0c;开发者开发时只需要关注如何编写SQL语句&#xff0c;可以…

蓝桥杯C/C++VIP试题每日一练之完美的代价

💛作者主页:静Yu 🧡简介:CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家,前端知识交流社区创建者 💛社区地址:前端知识交流社区 🧡博主的个人博客:静Yu的个人博客 🧡博主的个人笔记本:前端面试题 个人笔记本只记录前端领域的面试题目,项目总结,面试技…

Python 十大开源Python库,看看你熟悉几个?

嗨害大家好鸭&#xff01;我是芝士❤ 对于码农来说&#xff0c; 关注的永远是新近有什么流行的、 既能解决问题又好用的利器。 本文就为你盘点十大开源Python库。 1、Pipenv 第一名非它莫属&#xff0c; 这个工具2017年初才发布&#xff0c; 但它已经能够影响每个Python开发…

菜鸟刷题Day7

⭐作者&#xff1a;别动我的饭 ⭐专栏&#xff1a;菜鸟刷题 ⭐标语&#xff1a;悟已往之不谏&#xff0c;知来者之可追 一.整理字符串&#xff1a;1544. 整理字符串 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个由大小写英文字母组成的字符串 s 。 一个整理好的字…

C语言番外-------《函数栈帧的创建和销毁》知识点+基本练习题+完整的思维导图+深入细节+通俗易懂建议收藏

绪论 书接上回&#xff0c;上回我们已经将C语言的所有知识点进行了总结归纳到同一个思维导图中&#xff0c;而本章是一个番外篇&#xff0c;将具体讲述一些更深入的知识。 话不多说安全带系好&#xff0c;发车啦&#xff08;建议电脑观看&#xff09;。 附&#xff1a;红色&…

我用Python django开发了一个商城系统,已开源,求关注!

起始 2022年我用django开发了一个商城的第三方包&#xff0c;起名为&#xff1a;django-happy-shop。当时纯粹是利用业余时间来开发和维护这个包&#xff0c;想法也比较简单&#xff0c;Python语言做web可能用的人比较少&#xff0c;不一定有多少人去关注&#xff0c;就当是一个…

我们在操作自动化测如何实现用例设计实例

在编写用例之间&#xff0c;笔者再次强调几点编写自动化测试用例的原则&#xff1a; 1、一个脚本是一个完整的场景&#xff0c;从用户登陆操作到用户退出系统关闭浏览器。 2、一个脚本脚本只验证一个功能点&#xff0c;不要试图用户登陆系统后把所有的功能都进行验证再退出系统…

【开发】后端框架——Dubbo

前置知识&#xff1a; 微服务 Dubbo是高性能的RPC框架&#xff0c;主要目的是支持远程调用 Dubbo Dubbo是一个 高性能和透明化的RPC框架 &#xff0c;主要目的是支持远程调用&#xff0c;是阿里巴巴SOA服务化治理方案的核心框架 最大的特点是按照分层的方式来 架构 &#xff0c…

LDNet分割模型搭建

原论文&#xff1a;https://arxiv.org/abs/2110.09103源码&#xff1a;https://github.com/unilight/LDNet 直接步入正题~~~ 一、ESA_blcok模块 1、PPM模块 class PPM(nn.Module):def __init__(self, pooling_sizes(1, 3, 5)):super().__init__()self.layer nn.ModuleList…

蓝桥杯刷题冲刺 | 倒计时13天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.母牛的故事2.魔板1.母牛的故事 题目 链接&#xff1a; [递归]母牛的故事 - C语言网 (dotcpp.c…

基于微信小程序+爬虫制作一个表情包小程序

跟朋友聊天斗图失败气急败坏的我选择直接制作一个爬虫表情包小程序&#xff0c;从源头解决问题&#xff0c;从此再也不用担心在斗图中落入下风 精彩专栏持续更新↓↓↓ 微信小程序实战开发专栏 一、API1.1 项目创建1.2 图片爬虫帮助类1.3 测试窗体1.4 接口封装二、小程序2.1 项…

【iOS】GCD再学

文章目录前言GCD概要什么是GCD多线程编程GCD的APIDispatch Queuedispatch_queue_createMain Dispatch Queue/Global Dispatch Queuedispatch_set_target_queuedispatch_afterDispatch Groupdispatch_barrier_asyncdispatch_syncdispatch_applydispatch_suspend/dispatch_resume…

网络安全 2023 年为什么如此吃香?事实原来是这样....

前言由于我国网络安全起步晚&#xff0c;所以现在网络安全工程师十分紧缺。俗话说:没有网络安全就没有国家安全为什么选择网络安全&#xff1f;十四五发展规划建议明确提出建设网络强国&#xff0c;全面加强网络安全保障体系和能力建设&#xff0c;加强网络文明建设&#xff0c…

多线程(三):Thread 类的基本属性

上一个篇章浅浅了解了一下 线程的概念&#xff0c;进程与线程的区别&#xff0c;如何实现多线程编程。 而且上一章提到一个重要的面试点&#xff1a; start 方法和 run 方法的区别。 start 方法是从系统那里创建一个新的线程&#xff0c;这个线程会自动调用内部的run 方法&…

瑟瑟发抖吧~OpenAI刚刚推出王炸——引入ChatGPT插件,开启AI新生态

5分钟学会使用ChatGPT 插件&#xff08;ChatGPT plugins&#xff09;——ChatGPT生态建设的开端ChatGPT插件是什么OpenAI最新官方blog资料表示&#xff0c;已经在ChatGPT中实现了对插件的初步支持。插件是专门为以安全为核心原则的语言模型设计的工具&#xff0c;可帮助ChatGPT…

JSON 教程导读

JSON 教程导读在开始深入了解JSON知识之前&#xff0c;让我们先了解什么是JSON&#xff01;JSON: JavaScript Object Notation(JavaScript 对象表示法) JSON 是存储和交换文本信息的语法&#xff0c;类似 XML。JSON 比 XML 更小、更快&#xff0c;更易解析。JSON实例&#xff1…
最新文章