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

Question

我们得到了一个二叉树，其中 中序线程 。意思是，如果一个节点没有左child（右child），左线程（右线程）从该节点链接到它的顺序前导（顺序继承者）。

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

TMI：我实际上需要这个pseudocode/algorithm来创建另一个算法来获得二叉树的后序后继。

Answer 1

从图片看来：

head节点是一个特殊的哨兵节点，只是作为附加实际树（可能为空）的哨兵节点
节点有两个额外的布尔标志来指示它们是否有 left/right child

那么查找给定节点的parent的逻辑可以如下：

在给定节点的子树中找到最右边的节点。
跟随该节点的 right-link 到祖先。我们知道原始节点在这个祖先节点的左子树中。
检查祖先的左child是否为原始节点。如果是这样，我们找到了 parent.
向左走child。我们知道原来的节点一定在这个节点下面的right-side路径上。找到它，然后return parent 我们必须在到达那里之前访问。

这是 JavaScript 中该想法的实现。此代码片段定义了一个 Node class。它创建示例中给出的树。 Node class 有一个 inorder 迭代器，我们用它来访问每个节点，然后使用上面的算法显示它的 parent：

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);
}

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

Given an inorder threaded binary tree and a node, how to find the parent of that particular node?

algorithm

tree

binary-tree

inorder

postorder