有没有可能在树结构中添加返回到父级的指针的方法？

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;在其他地方实现相同的逻辑