0
0

Java数据结构-手砍二叉树

前言:

    今天,我们终于来了解二叉树了,其实树呢有很多种,二叉树,线索化二叉树,B树,B+树,赫夫曼树,红黑树......所以呢,我们先开始从最简单的二叉树开始学起,领略树的奥秘,探索高层次数据结构.

    我们将从一下几个方面展开阐述:

    ***二叉树的概述 🔜 二叉树的创建思路 🔜 二叉树的代码实现与分析 🔜 总结***

*** 喜欢博主的话,戳这🎟️关注作者***

*** 精彩分区: 数据结构 SQL SE知识点(周更)***

*** 往期精彩:***

*** 哈希表的实现***

*** 七大排序算法***


好一个二叉树

🎆二叉树的概述:

     **在我们概述二叉树之前,我们不妨先回顾一下我们我们以前学过的数据结构,比较典型的有两个个,第一个是数组,第二个是链表,其实,数组和链表都有他们本身的优点,也有他们本身的缺点.**

数据结构的回顾🎇

   **数组的优点:因为数组在Java中在堆空间内是连续存放到,所以数组元素的内存地址是连续的,我们可以通过某个数学表达式直接定位到该下标中,故检索效率极高**

** 数组的缺点:当我们进行随机删改的时候,因为数据存储的连续性,常常伴随着大量数据移动,导致效率极低**

** 链表的优点:随机删改元素的效率极高,我们只需要找到待删除节点或者是前一个节点的元素即可,不需要对数据进行大量的移动**

** 链表的缺点:链表检索元素的效率极低,无论是单向链表还是双向链表甚至是环形链表,我们都需要从头节点开始一个一个的去遍历,如果我们要找的是最后一个元素,效率极低**

二叉树的引出🎇

    **接下来,我们树结构的引出了**

** 二叉树,不论是检索效率和随机删改效率都大幅提升,其本质原因是该数据结构的独特性,例如删除元素,找到待删除节点的父节点即可,检索元素,树的检索类似于二分查找,能减少多于一半的检索次数,效率较链表大幅提高,这就是二叉树**

二叉树的定义🎇

   **若树的节点中只有两个子节点,这种树被称为二叉树 **

常用术语

常用术语
术语含义父节点顾名思义,一个包含其他节点的节点子节点顾名思义,一个节点包含的另一个节点根节点第一个出发的节点层相当于第几行树高总层数子树子节点以及起下面所有节点的和叶子节点没有子节点的节点节点的权该节点的值森林多颗子树构成森林路径从根节点到目标节点的路径节点****构成树的元素

🥸关于前中后序

😶‍🌫️前序:

    前序通常被理解为根左右,其表达的意思如下(以遍历节点为例,其他思路也一致)
  1. 先输出当前节点
  2. 判断该节点的左子节点是否为空,若不为空,则进入左子树遍历
  3. 判断该节点的右子节点是否为空,若不为空,则进入右子树遍历
  4. 注意:若左子节点不为空,会一直进入左子树,某一次左子节点为空了,才有机会进入右子树

😶‍🌫️中序:

    中序通常被理解为左根右
  1. 判断该节点的左子节点是否为空,若不为空,则进入左子树遍历
  2. 先输出当前节点
  3. 判断该节点的右子节点是否为空,若不为空,则进入右子树遍历
  4. 注意:若左子节点不为空,会一直进入左子树,某一次左子节点为空了,才有机会进入右子树

😶‍🌫️后序:

     后序通常被理解为左右根
  1. 判断该节点的左子节点是否为空,若不为空,则进入左子树遍历
  2. 判断该节点的右子节点是否为空,若不为空,则进入右子树遍历
  3. 先输出当前节点
  4. 注意:若左子节点不为空,会一直进入左子树,某一次左子节点为空了,才有机会进入右子树

🎆二叉树的创建思路:

  1. ** 创建一个节点类,该节点类中应该有两个属性left和right**
  2. ** 创建一个二叉树类,该二叉树类中应该有属性root**
  3. ** 前面哈希表已经阐述过,二叉树的创建思维与哈希表相似,都要有底层思想**
  4. ** 在两个类中都创建对应的方法,完成二叉树**

🎆二叉树的代码实现与分析:

1.创建一个节点类✨

public class Node {
    public int no;
    public String name;
    public Node left;
    public Node right;

    public Node(int no,String name) {
        this.name = name;
        this.no = no;
    }

    public String toString() {
        return "名字:" + name + " 序号:" + no;
    }
}

🎊代码分析:

  1. ** no,name是节点的data域,用于存放数据的,left和right分别存放左子节点和右子节点的内存地址**
  2. ** 我们需要一个有参构造,用于初始化我们的节点(注意:千万不要初始化左右节点,必须要通过方法增加或者手动增加)**
  3. ** 重写toString方法,为了方便输出,随着读者的自由发挥**

2.创建一个树类✨

public class BinaryTree {
    public Node root;
}

🎊代码分析:

  1. 属性root代表的是根节点,即第一个节点
  2. ** 树中可以不写构造方法,利用默认无参构造即可,也可以写,随你喜欢**

节点中的方法

3.创建一个遍历节点的方法(前序)✨

public void prefixOrder() {
        System.out.println(this);
        if (left != null) {
            left.prefixOrder();
        }
        if (right != null) {
            right.prefixOrder();
        }
    }

🎊代码分析:

  1. 先输出当前节点
  2. ** 判断左子节点是否不为空,若不为空则直接进入左子树递归**
  3. ** 判断右子节点是否不为空,若不为空则直接进入右子树递归**

4.创建一个遍历节点的方法(中序,后序)✨

    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    public void suffixOrder() {
        if (left != null) {
            left.suffixOrder();
        }
        if (right != null) {
            right.suffixOrder();
        }
        System.out.println(this);
    }

🎊代码分析:

   **略~~~**

5.创建一个查找节点的方法(前序)✨

 public Node prefixSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //这个辅助变量的建立是为了防止过早的结束递归,导致无法向右递归查找
        Node resNode = null;
        if (left != null) {
            resNode = left.prefixSearch(no);
        }
        // 这个if能提高代码效率,不能省略
        if(resNode != null) {
            return resNode;
        }
        if (right != null) {
            resNode =  right.prefixSearch(no);
        }
        return resNode;
    }

🎊代码分析:

  1. 先判断当前节点是否是我们想要的节点,如果是则直接返回该节点
  2. 建立一个辅助变量resNode,用于存放递归后的结果
  3. 如果左子节点不为空,则进入左子树递归查找,并将结果返回resNode
  4. 如果resNode不为空,说明在左子树的方向已经找到了该节点,可以直接跳出方法,不需要去右子树查找
  5. 如果resNode为空,则说明在左子树方向找不到,应该到右子树方向去查找,最后不论是否为空,直接返回
  6. 注意:resNode必须要有,不能直接返回向左子树递归后的结果或者是右子树递归后的结果,否则会出现只查找了左子树,没有机会查找右子树(因为return触发了,下面代码没机会执行了)
  7. 注意:最后的resNode不需要写判断.因为左子树没有,右子树仍然没有,就是真的没有了,不需要判断

6.创建一个查找节点的方法(中序+后序)✨

public Node infixSearch(int no) {
        Node resNode = null;
        if (left != null) {
            resNode = left.infixSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (right != null) {
            resNode = right.infixSearch(no);
        }
        return resNode;
    }

    public Node suffixSearch(int no) {
        Node resNode = null;
        if (left != null) {
            resNode = left.suffixSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (right != null) {
            resNode = right.suffixSearch(no);
        }
        // 若不写会少递归情况(辟邪)
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        // 为了找不到而写
        return resNode;
    }

🎊代码分析:

    **略~~~**

7.创建一个删除的方法✨

要求:

若删除的是叶子节点则直接置空

**若删除的是非叶子节点则直接将该子树置空 **

    public Node del(Node node) {
        Node res = null;
        if (left != null && left.equals(node)) {
            res = left;
            left = null;
            return res;
        }
        if (right != null && right.equals(node) {
            res = right;
            right = null;
            return res;
        }
        if (left != null) {
            res = left.del(node);
        }
        if (res != null) {
            return res;
        }
        if (right != null) {
            res = right.del(node);
        }
        return res;
    }

🎊代码分析:

  1. 首先明确的是,删除节点必须要找到待删除结点的父节点
  2. ** 一:判断当前节点的左子节点是否为空,若不为空继续判断是否为我们想要删除的节点,若是则 直接置空,并将其放回**
  3. 注意:我们需要将待删除节点放入一个辅助引用中,再置空,方便传回来
  4. 同理得右子节点的操作
  5. 如果当前节点的左右子节点都不是,则判断左子节点是否为空,若不为空,则跳入左子树进行递归删除,并用res接收返回值
  6. 若返回值不为空,说明已删除该节点,可以直接结束方法,否则同上进入右子树去删除
  7. 最后不论是否为空,若为空说明删除失败,若不为空则说明删除成功,不需要判断
  8. 注意:该删除方法必须要有返回值,如果没有返回值,假设在左边删除了该节点,该方法不会立刻退出,而是继续去右子树去删除,大大降低了程序的效率

8.创建一个删除的方法(升级版)✨

要求:

若删除的是叶子节点则直接置空

若删除的是非叶子节有如下要求:

1.若只有一个节点,则直接让该节点替代他

2.若有两个节点,则让左子节点替换他

public void delete(Node node) {
        if (left != null && left.no == node.no) {
            left = delFinish(left);
        }
        if (right != null && right.no == node.no) {
            right = delFinish(right);
        }
        if (left != null) {
            left.delete(node);
        }
        if (right != null) {
            right.delete(node);
        }
    }

    public Node delFinish(Node root) {
        if (root.left == null && root.right == null) {
            root = null;
        }else if (root.left != null && root.right == null) {
            root = root.left;
        }else if (root.left == null) {
            root = root.right;
        }else {
            root.left.right = root.right;
            root = root.left;
        }
        return root;
    }

🎊代码分析:

  1. 整体的删除思路不变,主要阐述一下deleteFinish中怎么写出满足要求的代码
  2. ** 若当前节点的左子节点和右子节点都为空,则说明是叶子节点,直接置空**
  3. ** 若左子节点不为空,右子节点为空,说明只有一个节点,让该节点顶上去即可,即root = root.left, 让父节点指向子节点**
  4. ** 注意:root只是一个变量,不是根节点的意思**
  5. ** 若左子节点为空,经过了两个判断,右子节点一定不为空,则让该节点顶上即可,即 root = root.right**
  6. ** 最后,若有两个节点,先把右子节点,放到左子节点的右子节点,保障了右子树的完整,即root.left.right = root.right,然后再顶上去,即root = root.left**
  7. ** 注意:这个操作不可避免会损失一些子树,但是这个是最好的保留情况了**

二叉树中的方法

9.创建对应的方法✨

public void prefixOrder() {
        if (root != null) {
            root.prefixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public void suffixOrder() {
        if(root != null) {
            root.suffixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public Node prefixSearch(int no) {
        if (root != null) {
            return root.prefixSearch(no);
        }
        return null;
    }

    public Node infixSearch(int no) {
        if (root != null) {
            return root.infixSearch(no);
        }
        return null;
    }

    // 后续查找方式最优
    public Node suffixSearch(int no) {
        if (root != null) {
            return root.suffixSearch(no);
        }
        return null;
    }

    public Node del(Node node) {
        if (root == null) {
            return null;
        }else {
            if (root.equals(node)) {
                var res = root;
                root = null;
                return res;
            }
        }
        return root.del(node);
    }

    /**
     * 若删除非叶子节点,若只有一个节点,则用该节点替代他
     * 若有两个节点,则用左子节点替代他
     * @return 已删除的节点
     */
    public void delete(Node node){
        if (root != null) {
            if (root.no == node.no) {
                root = root.delFinish(root);
            } else {
                root.delete(node);
            }
        }
    }

🎊代码分析:

  1. 可以看出的是,表层调用的方法都是清一色的先判断根节点是否为空,在调用底层方法,不具有 难度
  2. ** **特别注意删除节点,因为删除节点要找到待删除节点的上一个节点,所以对根节点要特殊处理, 若根节点是我们想要删除的节点,则置空,或调用deleteFinsh方法,否则调用底层方法

🥸完整代码

package datastructure.chapter04.tree.binarytree.publicbinarytree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 江骏杰
 * Date: 2022-03-22
 * Time: 16:07
 */
public class Node {
    public int no;
    public String name;
    public Node left;
    public Node right;

    public Node(int no,String name) {
        this.name = name;
        this.no = no;
    }

    public String toString() {
        return "名字:" + name + " 序号:" + no;
    }

    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }else if (!(obj instanceof Node)) {
            return false;
        }
        var node = (Node)obj;
        return this.no == node.no && this.name.equals(node.name);
    }

    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    public void suffixOrder() {
        if (left != null) {
            left.suffixOrder();
        }
        if (right != null) {
            right.suffixOrder();
        }
        System.out.println(this);
    }

    public void prefixOrder() {
        System.out.println(this);
        if (left != null) {
            left.prefixOrder();
        }
        if (right != null) {
            right.prefixOrder();
        }
    }

    public Node prefixSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //这个辅助变量的建立是为了防止过早的结束递归,导致无法向右递归查找
        Node resNode = null;
        if (left != null) {
            resNode = left.prefixSearch(no);
        }
        // 这个if能提高代码效率,不能省略
        if(resNode != null) {
            return resNode;
        }
        if (right != null) {
            resNode =  right.prefixSearch(no);
        }
        return resNode;
    }

    public Node infixSearch(int no) {
        Node resNode = null;
        if (left != null) {
            resNode = left.infixSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (right != null) {
            resNode = right.infixSearch(no);
        }
        return resNode;
    }

    public Node suffixSearch(int no) {
        Node resNode = null;
        if (left != null) {
            resNode = left.suffixSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (right != null) {
            resNode = right.suffixSearch(no);
        }
        // 若不写会少递归情况(辟邪)
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        // 为了找不到而写
        return resNode;
    }

    public Node del(Node node) {
        Node res = null;
        if (left != null && left.equals(node)) {
            res = left;
            left = null;
            return res;
        }
        if (right != null && right.equals(node)) {
            res = right;
            right = null;
            return res;
        }
        if (left != null) {
            res = left.del(node);
        }
        if (res != null) {
            return res;
        }
        if (right != null) {
            res = right.del(node);
        }
        return res;
    }

    public void delete(Node node) {
        if (left != null && left.no == node.no) {
            left = delFinish(left);
        }
        if (right != null && right.no == node.no) {
            right = delFinish(right);
        }
        if (left != null) {
            left.delete(node);
        }
        if (right != null) {
            right.delete(node);
        }
    }

    public Node delFinish(Node root) {
        if (root.left == null && root.right == null) {
            root = null;
        }else if (root.left != null && root.right == null) {
            root = root.left;
        }else if (root.left == null) {
            root = root.right;
        }else {
            root.left.right = root.right;
            root = root.left;
        }
        return root;
    }
}
package datastructure.chapter04.tree.binarytree.publicbinarytree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 江骏杰
 * Date: 2022-03-22
 * Time: 16:07
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        var binaryTree = new BinaryTree();
        binaryTree.root = new Node(1,"1");
        var node1 = new Node(2,"2");
        var node2 = new Node(3,"2");
        var node3 = new Node(4,"2");
        var node4 = new Node(5,"2");
        binaryTree.root.left = node1;
        binaryTree.root.right = node2;
        node1.left = node3;
        node3.right = node4;
        binaryTree.delete(new Node(1,"1"));
        binaryTree.prefixOrder();
    }
}
package datastructure.chapter04.tree.binarytree.publicbinarytree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 江骏杰
 * Date: 2022-03-22
 * Time: 16:07
 */
public class BinaryTree {
    public Node root;
    public void prefixOrder() {
        if (root != null) {
            root.prefixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public void suffixOrder() {
        if(root != null) {
            root.suffixOrder();
            return;
        }
        System.out.println("树中无节点");
    }

    public Node prefixSearch(int no) {
        if (root != null) {
            return root.prefixSearch(no);
        }
        return null;
    }

    public Node infixSearch(int no) {
        if (root != null) {
            return root.infixSearch(no);
        }
        return null;
    }

    // 后续查找方式最优
    public Node suffixSearch(int no) {
        if (root != null) {
            return root.suffixSearch(no);
        }
        return null;
    }

    public Node del(Node node) {
        if (root == null) {
            return null;
        }else {
            if (root.equals(node)) {
                var res = root;
                root = null;
                return res;
            }
        }
        return root.del(node);
    }

    /**
     * 若删除非叶子节点,若只有一个节点,则用该节点替代他
     * 若有两个节点,则用左子节点替代他
     * @return 已删除的节点
     */
    public void delete(Node node){
        if (root != null) {
            if (root.no == node.no) {
                root = root.delFinish(root);
            } else {
                root.delete(node);
            }
        }
    }
}

结论:

     看完这篇博客后,瞬间幡然醒悟,原来二叉树如此简单.妈妈再也不用担心我学不会了,我来总结一下要掌握几点

*** 1.前中后序及其引用***

*** 2.删除节点的两大要求所需要的代码***

*** 3.调用思想***

*** 4.常用术语***

**三连是对博主最大的鼓励,是博主浏览老爷们博客的动力源泉! **

标签： java 数据结构
本文转载自: https://blog.csdn.net/JOElib/article/details/123770307
版权归原作者 爪哇土著、JOElib 所有， 如有侵权，请联系我们删除。
登录后发布评论

“Java数据结构-手砍二叉树”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航