二叉搜索树与双向链表(双向链表和二叉链表的区别)

导语：算法系列之双向链表和二叉搜索树

01 题目描述

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。举例如下图的二叉搜索树，转为双向链表。

树结构的定义如下

class BinaryTreeNode { int value; BinaryTreeNode leftChild; BinaryTreeNode rightChild; BinaryTreeNode(){ } BinaryTreeNode(BinaryTreeNode leftChild, BinaryTreeNode rightChild, int value){ this.leftChild = leftChild; this.rightChild = rightChild; this.value = value; }}

双向链表和树结构有着相同的结果，所以我们用leftNode表示链表的前一个节点。rightNode表示链表的下一个节点。

02 解题

看到此题，我们首先回忆一下二叉搜索树的性质

左孩子节点的值 < 根节点 < 右孩子节点，我们按照中序遍历得到的结果刚好就是有序的。

我们可以在中序遍历的同时，将二叉搜索树转换为双向链表吗？

现在我们尝试在遍历的过程中，将二叉搜索树转为双向链表。

1.首先循环遍找到第一个节点，最左节点4

当前被访问的变量currentNode=4；因为它是第一个节点，所以currentNode.leftNode=null;

下一个需要访问的节点还不确定，所以currentNode的rightNode不确定。

2.回退到节点6 currentNode=6

6的前一个节点(leftChild)是它的左孩子节点4.

那么对于下图这种情况，6的前一个节点应该是多少呢？读者考虑下

对于节点6的左子树来说，中序遍历的最后一个节点5，所以6的前一个节点（leftChild）应该是5。

思考下，怎么才能把6的leftChild指针，连到5上呢？

我们需要一个变量lastVisitNode记录上一次被访问到的节点，那么lastVisitNode=5或者4。

然后我们就可以方便的赋值了

currentNode.left=lastVisitNode;

lastVisitNode.right = currentNode.

3.在访问完节点6之后，6存在右孩子节点，所以此时应该访问6的右孩子节点8。

lastVisitNode=6；

currentNode=8；

currentNode.left=lastVisitNode;

lastVisitNode.right = currentNode. 将 6和8互连。

4. 8节点访问完，回到节点10. 重复同样的步骤

5.接下来访问12节点。10节点访问完，按照中序遍历，应该访问右孩子节点上的最左节点即12节点。 10的右孩子节点为12，12的右孩子节点为10

lastVisitNode = 10;

currentNode= 12;

执行连接操作

currentNode.left=lastVisitNode;

lastVisitNode.right = currentNode.

6.按照上述操作执行到将树节点访问完。

03 总结

通过上述步骤的分析当中，我们可以发现，对于一个节点A来说

最后一个被访问到的节点永远都是A的前一个节点。A.pre = lastVisitNode

最后一个被访问的节点的下一个节点时A. lastVisitNode.next = A;

遍历过程为中序遍历。

04 代码

转换代码public static BinaryTreeNode convert(BinaryTreeNode currentNode, BinaryTreeNode pLastVisitNode) { if (currentNode == null) { return null; } // 遍历最左节点 if (currentNode.leftChild != null) { pLastVisitNode = convert (currentNode.leftChild, pLastVisitNode); } // 更新当前节点的前一个节点为pLastVisitNode currentNode.leftChild = pLastVisitNode; if (pLastVisitNode != null) { pLastVisitNode.rightChild = currentNode; } // 更新最后一个被访问为当前节点。 pLastVisitNode = currentNode; // 访问右孩子节点 if (currentNode.rightChild != null) { pLastVisitNode = convert(currentNode.rightChild, pLastVisitNode); } return pLastVisitNode;}

调用代码：

public static BinaryTreeNode convertToDoublyLinked(BinaryTreeNode root) { BinaryTreeNode pHead = root; while (pHead.leftChild != null) { pHead = pHead.leftChild; } convert(root, null); return pHead;}

测试用例

 public static void main(String[] args) { // 边界一测试 =纯左子节点 BinaryTreeNode treeNode0 = new BinaryTreeNode(null, null, 0); BinaryTreeNode treeNode11 = new BinaryTreeNode(treeNode0, null, 1); BinaryTreeNode treeNode12 = new BinaryTreeNode(treeNode11, null, 2); BinaryTreeNode treeNode13 = new BinaryTreeNode(treeNode12, null, 3); BinaryTreeNode treeNode14 = new BinaryTreeNode(treeNode13, null, 4); BinaryTreeNode treeNode15 = new BinaryTreeNode(treeNode14, null, 5); BinaryTreeNode treeNode16 = new BinaryTreeNode(treeNode15, null, 6); BinaryTreeNode treeNode17 = new BinaryTreeNode(treeNode16, null, 7); BinaryTreeNode head = convertToDoublyLinked(treeNode17); // 边界2测试 纯右孩子节点 BinaryTreeNode treeNode27 = new BinaryTreeNode(null, null, 7); BinaryTreeNode treeNode26 = new BinaryTreeNode(null, treeNode27, 6); BinaryTreeNode treeNode25 = new BinaryTreeNode(null, treeNode26, 5); BinaryTreeNode treeNode24 = new BinaryTreeNode(null, treeNode25, 4); BinaryTreeNode treeNode23 = new BinaryTreeNode(null, treeNode24, 3); BinaryTreeNode treeNode22 = new BinaryTreeNode(null, treeNode23, 2); BinaryTreeNode treeNode21 = new BinaryTreeNode(null, treeNode22, 1); BinaryTreeNode treeNode01 = new BinaryTreeNode(null, treeNode21, 0); BinaryTreeNode head01 = convertToDoublyLinked(treeNode01); // 普通的二叉搜索树// BinaryTreeNode treeNode37 = new BinaryTreeNode(null, null, 7); BinaryTreeNode treeNode36 = new BinaryTreeNode(null, null, 16); BinaryTreeNode treeNode35 = new BinaryTreeNode(null, null, 12); BinaryTreeNode treeNode34 = new BinaryTreeNode(null, null, 8); BinaryTreeNode treeNode33 = new BinaryTreeNode(null, null, 4); BinaryTreeNode treeNode32 = new BinaryTreeNode(treeNode35, treeNode36, 14); BinaryTreeNode treeNode31 = new BinaryTreeNode(treeNode33, treeNode34, 6); BinaryTreeNode treeNode03 = new BinaryTreeNode(treeNode31, treeNode32, 10); BinaryTreeNode head02 = convertToDoublyLinked(treeNode03); }

本文内容由快快网络小快创作整理编辑！