Блог

Нам дается двоичное дерево с упорядоченными потоками. Это означает, что если у узла нет левого дочернего элемента (правого дочернего элемента), левые потоки (правые потоки) связаны с этим узлом с его предшественником по порядку (преемником по порядку).

Можете ли вы помочь мне придумать псевдокод или алгоритм, который нашел бы родителя узла? Например (см. фото ниже), данный узел-Q, родителем должен быть I. (Предполагается, что мы должны использовать данную идею о том, что двоичный файл упорядочен по потоку)

TMI: Мне действительно нужен этот псевдокод/алгоритм для создания другого алгоритма, который получил бы преемника двоичного дерева после заказа.

Судя по картинке, кажется, что:

• head узел-это специальный сторожевой узел, который просто служит сторожевым узлом для прикрепления фактического дерева (которое может быть пустым).
• узлы имеют два дополнительных логических флага, указывающих, есть ли у них левый/правый дочерний элемент

Тогда логика поиска родителя данного узла может быть следующей:

• Найдите самый правильный узел в поддереве данного узла.
• Перейдите по правой ссылке этого узла к предку. Мы знаем, что исходный узел находится в левом поддереве этого узла-предка.
• Проверьте, является ли левый дочерний элемент предка исходным узлом. Если это так, то мы нашли родителя.
• Идите к левому ребенку. Мы знаем, что исходный узел должен находиться на правом пути ниже этого узла. Найдите его и верните родителя, которого мы должны были посетить, прежде чем попасть туда.

Вот реализация этой идеи в JavaScript. Этот фрагмент кода определяет Node класс. Он создает дерево, приведенное в примере. В Node классе есть inorder итератор, который мы используем для посещения каждого узла, а затем отображения его родительского элемента с помощью описанного выше алгоритма:

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