博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
二叉树进阶之搜索二叉树的判断与找出搜索二叉树中出错的结点
阅读量:6527 次
发布时间:2019-06-24

本文共 2560 字,大约阅读时间需要 8 分钟。

转载请注明原文地址: 

    搜索二叉树

   树的每个结点:左儿子比当前结点小,右结点比当前结点大,则该树为搜索二叉树。

   搜索二叉树有很多种实现:常见的有BST二叉查找树、平衡搜索二叉树(AVL树)、红黑树,这些数据结构通过不同的特性约束使得数据的存储和查抄更高效。这里不再展开。

   观察发现,搜索二叉树的中序遍历结果,是一个 递增的序列。

   由此,判断一棵树是否为搜索二叉树的方法就简单了:中序遍历这个树,每次遍历一个结点时与上一个遍历结点值比较,如果小于上一个遍历的结点则说明树不是二叉搜索树,返回false,终止遍历。

public boolean chk(TreeNode root) {        //用一个map来保存上一次遍历时的结点值,遍历过程中通过同一个key不断修改最新的pre值        Map
pre_map=new HashMap
(); Stack
nodes=new Stack
(); nodes.push(root); //中序遍历二叉树 while(!nodes.isEmpty()){ //循环处理左子树 while(root!=null){ root=root.left; if(root!=null) nodes.push(root); } //左子树入栈完毕,开始处理栈顶 root=nodes.pop(); //第一个弹出的结点,存入map if(pre_map.size()<1){ pre_map.put("pre",root.val); }else{ //后面弹出的结点与map保存的前一遍历结点值比较 int pre_val=pre_map.get("pre"); if(root.val

 

    如果明确给出一棵搜索二叉树的根节点root,现在这棵树中两个结点交换了位置使得该树不是搜索二叉树了(递增性被破坏)。求出这两个错位的结点?

    我们知道,搜索二叉树的中序遍历序列是有序的递增序列,比如:1 2 3 4 5 6 7

    现在假设两结点交换了位置,使得中序遍历结果为:1 2 6 4 5 3 7。我们可以发现,3与6所在结点发生了交换,使得序列不是单纯递增,而是出现了两个逆序对:6 45 3。并且交换位置的两数6、3分别是两逆序对的 较大者  与  较小者。

    所以,从出错的搜索二叉树中找到交换了位置的两个结点的简单思路就是:中序遍历这棵二叉树,在遍历过程中找出逆序对(后一元素大于前一元素):

                                                                                如果只有一个逆序对,则发生交换的结点就是这个逆序对的两个元素;

                                                                                如果有两个逆序对,那么发生交换的两个结点就是:第一个逆序对的较大者  与  第二个逆序对的较小者

    (注意:因为只有两个出错结点,所以无论是一个逆序对还是两个逆序对:我们默认只有一个逆序对,找到后存到数组中,当有第二个逆序对出现时,只需把数组中第二个元素改成第二逆序对中的小者就行了。)

public int[] findError(TreeNode root) {        int[] res=new int[2];        TreeNode[] errornodes=new TreeNode[2];        Stack
stack=new Stack
(); stack.push(root); TreeNode prenode=null; while(!stack.isEmpty()){ while(root!=null){ root=root.left; if(root!=null){ stack.push(root); } } root=stack.pop(); if(prenode!=null && prenode.val>root.val){ //第一次出现逆序对时,存在了errornodes[]中。如果有第二个逆序对的出现,那么第二个逆序对的小者(后者)为错误结点,前者不用保存 errornodes[0]=(errornodes[0]==null?prenode:errornodes[0]); errornodes[1]=root; } //修改前继结点,作为下一出栈的结点的前继结点 prenode=root; root=root.right; if(root!=null){ stack.push(root); } } //找到出错的结点后,输出结点值时它们交换回来再输出! res[0]=errornodes[1].val; res[1]=errornodes[0].val; return res; }

 

你可能感兴趣的文章
java基础学习总结——IO流
查看>>
iOS获取APP ipa 包以及资源文件
查看>>
CentOS 7 关闭启动防火墙
查看>>
Vue-选项卡切换
查看>>
linux网络命令
查看>>
nodejs ejs 请求路径和静态资源文件路径
查看>>
C++小代码
查看>>
记一次思维转变的时刻
查看>>
STL - Map - 运行期自定义排序
查看>>
Oil Deposits
查看>>
poj3984 迷宫问题(简单搜索+记录路径)
查看>>
Linux 服务器buff/cache清理
查看>>
算法试题 及其他知识点
查看>>
php课程---Json格式规范需要注意的小细节
查看>>
hadoop hdfs notes
查看>>
Java反射机制详解(3) -java的反射和代理实现IOC模式 模拟spring
查看>>
(2编写网络)自己动手,编写神经网络程序,解决Mnist问题,并网络化部署
查看>>
【转】如何使用分区助手完美迁移系统到SSD固态硬盘?
查看>>
NIO框架入门(四):Android与MINA2、Netty4的跨平台UDP双向通信实战
查看>>
ios兼容iphonex刘海屏解决方案
查看>>