|
|
| Line 1: |
Line 1: |
| | | | |
| − | for any node in the tree, there are two possibilities
| |
| − | # either the diameter is contained in one of the subtrees
| |
| − | # or the node itself is at the top of the longest path in the tree that defines the diameter
| |
| − |
| |
| − | in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node
| |
| − |
| |
| − | the following algorithm calculates the diameter in <math>O(n)</math> time
| |
| − |
| |
| − | <source lang="python">
| |
| − |
| |
| − | class Node:
| |
| − |
| |
| − | def __init__(self, value, children):
| |
| − | self.value = value
| |
| − | self.children = children
| |
| − |
| |
| − | @classmethod
| |
| − | def preorder(cls, lists):
| |
| − | return cls(
| |
| − | lists[0],
| |
| − | [cls.preorder(l) for l in lists[1:]]
| |
| − | )
| |
| − |
| |
| − |
| |
| − | def dd(root):
| |
| − | """
| |
| − | returns depth, diameter for tree with given root node
| |
| − |
| |
| − | >>> dd(Node.preorder([0, [1], [2]]))
| |
| − | (1, 2)
| |
| − | >>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
| |
| − | (2, 4)
| |
| − | >>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
| |
| − | (4, 5)
| |
| − | """
| |
| − | d1 = d2 = -1
| |
| − | md = 0
| |
| − | for child in root.children:
| |
| − | depth, diameter = dd(child)
| |
| − | if diameter > md:
| |
| − | md = diameter
| |
| − | if depth >= d1:
| |
| − | d2 = d1
| |
| − | d1 = depth
| |
| − | elif depth > d2:
| |
| − | d2 = depth
| |
| − | return d1 + 1, max(md, d1 + d2 + 2)
| |
| − |
| |
| − |
| |
| − | if __name__ == "__main__":
| |
| − | import doctest
| |
| − | doctest.testmod()
| |
| − |
| |
| − | </source>
| |
