当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Build tree from list of list

问题描述:

I have a list of list look like: {{f,h,i}, {b,e,f,g}, {a,b,c,d}}

I need to build a tree with the rule:

  • for each list the first element is the root.
  • rest of elements is the children.

for this example the tree look:

 a

b c d

e f g

h i

can you help me to write algo for this.

Thank!

网友答案:

It's a simple recursive procedure.

  1. If the list contains a list, first recursively deal with that list, then replace it with its first element (its root).

  2. Now the list contains only letters (representing nodes).

    a. Make the first letter a node.

    b. Sort the other elements smaller than the first letter. Chain them into a downward-right facing branch, and make the largest one a left child of the first letter.

    c. Similarly, sort the other elements larger than the first letter. Chain them into a downward-right facing branch, and make the smallest one a left child of the first letter.

In pseudocode:

def make_into_tree(l):
    for e in l:
        if type(e) == list:
            e = make_into_tree(e)

    root = e[0]

    smaller = sorted(all letters smaller than e[0])
    for each s in smaller (except for first):
        make s a right child of its predecessor
    smaller_root = smaller[0]
    make smaller_root left child of root

    larger = sorted(all letter larger than e[0])
    for each l in larger (except for first):
        make l a right child of its predecessor
    larger_root = smaller[0]
    make larger_root right child of root

    return root
分享给朋友:
您可能感兴趣的文章:
随机阅读: