CODEWITHSUNDEEP
tree
alexbirkett
alexbirkett

Reputation: 2682

Addressing nodes in a tree

Are there any standard notations to address nodes in a tree?

For example, this is my homemade notation:

     0
    / \
   1   2
  / \   \
 3   4   5

The position of the nodes could be addressed as follows:

The tree in the diagram is a binary tree, but I need a solution for all trees.

Upvotes: 0

Views: 1194

Answers (1)

danh
danh

Reputation: 62676

I know this is old, but I needed to solve this just now. The solution you suggest in the question is fine and straight-forwardly generalizable to an n-ary tree.

The idea is that an address of a tree node is a list of indexes where each is a 0-based index into a node's children array at each level. So for example, given this more general tree:

       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]

In other words, to get an address for a node (in pseudo 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)
}

To get a node given an address and a tree (which is taken to be the root node):

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

Where indexOf(), unshift() and shift() operate as in javascript: indexOf() returns the index of an element in an array. unshift() appends an element to the front of an array. shift() removes from the front and returns it.

Upvotes: 1

Related Questions