二叉树-------前,中,后序遍历 + 前，中，后序查找+删除节点 （java详解）

目录

提要：

 创建一个简单的二叉树：

二叉树的前中后序遍历：

二叉树的前序遍历：

二叉树的中序遍历： 

二叉树的后续遍历：

小结： 

二叉树的前中后续查找：

二叉树的前序查找：

二叉树的中序查找：

二叉树的后续查找: 

代码实现：

二叉树节点删除操作：

思路与约定：

代码实现：

最后，完整代码：

提要：

 二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅能访问一次（说明不可二次访问，一遍而过）。遍历一颗二叉树便要决定对根结点N、左子树L和右子树的访问顺序。 二叉树常的的遍历方法有前序遍历（NLR）、中序遍历（LNR）和后序遍历（LRN）三种遍历算法，其中 “序” 指的是根结点在何时被访问。

遍历大致过程：

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

--------------------------------------------------------------------------------------------------------------------------------

 创建一个简单的二叉树：

二叉树的存储结构分为：顺序存储和类似于链表的链式存储，这里我们学习链式存储的方式， 简单枚举一棵二叉树。

用孩子表示法创建一颗二叉树：

//孩子表示法
class KunBinaryTree{
      //数据域
    public int no;//序号
    public String name;//姓名

    public KunBinaryTree left;//左孩子的引用，常常代表左孩子为根的整棵左子树
    public KunBinaryTree right;//右孩子的引用，常常代表右孩子为根的整棵右子树
    //构造方法
    public KunBinaryTree(int no,String name){
        super();
        this.no = no;
        this.name = name;
    }
}
public class TestBinaryTree {
    public static void main(String[] args){
        //对象实例化
        KunBinaryTree root = new KunBinaryTree(1,"唱");
        KunBinaryTree node1 = new KunBinaryTree(2,"跳");
        KunBinaryTree node2 = new KunBinaryTree(3,"rap");
        KunBinaryTree node3 = new KunBinaryTree(4,"篮球");
        KunBinaryTree node4 = new KunBinaryTree(5,"music");
        KunBinaryTree node5 = new KunBinaryTree(6,"坤坤");
    //链接各个节点，使其构成一颗二叉树
        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
    }
}

创建了一颗如图所示的二叉树（一共有6个节点，其中root节点为 “唱”）：

 

-------------------------------------------------------------------------------------------------------------------------------- 

二叉树的前中后序遍历：

通过上面的简单介绍，我们可以开始正式学习接下来的操作了

二叉树的前序遍历：

基本思路：

若二叉树为空，什么都不做，否则：

        i、先访问根结点；

        ii、再前序遍历左子树；

        iii、最后前序遍历右子树；

代码实现：

//前序遍历
    public static void preOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        System.out.print(root.no+" "+root.name+" ");//先访问根
        preOrder(root.left);//接着左右子树
        preOrder(root.right);
    }

函数递归展开图解：

首先，我们从蓝色出发，也就是途中的①，按照先根节点后左右子树的过程进行依次遍历，这里相当于先打印根节点所对应的数据域中的信息后，在接着递归调用左子树，直到为空，回溯后递归调用右子树，直到为空。该树的左子树（总的）调用完后， 开始调用右子树，来到②过程，按照（根-----》左子树---》右子树）的规则继续递归。直到左右子树都为空，返回，也就是③，④过程。从途中可以看出，打印的顺序为：1 唱 2 跳 3 rap 4 篮球 5 music 6 坤坤 

 通过遍历的测试结果也显示，上述过程正确：

 或则用更明了直观的动图解释（图中栗子不为上述栗子，仅做参考，便于理解）：

二叉树的中序遍历： 

 基本思路：

二叉树为空，什么也不做，否则：

        i、中序遍历左子树；

        ii、访问根结点；

        iii、中序遍历右子树

代码实现：

 //中序遍历
    public static void infixOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        infixOrder(root.left);
        System.out.print(root.no +" "+root.name+" ");
        infixOrder(root.right);
    }

 函数递归展开图：

 首先，我们先从红色出发，也就是①，按照(左子树---》根---》右子树)的规则依次遍历，这里相当于从不可在分割的左子树开始从后往前进行打印输出对应信息，与前序遍历基本一致，就是中间根节点的位置变化导致输出顺序的不同。

最终递归结果为(打印顺序为)：2 跳 1 唱 4 篮球 3 rap 6 坤坤 5 music 

通过测试也可已看出确实是这样:

 用更直观的动图展示（栗子与上述不同，主要是便于理解其过程）：

二叉树的后续遍历：

 基本思路：

若二叉树为空，什么也不做，否则：

        i、后序遍历左子树

        ii、后序遍历右子树

        iii、访问根结点

代码实现：

 //后续遍历
    public static void postOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.no +" "+root.name+" ");
    }

 函数递归展开图：

首先从①开始，按照（左子树---》右子树---》根）的规则依次遍历，过程与上述类似，不在赘述。递归结果为:2 跳 4 篮球 6 坤坤 5 music 3 rap 1 唱  

测试结果也表明上述结果正确： 

 用更直观的动图演示该过程（栗子与上述不同，主要是便于理解其过程）：

小结： 

比较各个遍历的过程 

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

我们不难发现，前序遍历的root节点（栗子中也就是"1.唱"）一定在遍历结果的首部，二中序遍历的root节点在整个树的中部，在遍历的结果中随树的变化二变化，后续遍历的root节点一定在尾部，利用这个特性，我们可以只知道（前序+中序）或者（后续+中序）或则（前序+后续）的遍历结果还原出该二叉树。

二叉树的前中后续查找：

 有了前中后续遍历的实现，我们接着就能实现查找过程，这是基于遍历来实现的

二叉树的前序查找：

基本思路：

1.先判断当前节点的no(序号)是否等于要查找的

2.如果是相等的，则返回当前节点

3.如果不等，则判断当前节点的左右子节点是否为空，如果不为空，则递归前序查找

4.如果左递归前序查找找到节点，则返回，否则继续判断当前节点的左右子节点是否为空，如果不为空，则继续右递归前序查找

代码实现：

//前序查找
    public static int count1 = 0;//用于记录递归查找的次数
    public static KunBinaryTree preOrderSearch(KunBinaryTree root,int no){
        ++count1;
        if(root.no == no){
            return root;
        }

        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = preOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }
        if(root.right != null){
            resNode = preOrderSearch(root.right,no);
        }
        return resNode;
    }

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么前序查找遍历的次数为6（即count1=6）：

测试结果：

 

二叉树的中序查找：

 基本思路：

1.判断当前节点的左右子节点是否为空，如果不为空，则递归中序查找

2.如果找到，则返回，若果没有找到，就和当前节点比较，如果是则返回当前节点，否则继续进行右递归的中序查找

3.右递归中序查找，找到就返回，否则返回null

代码实现：

//中序查找
    public static int count2 = 0;//记录中序查找次数
    public static KunBinaryTree infixOrderSearch(KunBinaryTree root,int no){
        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = infixOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }
   ++count2;
        if(root.no == no){
            return root;
        }

        if(root.right != null){
            resNode = infixOrderSearch(root.right,no);
        }
        return resNode;
    }

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么中序查找的遍历次数为5（count2=5）:

测试结果：

二叉树的后续查找: 

 基本思路：

1.判断当前节点的左子节点是否为空，如果不为空，则递归后序查找

2.如果找到，就返回，如果没有找到，就判断当前节点的有子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回

3.接着和当前节点进行比较，找到则返回，否则返回null

代码实现：

   //后序查找
    public static int count3 = 0;//记录后序查找遍历次数
    public static KunBinaryTree postOrderSearch(KunBinaryTree root,int no){
        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = postOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }

        if(root.right != null){
            resNode = postOrderSearch(root.right,no);
        }
        if(resNode != null){
            return resNode;
        }
        ++count3;
        if(root.no == no){
            return root;
        }
        return resNode;
    }

按照上述的遍历结果我们可以知道，一共进行了6次遍历，（咱们这里查找数字6）那么后序查找的次数为3（count3=3）:

测试结果：

 

二叉树节点删除操作：

 最后，咱么来进行二叉树节点删除的操作

思路与约定：

代码实现：

 //删除节点
    public static void delTreeNode(KunBinaryTree root,int no){
        if(root.no == no){
            root = null;
        }else{
            if(root.left != null && root.left.no == no){
                root.left = null;
                return ;
            }
            if(root.right != null && root.right.no == no){
                root.right = null;
                return ;
            }
            if(root.left != null){
                delTreeNode(root.left,no);
            }
            if(root.right != null){
                delTreeNode(root.right,no);
            }
        }
    }

 

这里我们删除4子节点，也就是篮球 

测试结果：

当我们删除3这个子节点时，后面的节点也一并删除了：

 

最后，完整代码：

import java.util.*;

class KunBinaryTree{
    public int no;
    public String name;
    public KunBinaryTree left;
    public KunBinaryTree right;
    public KunBinaryTree(int no,String name){
        super();
        this.no = no;
        this.name = name;
    }
}

public class BinaryTree {
//前中后序遍历
    //前序遍历
    public static void preOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        System.out.print(root.no+" "+root.name+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
   //中序遍历
    public static void infixOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        infixOrder(root.left);
        System.out.print(root.no +" "+root.name+" ");
        infixOrder(root.right);
    }
   //后续遍历
    public static void postOrder(KunBinaryTree root){
        if(root == null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.no +" "+root.name+" ");
    }
//前中后序查找
    //前序查找
    public static int count1 = 0;//用于记录递归查找的次数
    public static KunBinaryTree preOrderSearch(KunBinaryTree root,int no){
        ++count1;
        if(root.no == no){
            return root;
        }

        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = preOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }
        if(root.right != null){
            resNode = preOrderSearch(root.right,no);
        }
        return resNode;
    }
    //中序查找
    public static int count2 = 0;//记录中序查找次数
    public static KunBinaryTree infixOrderSearch(KunBinaryTree root,int no){
        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = infixOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }
   ++count2;
        if(root.no == no){
            return root;
        }

        if(root.right != null){
            resNode = infixOrderSearch(root.right,no);
        }
        return resNode;
    }

   //后序查找
    public static int count3 = 0;//记录后序查找遍历次数
    public static KunBinaryTree postOrderSearch(KunBinaryTree root,int no){
        KunBinaryTree resNode = null;
        if(root.left != null){
            resNode = postOrderSearch(root.left,no);
        }
        if(resNode != null){
            return resNode;
        }

        if(root.right != null){
            resNode = postOrderSearch(root.right,no);
        }
        if(resNode != null){
            return resNode;
        }
        ++count3;
        if(root.no == no){
            return root;
        }
        return resNode;
    }
    //删除节点
    public static void delTreeNode(KunBinaryTree root,int no){
        if(root.no == no){
            root = null;
        }else{
            if(root.left != null && root.left.no == no){
                root.left = null;
                return ;
            }
            if(root.right != null && root.right.no == no){
                root.right = null;
                return ;
            }
            if(root.left != null){
                delTreeNode(root.left,no);
            }
            if(root.right != null){
                delTreeNode(root.right,no);
            }
        }
    }
    //测试
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        KunBinaryTree root = new KunBinaryTree(1,"唱");
        KunBinaryTree node1 = new KunBinaryTree(2,"跳");
        KunBinaryTree node2 = new KunBinaryTree(3,"rap");
        KunBinaryTree node3 = new KunBinaryTree(4,"篮球");
        KunBinaryTree node4 = new KunBinaryTree(5,"music");
        KunBinaryTree node5 = new KunBinaryTree(6,"坤坤");

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;

        preOrder(root);
        System.out.println();

        infixOrder(root);
        System.out.println();
        postOrder(root);
        System.out.println();

        System.out.print("请输入要查找的数字：");
        int n = sc.nextInt();
        KunBinaryTree resNode = postOrderSearch(root,n);
        System.out.println("一共查找的次数count3："+count3);
        if(resNode != null){
            System.out.printf("找到了,Kun节点 no=%d name=%s",resNode.no,resNode.name);
        }else{
            System.out.printf("没有找到Kun节点%d的信息",n);
        }
        System.out.println();
        System.out.print("请输入要删除的子节点：");
        int n2 = sc.nextInt();
        System.out.println("删除前：");
        preOrder(root);
        System.out.println();
        System.out.println("删除后：");
        delTreeNode(root,n2);
        preOrder(root);

    }
}

博客到这里也是结束了，制作不易，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~

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

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

相关文章

双链表简介

双链表简介

一.双链表 这里简单的介绍一下双链表，双链表也是和单链表是一种类型的结构，但是也有些许不同，其中不同的地方在于，双链表多了一个可以存储上一个单元的地址，并且是循环的链表，而且还增加了一个哨兵位&…
阅读更多...
【linux内核调试及根文件系统】

【linux内核调试及根文件系统】

linux内核分成两个部分，一个是逻辑代码存于驱动代码，一个是硬件信息存于设备树 linux内核分成两个部分一部分为逻辑代码放在uimage，另一部分硬件信息放在设备树
阅读更多...
【STM32 CubeMX】HAL库的本质读写寄存器

【STM32 CubeMX】HAL库的本质读写寄存器

文章目录 前言一、HAL库的本质1.1 HAL库的本质是操作寄存器1.2 自己实现HAL_GPIO_WritePin寄存器通过寄存器的操作点灯代码概况Port bit set/reset register寄存器 总结 前言 在嵌入式系统开发中，HAL（Hardware Abstraction Layer）库是一个重…
阅读更多...
Kotlin和Java 单例模式

Kotlin和Java 单例模式

Java 和Kotlin的单例模式其实很像，只是Kotlin一部分单例可以用对象类和委托lazy来实现 Java /*** 懒汉式，线程不安全*/ class Singleton {private static Singleton instance;private Singleton() {}public static Singleton getInstance() {if (insta…
阅读更多...
肯尼斯·里科《C和指针》第13章 高级指针话题（2）函数指针

肯尼斯·里科《C和指针》第13章 高级指针话题（2）函数指针

我们不会每天都使用函数指针。但是，它们的确有用武之地，最常见的两个用途是转换表(jump table)和作为参数传递给另一个函数。本节将探索这两方面的一些技巧。但是，首先容我指出一个常见的错误，这是非常重要的。 简单声明一个函数指…
阅读更多...
静态时序分析：SDC约束命令set_clock_uncertainty

静态时序分析：SDC约束命令set_clock_uncertainty

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 set_clock_uncertainty是用来指定设计中时钟周期的不确定性，不确定性指的是对那些会对时钟周期造成的负面影响。这些不确定性可能来源于时钟抖动(clo…
阅读更多...
【JavaEE】_JavaScript（Web API）

【JavaEE】_JavaScript（Web API）

目录 1. DOM 1.1 DOM基本概念 1.2 DOM树 2. 选中页面元素 2.1 querySelector 2.2 querySelectorAll 3. 事件 3.1 基本概念 3.2 事件的三要素 3.3 示例 4.操作元素 4.1 获取/修改元素内容 4.2 获取/修改元素属性 4.3 获取/修改表单元素属性 4.3.1 value&#xf…
阅读更多...
HotCoin Global: 澳洲双牌照持有平台，坚守全球合规之路

HotCoin Global: 澳洲双牌照持有平台，坚守全球合规之路

前言： 加密交易平台的合规性不仅是相关法规遵守的问题，更是市场透明度和用户公平性的关键。为促使加密市场的交易活动有规范、有秩序地进行，确保加密投资者的资产与交易安全，部分国家明确对加密资产的交易和经营活动进行监督及管…
阅读更多...
SNMP 简单网络管理协议、网络管理

SNMP 简单网络管理协议、网络管理

目录 1 网络管理 1.1 网络管理的五大功能 1.2 网络管理的一般模型 1.3 网络管理模型中的主要构件 1.4 被管对象 (Managed Object) 1.5 代理 (agent) 1.6 网络管理协议 1.6.1 简单网络管理协议 SNMP 1.6.2 SNMP 的指导思想 1.6.3 SNMP 的管理站和委托代理 1.6.4 SNMP…
阅读更多...
博客系统-SpringBoot版本

博客系统-SpringBoot版本

相比于之前使用Servlet来完成的博客系统，SpringBoot版本的博客系统功能更完善，使用到的技术更接近企业级，快来看看吧~ 目录 1.项目介绍 2.数据库准备 3.实体化类 4.返回格式 5.登录和注册功能 6.登出（注销）功能…
阅读更多...
【Python】Python代码的单元测试

【Python】Python代码的单元测试

Python代码的单元测试 单元测试的概念 定义：是指对软件中的最小可测试单元进行检查和验证。 作用：可以确保程序模块是否否和我们规范的输出，保证该模块经过修改后仍然是满足我们的需求。 单元测试的策略 如果要创建单元测试，…
阅读更多...
C语言-----用二维数组解决菱形的打印问题

C语言-----用二维数组解决菱形的打印问题

1.打印菱形&#xff0c;多组输入&#xff0c;一个整数&#xff08;2~20&#xff09;&#xff0c;表示输出的行数&#xff0c;也表示组成“X”的反斜线和正斜线的长度。 #include <stdio.h>int main() {int n0;while(scanf("%d",&n)! EOF){int i0;int j0;f…
阅读更多...
初识webpack（二）解析resolve、插件plugins、dev-server

初识webpack（二）解析resolve、插件plugins、dev-server

目录 (一)webpack的解析(resolve) 1.resovle.alias 2.resolve.extensions 3.resolve.mainFiles (二) plugin插件 1.CleanWebpackPlugin 2.HtmlWebpackPlugin 3.DefinePlugin (三)webpack-dev-server 1.开启本地服务器 2.HMR模块热替换 3.devServer的更多配置项 (…
阅读更多...
.NET高级面试指南专题七【SocketWebSocket】

.NET高级面试指南专题七【SocketWebSocket】

Socket&#xff08;套接字&#xff09;是一种在计算机网络中实现通信的一种机制&#xff0c;它提供了一种标准的接口&#xff0c;使不同计算机上的程序能够通过网络进行数据交换。Socket允许在网络中的不同设备之间建立连接&#xff0c;进行双向的数据传输。 Socket通常用于实现…
阅读更多...
Map和Set（哈希表）

Map和Set（哈希表）

目录 map&#xff1a; map说明&#xff1a; Map.Entry的说明&#xff1a;,v> Map 的常用方法: 演示&#xff1a; 注意&#xff1a; TreeMap和HashMap的区别 Set&#xff1a; 常见方法说明&#xff1a; 注意&#xff1a; TreeSet和HashSet的区别 哈希表: 冲突&a…
阅读更多...
FileZilla Server 1.8.1内网搭建

FileZilla Server 1.8.1内网搭建

配置环境服务器服务器下载服务器配置服务器配置 Server - ConfigureServer Listeners - Port 协议设置 Protocols settingsFTP and FTP over TLS(FTPS) Rights management(权利管理)Users(用户) 客户端建立连接 配置环境 服务器处于局域网内: 客户端 < -访问- > 公网 &l…
阅读更多...
车载软件架构 —— Adaptive AUTOSAR软件架构

车载软件架构 —— Adaptive AUTOSAR软件架构

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师&#xff08;Wechat&#xff1a;gongkenan2013&#xff09;。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 本就是小人物&#xff0c;输了就是输了&#…
阅读更多...
寒假思维训练day21

寒假思维训练day21

今天更新一道不错的状态压缩DP题&#xff0c;顺带总结一下状态压缩DP。 摘要&#xff1a; Part1 浅谈状态压缩DP的理解 Part2 浅谈对状态机DP的理解 Part3 关于状态压缩DP的1道例题 Part1 状态压缩DP 1、状态压缩DP&#xff1a; 事物的状态可能包含多个特征&#xff0c;…
阅读更多...
linuxqq关闭主面板后无法再次打开的问题

linuxqq关闭主面板后无法再次打开的问题

文章目录 前言解决方案强调一点 前言 听说QQ出了linux版&#xff0c;所以来试试。结果试试就逝世。这次记录一个关闭后没办法打开的解决办法。 解决方案 刚安装好后如果点了关闭&#xff0c;系统托盘里也没有&#xff0c;点击图标又是重新登录。当然&#xff0c;我们最简单、…
阅读更多...
浅谈Linux环境

浅谈Linux环境

冯诺依曼体系结构&#xff1a; 绝大多数的计算机都遵守冯诺依曼体系结构 在冯诺依曼体系结构下各个硬件相互配合处理数据并反馈结果给用户 其中控制器和运算器统称为中央处理器&#xff08;CPU&#xff09;&#xff0c;是计算机硬件中最核心的部分&#xff0c;像人类的大脑操控…
阅读更多...
最新文章

Copyright @ 2022~2023