17 将二叉排序树转换为有序双链表

2024-05-28 15:48

本文主要是介绍17 将二叉排序树转换为有序双链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

这里写图片描述

思路

思路 : 因为要将二叉排序树更新各个结点的引用更新为一个有序双链表, 所以必然需要将左子树的最大结点 和根节点和 右子树的最小结点连在一起, 这样的话将左右子树看成一个整体, 整个链表就变成了”左子树 - 根节点 - 右子树”, 有序, 然后对于左右子树递归处理

参考代码

/*** file name : Test10BinarySortedTreeAndSortedLinkedList.java* created at : 5:36:06 PM Jun 7, 2015* created by 970655147*/package com.hx.test05;import com.hx.test04.Test17BinarySortTree.BinarySortTree;
import com.hx.test04.Test17BinarySortTree.Node;
import com.hx.util.Log;public class Test10BinarySortedTreeAndSortedLinkedList {// 将一颗二叉排序树 转化为一个有序双链表public static void main(String []args) {BinarySortTree bst = new BinarySortTree();int[] data = new int[] {10, 6, 14, 4, 8, 12, 16 };for(int i=0; i<data.length; i++) {bst.add(data[i]);}Log.log(bst.toString() );Log.horizon();//      Log.log(bst);transferBinarySortedTreeToSortedLinkedList(bst.root() );Node head = getMinNode(bst.root(), bst.root() );Node tmp = head;while(tmp != null) { Log.log(tmp);tmp = tmp.getRight();}Log.horizon();}// 先更新各个结点的指向// 最后 特殊处理  max.right, min.leftpublic static void transferBinarySortedTreeToSortedLinkedList(Node node) {transferBinarySortedTreeToSortedLinkedList0(node);getMaxNode(node, node).setRight(null);getMinNode(node, node).setLeft(null);}// 思路 : 获取node左边的最大的结点, 以及node右边的最小的结点// 设置这三个结点的关系, node.left = leftMax, node.right = rightMin, leftMax.right = node, rightMin.left = node// 如果leftMax 不为left  则递归transferBinarySortedTreeToSortedLinkedList0// 如果rightMax 不为right   则递归transferBinarySortedTreeToSortedLinkedList0private static void transferBinarySortedTreeToSortedLinkedList0(Node node) {if(node == null) {return ;}Node left = node.getLeft(), right = node.getRight();Node leftMax = getMaxNode(node.getLeft(), node);Node rightMin = getMinNode(node.getRight(), node);node.setLeft(leftMax);if(leftMax != null) {leftMax.setRight(node);}node.setRight(rightMin);if(rightMin != null) {rightMin.setLeft(node);}if((left != null) && (left != leftMax) ) {transferBinarySortedTreeToSortedLinkedList0(left);}if((right != null) && (right != rightMin) ) {transferBinarySortedTreeToSortedLinkedList0(right);}}// 获取node节点下最小的结点   并且不能小于unexpectedprivate static Node getMinNode(Node node, Node unexpected) {if(node == null) {return null;}Node tmp = node;while(tmp.getLeft() != null && tmp.getLeft() != unexpected) {tmp = tmp.getLeft();}return tmp;}// 获取node节点下 最大的结点   并且不能超过unexpectedprivate static Node getMaxNode(Node node, Node unexpected) {if(node == null) {return null;}Node tmp = node;while(tmp.getRight() != null && tmp.getRight() != unexpected) {tmp = tmp.getRight();}return tmp;}}

效果截图

这里写图片描述

总结

再一次巧妙的利用了递归。。

注 : 因为作者的水平有限,必然可能出现一些bug, 所以请大家指出!

这篇关于17 将二叉排序树转换为有序双链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

利用Python脚本实现批量将图片转换为WebP格式

《利用Python脚本实现批量将图片转换为WebP格式》Python语言的简洁语法和库支持使其成为图像处理的理想选择,本文将介绍如何利用Python实现批量将图片转换为WebP格式的脚本,WebP作为... 目录简介1. python在图像处理中的应用2. WebP格式的原理和优势2.1 WebP格式与传统

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

在Java中将XLS转换为XLSX的实现方案

《在Java中将XLS转换为XLSX的实现方案》在本文中,我们将探讨传统ExcelXLS格式与现代XLSX格式的结构差异,并为Java开发者提供转换方案,通过了解底层原理、性能优势及实用工具,您将掌握... 目录为什么升级XLS到XLSX值得投入?实际转换过程解析推荐技术方案对比Apache POI实现编程

Python使用FFmpeg实现高效音频格式转换工具

《Python使用FFmpeg实现高效音频格式转换工具》在数字音频处理领域,音频格式转换是一项基础但至关重要的功能,本文主要为大家介绍了Python如何使用FFmpeg实现强大功能的图形化音频转换工具... 目录概述功能详解软件效果展示主界面布局转换过程截图完成提示开发步骤详解1. 环境准备2. 项目功能结

使用Python实现网页表格转换为markdown

《使用Python实现网页表格转换为markdown》在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,本文将使用Python编写一个网页表格转Markdown工具,需... 在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,以便在文档、邮件或

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr