将二进制搜索树转换为双向链表

首先，您需要了解二叉搜索树也是一种排序的数据结构，并且其中序遍历是一种不递减的顺序排列

因此，如果要转换为排序的双向链表，则只需更改指向左子节点和右子节点的原始指针，以便它们指向前节点和后节点，如图所示

调整指针

将原来指向左子节点的指针调整为指向链表中上一个节点的指针

指向右子节点的指针已调整为指向链表中下一个节点的指针

如何调整

请考虑根节点以及左右子树的基本情况，因为如果使用递归，则可以通过对左右子树应用相同的方法来考虑这种基本情况

对于这种基本情况，它可以分为三个部分. 根节点10，左子树和右子树. 所有需要做的就是将10与左子树中的最大值连接，然后将10与连接子树中的最小值连接

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

转换代码

公共静态BinaryTreeNode baseconvert（BinaryTreeNode根，BinaryTreeNode lastNode）{

如果（root == null）

返回lastNode;

BinaryTreeNode current = root;

如果（current.leftNode！= null）

lastNode = baseconvert（current.leftNode二叉排序树是，lastNode）；

current.leftNode = lastNode;

如果（lastNode！= null）

lastNode.rightNode =当前；

lastNode = current;

如果（current.rightNode！= null）

lastNode = baseconvert（current.rightNode，lastNode）；

返回lastNode;

}

关于为什么需要lastNode，

上面的代码中有两个参数，一个是根节点，另一个是转换后列表的最后一个节点. 由于二叉查找树中顺序遍历的特性，遍历到根节点时，左子树已经被排序，因此将有一个链表，其中左子树已被转换，而最后一个子树已被转换. 链表是我们需要连接到左侧根节点的节点

关于为什么需要lastNode的情况，假设当前节点的左子树按顺序排列，则lastNode应该是左子树的最大节点（即，左子树的右子的右子）直到没有合适的子节点为止，再加上合适的子节点. ）在不保存lastNode的情况下，很难找到当前节点左子树的最大节点.

要注意的另一件事是lastNode指向排序的双链表的尾节点（该尾节点的预指向已完成，而右节点尚未处理. ）

在一开始，lastNode为空

current是当前子树的根节点

如果存在左子树，则转换左子树并递归. 递归返回后，这意味着找到链表的第一个节点，即4的节点，而将4的前一个节点设置为null. 这时，当前是4的节点. 这时，由于遍历了6和4的左子树，因此需要返回上一层. 返回之前，需要将电流分配给lastNode，指示4的左子树的最后一个节点为4

由于向上返回一个图层，此时的当前已经是6，并且将左节点6分配给了之前返回的4，以确定之前返回的lastNode是否为null，并且不为空，指示根节点和lastNode已连接. 实际上，当lastNode为null时，仅第一个节点会出现，而在其他时间不会出现. 现在对6和6本身的左子树进行了排序，因此此时的lastNode为6

6和4之间的双向连接已完成. 由于右子树6存在，它将递归地转到右子树. 由于8没有左右子树，因此当前是递归到下一级后的8节点，但是它的左子节点为空，因此不会在左递归. 将8的左连接连接到上一个lastNode以建立双向连接. 然后，由于lastNode不为空，因此将lastNode的右连接连接到8. 现在，建立了双向连接，并且lastNode为8

已对468进行了排序. 此时，lastNode为8，并返回到上一层，即根节点10. 在此层，current为10，并且current的左连接连接到lastNode. 如果存在lastNode，则将lastNode的最后一个连接与10个连接连接以建立双向连接. 此时，将根节点和左子树连接起来，然后转换右子树. 当前的lastNode为10，当前的为14，而14有一个左子节点二叉排序树是，因此它需要递归到下一层，即下一层的当前. 因为12、12没有左子节点，所以不需要递归地坐着，所以12是12个子树的最左节点，转换为双向链表，将lastNode连接到12，即10和12，然后lastNode变为12，然后递归12的右边子树，因为没有正确的子树，因此它直接返回到上层. 上层的电流为14、14连接到有序的lastNode，即连接12和14，然后lastNode变为14，递归到14的右子树，然后电流变为16，递归到左子树，无左子树，连接16和14，然后lastNode变为16，递归右子树，没有右子树，因此整个递归工作已完成

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-215660-1.html