关于维基百科Day–Stout–Warren算法tree-to-vine伪代码的bug问询

问题发现 #

维基百科中用于平衡二叉搜索树（BST）的Day–Stout–Warren算法，其tree-to-vine伪代码存在缺陷：该步骤原本要将BST转换为以右指针连接的有序链表（“藤蔓”），但会跳过根节点的左子节点，导致根节点存在左子树时，转换后的链表会丢失这部分数据。

原伪代码 #

routine tree-to-vine(root)
    // Convert tree to a "vine", i.e., a sorted linked list,
    // using the right pointers to point to the next node in the list
    tail ← root
    rest ← tail.right
    while rest ≠ nil
        if rest.left = nil
            tail ← rest
            rest ← rest.right
        else
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            tail.right ← temp

修复后的伪代码 #

通过调整tail和rest指针的初始层级，新增head变量记录链表头节点，解决了原代码的问题：

routine tree-to-vine-fixed(root)
    head ← null
    tail ← null
    rest ← root

    while rest ≠ null
        if rest.left = null
            if tail = null
                // Set head to the minimum value of the tree (left-most node)
                head ← rest
            // No left child, move the tail and rest pointers forward
            tail ← rest
            rest ← rest.right
        else
            // Left child exists, perform rotations
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            if tail ≠ null
                tail.right ← temp

    return head

Java实现 #

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class DSW {
    public static TreeNode treeToVineFixed(TreeNode root) {
        TreeNode head = null, tail = null;  // 调整tail和rest的初始层级
        TreeNode rest = root;

        while (rest != null) {
            if (rest.left == null) {
                if (tail == null)  // 将head设为树的最小值节点（最左节点）
                    head = rest;
                // 无左子节点，移动tail和rest指针
                tail = rest;
                rest = rest.right;
            } else {
                // 存在左子节点，执行旋转操作
                TreeNode temp = rest.left;
                rest.left = temp.right;
                temp.right = rest;
                rest = temp;
                if (tail != null)  // 避免空指针异常
                    tail.right = temp;
            }
        }
        return head;
    }
}

测试用例 #

TreeNode root = new TreeNode(6);
root.left = new TreeNode(4);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right = new TreeNode(10);
root.right.left = new TreeNode(8);
root.right.right = new TreeNode(20);
root.right.left.left = new TreeNode(7);
root.right.left.right = new TreeNode(9);

System.out.println("Original Tree");
System.out.println(renderAsciiTree(root));

var head = treeToVineOriginal(root);  // 原算法实现未展示
System.out.println("Incorrect Vine");
System.out.println(renderAsciiTree(head));

var head = treeToVineFixed(root);
System.out.println("Vine");
System.out.println(renderAsciiTree(head));

遗漏点检查 #

目前的修复方案已覆盖核心问题，但可补充以下场景验证：

• 空树场景：传入null根节点时，方法是否正确返回null
• 单节点树：仅含根节点的树，转换后是否正确返回该节点作为链表头
• 极端结构树：左斜树（所有节点在左子树）或右斜树（所有节点在右子树），转换后的链表是否有序且无节点丢失
• 连续旋转场景：多次旋转操作下，tail指针指向是否始终正确，保证链表连贯性

内容的提问来源于stack exchange，提问作者Paul C