Адресация узлов в дереве

Question

Существуют ли стандартные обозначения для адреса узлов в дереве?

Например, это мое домашнее обозначение:

 0 
    /\ 
    1 2 
/\ \ 
3 4 5 

Положение узлов могут быть решены следующим образом:

• Узел 0: 0
• Узел 1: 0,0
• Узел 3: 0,0,0
• Узел 4: 0,0,1
• Узел 2: 0,1
• Узел 5: 0,1,0

Дерево в диаграмме является бинарное дерево, но нужно решение для всех деревьев.

Answer 1

Я знаю, что это старо, но мне нужно было решить это сейчас. Решение, которое вы предлагаете в вопросе, прекрасно и прямолинейно обобщается на n-арное дерево.

Идея состоит в том, что адрес узла дерева представляет собой список индексов, каждый из которых является индексом на основе 0 в дочернем массиве узла на каждом уровне. Так, например, учитывая это более общее дерево:

 0 
    /| \ 
    1 2 3 
/\ /| \ 
4 5 6 7 8 

address(0) = []  // root is [] by definition 
address(1) = [0]  // root.children[0] 
address(2) = [1]  // etc 
address(3) = [2] 
address(4) = [0,0] // root.children[0].children[0] 
address(5) = [0,1] // etc 
address(6) = [2,0] 
address(7) = [2,1] 
address(8) = [2,2] // root.children[2].children[2] 

Другими словами, чтобы получить адрес для узла (в псевдокоде Javascript):

function addressForNode(node) { 
    if (!node.parent) return [] 
    var parent = node.parent 
    var siblings = parent.children 
    var index = indexOf(siblings, node) 
    return addressForNode(parent).unshift(index) 
} 

Для того, чтобы получить узел дан адрес и дерево (которое берется корневой узел):

function nodeWithAddress(tree, address) { 
    if (address == []) return tree 
    var childIndex = address.shift() 
    var childNode = tree.children[childIndex] 
    return nodeFrom(childNode, address) 
} 

Где indexOf(), unshift() и shift() работать как в JavaScript: indexOf() возвращает индекс элемента в массиве. unshift() добавляет элемент к фронту массива. shift() удаляет спереди и возвращает его.