有没有办法在树结构中添加指向父级的反向指针？

Question

我正在尝试创建一个看起来像二叉树的结构。我需要在哪里设置反向指针以便每个节点都可以链接到它的父节点，这对性能有何影响？

function Node(expression, trueStatement, falseStatement) {
    this.expression = expression;
    this.trueStatement = trueStatement
    this.falseStatement = falseStatement
    this.left = null;
    this.right = null;
    this.back = null;
}

function BinarySearchTree() {
    this.root = null;
}

BinarySearchTree.prototype.push = function(state, expression, trueStatement, falseStatement) {
    var root = this.root;

    if (trueStatement == "") {
        trueStatement = false;
    }
    if (falseStatement == "") {
        falseStatement = false;
    }

    if (!root) {
        this.root = new Node(expression, trueStatement, falseStatement);
        return;
    }



    var currentNode = root;
    var newNode = new Node(expression, trueStatement, falseStatement);

    while (currentNode) {
        if (state) {
            if (!currentNode.left) {
                currentNode.left = newNode;
                break;
            } else {
                currentNode = currentNode.left;
            }
        } else {
            if (!currentNode.right) {
                currentNode.right = newNode;
                break;
            } else {
                currentNode = currentNode.right;
            }
        }
    }

}
var bst = new BinarySearchTree();
bst.push(true, "IIF()", "", "@user");
bst.push(false, "IIF()1", "@user", "");
bst.push(true, "IIF()2", "@user", "");

目标是每个节点都应该链接到它们的父节点。

Answer 1

将属性 parent/back 添加到您的 Node 对象并在创建 Node 时填充。以及你在哪里

currentNode.left = newNode;

同时添加

 currentNode.left = newNode;
 newNode.back = currentNode;

在其他地方实现相同的逻辑

有没有办法在树结构中添加指向父级的反向指针？

Is there a possible way to add back pointer to parent in tree structure?

javascript

algorithm

binary-tree