数据结构与算法练习(三)二叉树

文章目录

  • 1、树
  • 2、二叉树
  • 3、满二叉树
  • 4、完全二叉树
  • 5、二叉树的遍历(前序、中序、后序)
    • 二叉树删除节点或树
  • 6、顺序存储二叉树
    • 顺序存储二叉树遍历(前序、中序、后序)
  • 7、线索化二叉树
    • 中序线索二叉树
    • 前序线索二叉树
    • 后序线索二叉树


1、树

树是一种非线性的数据结构,是由n(n >=0)个结点组成的有限集合
如果n=0,树为空树。
如果n>0,除根节点外,其余结点被分成m(m>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。

在这里插入图片描述
相关概念:

  • 根节点:没有父节点的节点。
  • 叶节点:没有子节点的节点。
  • 兄弟节点:具有相同父节点的节点;
  • 结点的度:结点拥有的子树个数。例如A节点的度3。 B,C为2
  • 树的度:树内各结点最大的度 。例如A节点的度最大,所以树的度为3
  • 节点的层次 :从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推;
  • 树的高度或深度 :树中节点的最大层次; 如上图:树的高度为 4
  • 森林 :由 m( m>0 )棵互不相交的树的集合称为森林。

2、二叉树

二叉树(Binary tree)是每个节点最多有两个子节点的树。(删掉上面的D节点)

在这里插入图片描述

3、满二叉树

 一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
 如果一个二叉树的层数为n,且结点总数是2^n -1 ,则它就是满二叉树

在这里插入图片描述

4、完全二叉树

完全二叉树是一种特殊的二叉树,它除了最后一层外,其他每一层都被完全填满,且最后一层的节点都靠左排列。
满二叉树一定是完全二叉树

在这里插入图片描述

5、二叉树的遍历(前序、中序、后序)

按照不同的规则(看输出父节点的顺序)分为:

  • 前序遍历:先输出父节点,再遍历左子树,后右子树

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

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

    例如上面的完全二叉树:
        前序遍历:ABEFCG
        中序遍历:EBFAGC
        后序遍历:EFBGCA
    

代码实现:

package Tree;
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        //手动创建树
        binaryTree.setRoot(a);
        a.left=b;
        a.right=c;
        b.left=e;
        b.right=f;
        c.left=g;
        System.out.println("前序遍历:");
        binaryTree.preOrderM();
        System.out.println("中序遍历:");
        binaryTree.infixOrderM();
        System.out.println("后序遍历:");
        binaryTree.postOrderM();
    }
}
//创建树的属性和方法
class BinaryTree{
    //定义根节点
    Node root;

    public void setRoot(Node root) {
        this.root = root;
    }
    //前序遍历
    public void preOrderM() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
    //中序遍历
    public void infixOrderM() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
    //中序遍历
    public void postOrderM() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
}

//创建节点对象的属性和方法
class  Node{
    String name;
    Node left;
    Node right;

    public Node(String name) {
        this.name = name;
    }
    //重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public  void preOrder(){
        //先打印父节点
        System.out.println(this);
        if (this.left!=null){
            this.left.preOrder();
        }
        if (this.right!=null){
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        //先进行左树遍历
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        //先进行左树遍历
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
}
前序遍历中序遍历后序遍历
在这里插入图片描述在这里插入图片描述在这里插入图片描述

二叉树删除节点或树

  • 如果删除的节点是叶子节点,则删除该节点
  • 如果删除的节点是非叶子节点,则删除该子树

代码实现:删除树B和叶节点E

package Tree;
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        //手动创建树
        binaryTree.setRoot(a);
        a.left=b;
        a.right=c;
        b.left=e;
        b.right=f;
        c.left=g;
        System.out.println("前序遍历:");
        binaryTree.preOrderM();
        //删除某个节点
        System.out.println("删除节点E");
        binaryTree.deleteNode("E");
        System.out.println("查看删除后的节点");
        binaryTree.preOrderM();
        System.out.println("删除树B");
        binaryTree.deleteNode("B");
        System.out.println("查看删除后的节点");
        binaryTree.preOrderM();
    }
}
//创建树的属性和方法
class BinaryTree{
    //定义根节点
    Node root;

    public void setRoot(Node root) {
        this.root = root;
    }
    //前序遍历
    public void preOrderM() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
    //中序遍历
    public void infixOrderM() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
    //中序遍历
    public void postOrderM() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空!无法遍历!");
        }
    }
    //删除节点,先判断根节点是不是所需要的节点
    public  void deleteNode(String name){
       if (this.root!=null){
           if (this.root.name==name){
               this.root=null;
           }else {
               this.root.delNode(name);
           }
       }else {
           System.out.println("二叉树为空!无法删除节点");
       }
    }
}
//创建节点对象的属性和方法
class  Node{
    String name;
    Node left;
    Node right;

    public Node(String name) {
        this.name = name;
    }
    //重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "name='" + name + '\'' +
                '}';
    }
    //前序遍历
    public  void preOrder(){
        //先打印父节点
        System.out.println(this);
        if (this.left!=null){
            this.left.preOrder();
        }
        if (this.right!=null){
            this.right.preOrder();
        }
    }
    public void infixOrder() {
        //先进行左树遍历
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    public void postOrder() {
        //先进行左树遍历
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
    //删除node方法
    public void delNode(String name) {
        if (this.left!=null&&this.left.name==name){
            this.left=null;
            return;
        }
        if (this.right!=null&&this.right.name==name){
            this.right=null;
            return;
        }
        //上述是root底下的两个节点。若这两个都不是我们要的那个节点,需再递归
        if (this.left!=null){
            this.left.delNode(name);
        }
        if (this.right!=null){
            this.right.delNode(name);
        }
    }
}

6、顺序存储二叉树

 顺序存储二叉树是二叉树的一种存储方式。
 将二叉树存储在一个数组中,通过存储元素的下标反映元素之间的父子关系。

在这里插入图片描述
特点:

  • 顺序存储二叉树通常只考虑完全二叉树
  • 遍历数组arr时,仍然可以(前序、中序、后序遍历)
  • 下标为n的元素的左子节点下标为2*n+1
  • 下标为n的元素的右子节点下标为2*n+2
  • 下标为n的元素的父节点为(n-1)/2

顺序存储二叉树遍历(前序、中序、后序)

public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        String [] arr={"A","B","C","E","F","G"};
        ArrayBinaryTree tree = new ArrayBinaryTree(arr);
        tree.preOrder();
        System.out.println();
        tree.infixOrder();
        System.out.println();
        tree.postOrder();
    }
}
//实现顺序存储二叉树
class ArrayBinaryTree{
    String[] arr;

    public ArrayBinaryTree(String[] arr) {
        this.arr = arr;
    }
    public  void  preOrder(){
        this.preOrder(0);
    }
    public  void infixOrder(){
        this.infixOrder(0);
    }
    public  void  postOrder(){
        this.postOrder(0);
    }
    //实现前序遍历
    public  void  preOrder(int index){
        if (arr==null || arr.length==0){
            System.out.println("数组为空");
            return;
        }
        System.out.print(arr[index]+" ");
        if ((index * 2 + 1) < arr.length) {
            preOrder(index * 2 + 1);
        }
        //再递归右子树
        if ((index * 2 + 2) < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
    //实现中序遍历
    public  void  infixOrder(int index){
        if (arr==null || arr.length==0){
            System.out.println("数组为空");
            return;
        }
        if ((index * 2 + 1) < arr.length) {
            infixOrder(index * 2 + 1);
        }
        System.out.print(arr[index]+" ");
        //再递归右子树
        if ((index * 2 + 2) < arr.length) {
            infixOrder(index * 2 + 2);
        }
    }
    //后序遍历
    public  void  postOrder(int index){
        if (arr==null || arr.length==0){
            System.out.println("数组为空");
            return;
        }
        if ((index * 2 + 1) < arr.length) {
            postOrder(index * 2 + 1);
        }
        //再递归右子树
        if ((index * 2 + 2) < arr.length) {
            postOrder(index * 2 + 2);
        }
        System.out.print(arr[index]+" ");
    }
}

运行结果:
在这里插入图片描述

7、线索化二叉树

对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。
根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

注意:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。

遍历线索化二叉树:因为线索化后,各个结点指向有变化,因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。

中序线索二叉树

例如:中序线索二叉树

在这里插入图片描述

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        MyNode a = new MyNode("A");
        MyNode b = new MyNode("B");
        MyNode c = new MyNode("C");
        MyNode e = new MyNode("E");
        MyNode f = new MyNode("F");
        MyNode g = new MyNode("G");
        //手动创建树
        threadedBinaryTree.setRoot(a);
        a.left=b;
        a.right=c;
        b.left=e;
        b.right=f;
        c.left=g;
        System.out.println("未线索化前e节点的前驱节点和后驱");
        System.out.println("F号结点的前驱结点为:"+e.left);//3
        System.out.println("F号结点的后继结点为:"+e.right);//1
        System.out.println("中序线索化后e节点的前驱节点和后驱");
        threadedBinaryTree.infixThreadedNodes();
        System.out.println("F号结点的前驱结点为:"+e.left);//3
        System.out.println("F号结点的后继结点为:"+e.right);//1
    }
}
//定义能实现线索化的二叉树
class ThreadedBinaryTree {
    MyNode root;
    MyNode pre=null;//指向当前节点的前驱节点  递归过程中pre总是保留前一个节点
    //为了实现线索化,需要创建指向当前节点的前驱结点的指针
    public void setRoot(MyNode root) {
        this.root = root;
    }
    public void infixThreadedNodes() {
        this.infixThreadedNodes(root);
    }
    //编写对二叉树进行中序线索化的方法
    public void infixThreadedNodes(MyNode node) {
        if (node == null) {//节点为空 不能线索化
            return;
        }
            //线索化左子树
            infixThreadedNodes(node.left);
            if (node.left==null){
                node.left=pre;
                node.leftType=1;
            }
            //处理后继节点
            if (pre!=null && pre.right==null){
                pre.right=node;
                pre.rightType=1;
            }
            //每处理一个节点,让当前节点是下一个节点的前驱节点
            pre=node;
            //线索化右子树
            infixThreadedNodes(node.right);
    }
}
class  MyNode{
    String name;
    MyNode left;
    MyNode right;
    //说明
    //1.如果leftType==0 表示指向的是左子树,为1 表示指向前驱节点
    //2.如果rightType==0 表示指向的是右子树,为1 表示指向后继节点
    int leftType;
    int rightType;
    public MyNode(String name) {
        this.name = name;
    }
    //重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "name='" + name + '\'' +
                '}';
    }
}

运行结果:
在这里插入图片描述

前序线索二叉树

在这里插入图片描述

 //编写对二叉树进行前序线索化的方法
    public void preThreadedNodes(MyNode node) {
        if (node == null) {
            return;
        }
        //线索化当前节点
        //处理前驱节点     左指针为空 则将左指针指向前驱节点
        if (node.left == null) {
            node.left=pre;
            node.leftType=1;
        }
        //处理后继节点     前一个节点的后继节点指向当前节点
        if (pre != null && pre.right == null) {
            pre.right=node;
            pre.rightType=1;
         }
        //更新pre
        pre = node;
        //线索化左子树
        if (node.leftType == 0) {
            preThreadedNodes(node.left);
        }
        //线索化右子树
        if (node.rightType == 0) {
            preThreadedNodes(node.right);
        }
    }

在这里插入图片描述

后序线索二叉树

在这里插入图片描述

 //编写对二叉树进行后序线索化的方法
    public void postThreadedNodes(MyNode node) {
        if (node == null) {
            return;
        }
        //线索化左子树
        if (node.leftType == 0) {
            postThreadedNodes(node.left);
        }
        //线索化右子树
        if (node.rightType == 0) {
            postThreadedNodes(node.right);
        }
        //线索化当前节点
        if (node.left == null) {
            node.left=pre;
            node.leftType=1;
        }
        if (pre != null && pre.right == null) {
            pre.right=node;
            pre.rightType=1;
        }
        //更新pre
        pre = node;
    }

在这里插入图片描述

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

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

相关文章

悲观锁、乐观锁、自旋锁

悲观锁、乐观锁、自旋锁 &#xff08;1&#xff09;乐观锁 乐观锁是一种乐观的思想&#xff0c;即认为读多写少&#xff0c;遇到并发的可能性低&#xff0c;每次拿数据时都认为别人不会修改&#xff0c;所以不会上锁&#xff0c;但是在更新的时候会判断一下在此期间别人有没有…

开源赋能 普惠未来|中软国际寄语 2023 开放原子全球开源峰会

中软国际作为行业领先的全球化软件与信息技术服务企业及数字化转型服务商&#xff0c;近年来积极布局开源生态&#xff08;OpenHarmony、openEuler&#xff09;、智能云、ERP、AIGC、教育科技、智能车六大赛道&#xff0c;加速业务转型创新。 中软国际为开放原子开源基金会白金…

力扣---二叉树OJ题(多种题型二叉树)

文章目录 前言&#x1f31f;一、剑指 Offer 55 - I. 二叉树的深度&#x1f30f;1.1 链接&#xff1a;&#x1f30f;1.2 代码一&#xff1a;&#x1f30f;1.3 代码二&#xff1a;&#x1f30f;1.4 流程图&#xff1a; &#x1f31f;二、100. 相同的树&#x1f30f;2.1 链接&…

【ChatGPT】ChatGPT快速生成短视频

1.chatGPT剪映 chatGPT生成文本后通过剪映图文成片 这次用了new bing&#xff1a;Chatbot AI 在线网页版 (atmob.cn) 打开剪映-图文成片 把new bing生成的文本粘贴过来&#xff0c;点击生成视频。 生成好了&#xff0c;是这样 剪映自动生成的&#xff0c;最后还是得手工改改&…

Linux4.4网页与安全优化

文章目录 计算机系统5G云计算第一章 LINUX Apache网页与安全优化一、网页压缩1.检查是否安装 mod_deflate 模块2.如果没有安装mod_deflate 模块&#xff0c;重新编译安装 Apache 添加 mod_deflate 模块3.配置 mod_deflate 模块启用4.检查安装情况&#xff0c;启动服务5.测试 mo…

06 Redis分布式锁

常见面试问题 Redis除了拿来做缓存&#xff0c;你还见过基于Redis的什么用法&#xff1f;Redis 做分布式锁的时候有需要注意的问题&#xff1f;如果是 Redis 是单点部署的&#xff0c;会带来什么问题&#xff1f;那你准备怎么解决单点问题呢&#xff1f;集群模式下&#xff0c…

MySQL函数

日期函数 获得年月日&#xff1a; select current_date(); ---------------- | current_date() | ---------------- | 2017-11-19 | ----------------获得时分秒&#xff1a; select current_time(); ---------------- | current_time() | ---------------- | 13:51:21 …

SpringCloud:分布式缓存之Redis哨兵

Redis提供了哨兵&#xff08;Sentinel&#xff09;机制来实现主从集群的自动故障恢复。 1.哨兵原理 1.1.集群结构和作用 哨兵的结构如图&#xff1a; 哨兵的作用如下&#xff1a; 监控&#xff1a;Sentinel会不断检查您的master和slave是否按预期工作自动故障恢复&#xff…

使用 ChatGPT API 构建系统(三):思维链推理

今天我学习了DeepLearning.AI的 Building Systems with the ChatGPT API 的在线课程&#xff0c;我想和大家一起分享一下该门课程的一些主要内容。 下面是我们通过Open API来访问ChatGPT模型的主要代码&#xff1a; import openai#您的openai的api key openai.api_key YOUR-O…

VMware安装Centos7图形化GUI系统全过程

1、打开vmware&#xff0c;点击文件然后新建虚拟机 2、然后自定义直接下一步 3、下一步 4、这里我们稍后安装操作系统&#xff0c;继续下一步 5、随后选择Centos7 64位&#xff0c;继续下一步 6、选择你所需要安装的虚拟机存放的位置&#xff0c;虚拟机名字看自己来设置&#x…

MapReduce序列化【用户流量使用统计】

目录 什么是序列化和反序列化&#xff1f; 序列化 反序列化 为什么要序列化&#xff1f; 序列化的主要应用场景 MapReduce实现序列化 自定义bean对象实现Writable接口 1.实现Writable接口 2.无参构造 3.重写序列化方法 4.重写反序列化方法 5.顺序一致 6.重写toStri…

小狗避障-第14届蓝桥杯省赛Scratch中级组真题第4题

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥杯真题&#xff0c;这是Scratch蓝桥杯真题解析第139讲。 小狗避障&#xff0c;本题是2023年5月7日举行的第14届蓝桥杯省赛Scratch图形化编程中级组编程第4题&#xf…

二、高通相机bringup 流程

和你一起终身学习&#xff0c;这里是程序员Android 经典好文推荐&#xff0c;通过阅读本文&#xff0c;您将收获以下知识点: 一、相机Sensor 点亮相关的文件二、Sensor 驱动文件详解 一、相机Sensor 点亮相关的文件 1.1 Sensor 驱动XML以及CPP文件 Sensor 文件路径&#xff1a;…

基于stm32的超声波测距

文章目录 一、HC-SR04超声波测距模块说明1、产品特点2、电气参数3、HC-SR04超声波测距模块4、超声波时序图 二、 CUBEMX配置三、keil配置代码 模块选择&#xff1a; stm32f103c8芯片 HC-SR04超声波测距模块 一、HC-SR04超声波测距模块说明 1、产品特点 HC-SR04 超声波测距模块…

UNIX网络编程卷一 学习笔记 第十七章 ioctl操作

ioctl函数传统上一直作为那些不适合归入现有已定义类别的特性的系统接口。POSIX正在通过创建特定的包装函数来代替ioctl函数的某些功能&#xff0c;以取而代之的是那些已被POSIX标准化的函数。例如&#xff0c;Unix终端接口传统上使用ioctl函数访问&#xff0c;而POSIX为终端创…

CVE漏洞复现-CVE-2023-32233 NetFilter权限提升

CVE-2023-32233 NetFilter权限提升 Netfilter是Linux 内核中的网络数据包处理框架&#xff08;iptables&#xff09;通过各种规则和过滤器&#xff0c;基于数据包的来源、目标地址、协议类型、端口号等信息&#xff0c;控制网络流量和数据包的转发和处理具体&#xff0c;详情请…

灵活使用Postman环境变量和全局变量,提高接口测试效率!

目录 前言&#xff1a; 环境变量和全局变量的概念 环境变量和全局变量的使用方法 1. 定义变量 2. 使用变量 环境变量和全局变量的实例代码 变量的继承和覆盖 变量的动态设置 总结&#xff1a; 前言&#xff1a; Postman是一个流行的API开发和接口测试工具&#xff0c;…

RK平台使用i2c-tools调试

简介 i2ctool是嵌入式开发过程中调试i2c设备常用的工具包&#xff0c;其中比较常用的有&#xff1a;i2cdetect、i2cdump、i2cset、i2cget。 RK平台的SDK大部分默认都会带这个工具&#xff0c;如果没有编译进去或者找不到的情况下可以自己从网上下载编译进去&#xff1a;https:…

JavaScript中的Hook技术:特性、优点、缺点和使用场景

引言&#xff1a; 随着JavaScript的不断发展&#xff0c;开发者们正在寻找更灵活和可扩展的方式来修改或扩展现有的代码。其中一种广泛应用的技术是"Hook"&#xff0c;它允许开发者拦截和修改现有的函数或方法的行为。本文将详细介绍JavaScript中的Hook技术&#xf…

Hive库表基本操作

Hive基本操作-库、表 规则语法 大小写规则: 1. hive的数据库名、表名都不区分大小写 2. 建议关键字大写 复制代码 命名规则&#xff1a; 1. 名字不能使用数字开头 2. 不能使用关键字 3. 尽量不使用特殊符号 复制代码 库操作语法 创建数据库 创建数据库的本质就是在hive…