在树本身内重新排序二叉查找树

Question

如果给我一个无序的二叉树，那么在不创建新树的情况下对它进行排序的最佳方法是什么？当我说排序时，我的意思是左子树中的所有节点都小于根节点，而右子树中的所有节点都大于根节点。

我很欣赏将无序二叉树变成二叉树的最最佳方法是提取所有节点，然后将它们插入到新树中，但是是否有另一种方法涉及切换原始树中节点的位置，可以通过算法完成？

Answer 1

创建新树的方法当然是要走的路，但作为一种练习，可以就地对二叉树进行排序。

例如，您可以实现冒泡排序，这样所有节点都保持不变，但它们的值会在此过程中交换。

为此，您需要实现按顺序遍历。然后继续重复完整的无序遍历，其中比较两个连续访问的节点的值，如果它们的顺序不正确，则交换它们的值。当顺序遍历不会导致至少一次交换时，将对树进行排序，并且该过程可以停止。

下面是一个JavaScript实现:

它首先生成一个树，其中包含 10 个节点，其随机无符号整数小于 100。树的形状也是随机的（基于每次插入时提供的随机“路径”）

然后如上所述对树进行排序。由于JavaScript支持生成器和迭代器，所以我使用了这种语法，但也可以用回调系统来实现。

它以非常基本的方式显示树（旋转90°，即根在左侧），因为它是在排序操作之前和之后。

class Node {
    constructor(value) {
        this.value = value;
        this.left = this.right = null;
    }
}

class Tree {
    constructor() {
        this.root = null;
    }
    // Method to add a value as a new leaf node, using the 
    //   binary bits in the given path to determine 
    //   the leaf's location:
    addAtPath(value, path) {
        function recur(node, path) {
            if (!node) return new Node(value);
            if (path % 2) {
                node.right = recur(node.right, path >> 1);
            } else {
                node.left = recur(node.left, path >> 1);
            }
            return node;
        }
        this.root = recur(this.root, path);
    }
    *inorder() {
        function* recur(node) {
            if (!node) return;
            yield* recur(node.left);
            yield node;
            yield* recur(node.right);
        }
        yield* recur(this.root);
    }
    toString() {
        function recur(node, indent) {
            if (!node) return "";
            return recur(node.right, indent + "   ")
                 + indent + node.value + "\n"
                 + recur(node.left, indent + "   ");
        }
        return recur(this.root, "");
    }
    bubbleSort() {
        let dirty = true;
        while (dirty) {
            dirty = false;
            let iterator = this.inorder();
            // Get first node from inorder traversal
            let prevNode = iterator.next().value;
            for (let currNode of iterator) { // Get all other nodes
                if (prevNode.value > currNode.value) { 
                    // Swap
                    const temp = prevNode.value;
                    prevNode.value = currNode.value;
                    currNode.value = temp;
                    dirty = true;
                }
                prevNode = currNode;
            }
        }
    }
}

// Helper
const randInt = max => Math.floor(Math.random() * max);

// Demo:
const tree = new Tree();
for (let i = 0; i < 10; i++) {
    tree.addAtPath(randInt(100), randInt(0x80000000));
}
console.log("Tree before sorting (root is at left, leaves at the right):");
console.log(tree.toString());
tree.bubbleSort();
console.log("Tree after sorting:");
console.log(tree.toString());