本文共 3965 字，大约阅读时间需要 13 分钟。

二叉搜索树（BST）转换为双向链表是一项经典的数据结构转换题目本质上要求我们模擬操作过程，通过调整现有节点指针实现转换，而不是创建新的节点。正因如此，我们需要找到一种方法，利用二叉搜索树内部已有的结构特点，将其转换为一个有序的双向链表。

从二叉搜索树的性质来看，根节点的左子树全为小于根节点的值，右子树全为大于根节点的值。在这个转换过程中，左邻居节点实际上是该节点左子树中最大的节点，而右邻居节点则是该节点右子树中最小的节点。因此，我们需要从每个节点出发，分别向左和向右寻找这些特殊的邻居节点。

通过递归的方式，我们可以实现这一点。具体步骤如下：

接下来我们可以通过函数递归来实现上述逻辑。具体代码如下：

public class BSTreeNode {    private int value;    private BSTreeNode left;    private BSTreeNode right;    public BSTreeNode(int value) {        this.value = value;    }    public int getValue() {        return value;    }    public BSTreeNode getLeft() {        return left;    }    public BSTreeNode getRight() {        return right;    }    public void setLeft(BSTreeNode left) {        this.left = left;    }    public void setRight(BSTreeNode right) {        this.right = right;    }}public class BSTree {    public BSTreeNode bstree;    public BSTreeNode getDualLinkedList(BSTreeNode bst) {        if (bst == null) {            return null;        }        tree2List(bst);        return getMinNode(bst);    }    private void tree2List(BSTreeNode node) {        if (node == null) {            return;        }        // 左子树处理        if (node.left != null) {            tree2List(node.left);            node.left.right = node;            node.setLeft]]== node.left;        }        // 右子树处理        if (node.right != null) {            tree2List(node.right);            node.right.left = node;            node.setRight]] = node.right;        }    }    private BSTreeNode getMinNode(BSTreeNode node) {        if (node == null) {            return null;        }        // 找出右子树的最小值节点        BSTreeNode minNode = null;        while (node.left != null) {            minNode = node.left;            node = node.left;        }        return minNode;    }    private BSTreeNode getMaxNode(BSTreeNode node) {        if (node == null) {            return null;        }        // 找出左子树的最大值节点        BSTreeNode maxNode = null;        while (node.right != null) {            maxNode = node.right;            node = node.right;        }        return maxNode;    }    public void printDualList(BSTreeNode head) {        if (head == null) {            System.out.println("双向链表为空");            return;        }        System.out.println("顺序遍历：");        while (head != null) {            System.out.print(head.value + " ");            head = head.right;        }        System.out.println();        System.out.println("逆序遍历：");        while (head != null) {            System.out.print(head.value + " ");            head = head.left;        }        System.out.println();    }    public static void main(String[] args) {        BSTree tree = new BSTree();        BSTreeNode root = new BSTreeNode(10);        tree.bstree = root;        BSTreeNode left1 = new BSTreeNode(6);        BSTreeNode left2 = new BSTreeNode(4);        BSTreeNode left3 = new BSTreeNode(8);        BSTreeNode right1 = new BSTreeNode(14);        BSTreeNode right2 = new BSTreeNode(12);        BSTreeNode right3 = new BSTreeNode(16);        root.left = left1;        root.right = right1;        left1.left = left2;        left1.right = left3;        right1.left = right2;        right1.right = right3;        // 按照前序遍历打印二叉搜索树        System.out.println("二叉搜索树的前序遍历结果：");        printBSTree(root);        // 将二叉搜索树转换为双向链表        BSTreeNode listHead = tree.getDualLinkedList(root);        tree.printDualList(listHead);    }    private void printBSTree(BSTreeNode node) {        if (node == null) return;        printBSTree(node.left);        System.out.println(node.value + " ");        printBSTree(node.right);        System.out.println();    }}

核心算法解析

• 递归处理左子树：首先处理当前节点的左子树，找到其中值最大的节点，将其作为当前节点的左邻居。
• 递归处理右子树：然后处理当前节点的右子树，找到其中值最小的节点，将其作为当前节点的右邻居。
• 双向链表构建：通过递归调整左右指针，将二叉搜索树转换为双向链表。

这种方法充分利用了二叉搜索树的性质，在不创建新节点的情况下，通过调整现有节点的指针完成转换。这种转换方法的时间复杂度与二叉搜索树的遍历相当，具有一定的效率优越性。

转载地址：http://mfciz.baihongyu.com/