给定一个有序线程二叉树和一个节点，如何找到该特定节点的父节点？

Question

我们得到了一个有序线程的二叉树。这意味着，如果一个节点没有左子节点（右子节点），左线程（右线程）将从该节点链接到其索引前一个节点（索引后一个节点）。

你能帮我找到一个节点的父节点的伪代码或算法吗？例如（见下图），给定的节点是Q，父节点必须是I。（我们应该利用给定的想法，即二进制是有序线程）

TMI：我实际上需要这个伪代码/算法来创建另一个算法，它将获得二叉树的后序继承者。

Answer 1

从图中可以看出：

• head节点是一个特殊的哨兵节点，仅用作连接实际树的哨兵节点（可能是空的）

然后，查找给定节点的父节点的逻辑可以如下所示：

• 在给定节点的子树中找到最右边的节点

下面是这个想法在JavaScript中的实现。此代码段定义了一个节点类。它创建了示例中给出的树。节点类有一个顺序迭代器，我们使用该迭代器访问每个节点，然后使用上述算法显示其父节点：

class Node {
    constructor(value=null, left=null, right=null) {
        this.value = value;
        this.hasLeft = false;
        this.hasRight = false;
        this.left = left || this; // Default is self-reference
        this.right = right || this; // Default is self-reference
    }
    insertLeft(value) {
        this.hasLeft = true;
        this.left = new Node(value, this.left, this);
        return this.left;
    }
    insertRight(value) {
        this.hasRight = true;
        this.right = new Node(value, this, this.right);
        return this.right;
    }
    parent() {
        // Find rightmost node of subtree
        let node = this;
        while (node.hasRight) {
            node = node.right;
        }
        node = node.right; // go to ancestor
        // The this-node is in the left subtree of node.
        if (node.left === this) return node;
        node = node.left;
        while (node.right !== this) {
            node = node.right;
        }
        return node;
    }
    * inorder() {
        if (this.hasLeft) yield * this.left.inorder();
        if (this.right !== this) yield this; // When it is not the head
        if (this.hasRight) yield * this.right.inorder();
    }
}

// Create the example tree:
let head = new Node(); // Sentinel node (without data)
head.insertLeft("C").insertLeft("I").insertLeft("Q").insertRight("U").right.right
                    .insertRight("S").insertLeft("K").right
                                     .insertRight("R").insertLeft("O").right
                                                      .insertRight("T");

// Visit each node, display its value and that of its parent:
for (let node of head.inorder()) {
    console.log("parent of " + node.value + " is " + node.parent().value);
}