二叉搜索树转化为双向链表

Yangyang 发布于2019-08-16 12:45 / 1500人阅读

摘要：首先需要明白二叉搜索树也是一种排序的数据结构，它的中序遍历就是一个不递减的顺序排列所以如果要转换成一个排序好的双向链表，那么仅需要改变原来指向左子节点和右子节点的指针，让他们分别指向前节点和后节点即可，如图所示调整指针原先指向左子节点的指针

首先需要明白二叉搜索树也是一种排序的数据结构，它的中序遍历就是一个不递减的顺序排列

所以如果要转换成一个排序好的双向链表，那么仅需要改变原来指向左子节点和右子节点的指针，让他们分别指向前节点和后节点即可，如图所示

调整指针

原先指向左子节点的指针调整为链表中指向前一个节点的指针

原先指向右子节点的指针调整为链表中指向后一个节点的指针

如何调整

考虑根节点和左右子树的根本情况，因为如果用递归，这种根本情况考虑就可以去将同样的方法用到左右子树上

对于这种基本情况，可以分成三个部分来看，根节点10，左子树，右子树，需要做的就是将10与左子树中的最大值连起来，然后把10与右子树中的最小值连起来

现在有个问题就是我们并不知道左子树中的最大值和右子树中的最小值，如果我们知道就好了。但是想到递归，递归到左子树中，如果左子树已转换为双向链表，那么双向链表的最后一个节点就是我们想要的，而右子树中的第一个节点也是我们想要的

转换代码

public static BinaryTreeNode baseconvert(BinaryTreeNode root, BinaryTreeNode lastNode) {

if (root == null)

return lastNode;

BinaryTreeNode current = root;

if (current.leftNode != null)

lastNode=baseconvert(current.leftNode, lastNode);

current.leftNode = lastNode;

if (lastNode != null)

lastNode.rightNode = current;

lastNode = current;

if (current.rightNode != null)

lastNode=baseconvert(current.rightNode, lastNode);

return lastNode;

}

至于为什么需要一个lastNode，

上面的代码中有两个参数，一个是根节点，一个是已经转换好的链表的最后一个节点，因为二叉搜索树中序遍历的特性，当遍历到根节点的时候，左子树已经排好序了，所以会有一个左子树已经转换好的链表，而这个链表的最后一个节点即是我们需要和根节点左连的节点

至于为什么需要一个lastNode，假设当前节点的左子树都排好序，那么现在lastNode应该是左子树的最大节点（也就是左子树的右儿子的右儿子的右儿子直到没有右儿子的那个节点。）如果不保存lastNode找到当前节点的左子树的最大节点是不容易的。

另外需要说明的是lastNode指向的是已经排好序的双向链表的尾节点（这个尾节点的pre已经指向完毕了，右节点还没处理好。）

最开始的时候lastNode为null

current为当前子树的根节点

如果左子树存在，那么转换左子树，递归下去，递归返回之后，说明找到了链表的第一个节点，也就是4那个节点，将4的前面节点置为null，此时current为4那个节点，这个时候由于6的4这个左子树已遍历完了，所以需要往上层返回，返回之前需要将current赋值给lastNode，说明4这个左子树的最后一个节点就是4

由于往上返回了一层，此时的current已经是6了，将6的左节点赋值为之前返回的4，判断之前返回的lastNode是否为null，不为空说明需要把根节点和lastNode连起来，其实lastNode为null的情况就只有第一个节点会出现，其他的时候都不会出现。现在已排好序的包括6的左子树以及6本身了，所以此时的lastNode为6

6和4的双向连接就完成了，由于6的右子树存在，又会递归到右边子树去，由于8不存在左右子树，递归下去一层之后current就是8这个节点，但它的左孩子为空，所以不会左边递归下去，将8的左连接与之前的lastNode连接起来，建立双向连接的一条连接，然后由于lastNode不为空，所以又把lastNode的右连接与8连接起来，至此双向连接建立，此时lastNode为8

所以468都已排好序，此时lastNode为8，返回到上一层，也就是根节点10了，在这一层current为10，将current的左连接与lastNode连接起来，如果lastNode存在，将lastNode的右连接与10连接一起，以此建立双向连接。至此就将根节点和左子树都连接起来了，然后就是去转换右子树，现在的lastNode为10，current为14，14有左孩子，所以需要递归到下一层，下一层的current为12，12没有左孩子，所以不用在坐递归，所以12是12这棵子树转换成双向链表的最左边的节点，将lastNode与12连接，也就是10与12连接，此时的lastNode就变成了12，再将12的右子树递归，由于没有右子树，所以直接返回到上一层，上一层的current是14,14与已排好序的lastNode连接，也就是12与14连接，然后lastNode变为14，递归到14的右子树，也就current变为16，16再递归左子树，无左子树，将16与14连接，此时的lastNode变为16，递归右子树，无右子树，所以整个递归工作完成

云服务器 GPU服务器二叉链表双向链表二叉树转链表java 二叉树排序树规则

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71650.html

这几道Java集合框架面试题在面试中几乎必问

摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

bigdevil_s 2019-08-19 11:01 评论0 收藏0
【刷算法】二叉搜索树与双向链表

摘要：题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。分析如果是这样一棵二叉搜索树： showImg(https://segmentfault.com/img/remote/14600000...

FreeZinG 2019-08-22 18:32 评论0 收藏0
javascript数据结构

摘要：数据结构栈一种遵从先进后出原则的有序集合队列遵从先进先出原则的有序项优先队列修改版的队列，设置优先级循环队列基于队列，克服假溢出想象的队列。这种数据结构非常方便，提供了一个便利的语法来访问它的元素。 javascript数据结构栈一种遵从先进后出原则的有序集合队列遵从先进先出原则的有序项优先队列修改版的队列，设置优先级循环队列基于队列，克服‘假溢出’想象的队列。例如队列...

desdik 2019-08-23 13:50 评论0 收藏0
二叉树那些事儿

摘要：大家在聊到二叉树的时候，总会离不开链表。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。存储结构线性表主要由顺序表示或链式表示。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。大家在聊到二叉树的时候，总会离不开链表。这里先带大家一起了解一些基本概念。线性表概念线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关...

Little_XM 2019-08-22 16:28 评论0 收藏0
「中高级前端」窥探数据结构的世界- ES6版

摘要：单链表与双向链表单链表是表示一系列节点的数据结构，其中每个节点指向列表中的下一个节点。且分别称为该结点的左子树与右子树。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。1. 什么是数据结构？数据结构是在计算机中组织和存储数据的一种特殊方式，使得数据可以高效地被访问和修改。更确切地说，数据结构是数据值的集合，表示数据之间的关系，也包括了作用在数据上...

Lucky_Boy 2019-05-22 10:29 评论0 收藏0