python – converting a string into a tree

python – converting a string into a tree

If I understand your goal accurately, all you need is a Binary Search Tree (BST) of strings.
Every Node of the tree will be a list of lists of the following format: [left_sub_tree, right_sub_tree, word]. The empty list will represent the null pointer

Lets implement the simple recursive procedure for inserting new values based on its lexicographical order (it is a default comparison order for strings in Python).

def insert(x, word):
    if len(x) == 0:
        return [[], [], word]
    if word < x[2]:
        x[0] = insert(x[0], word)
    elif x[2] < word:
        x[1] = insert(x[1], word)
    return x

Now, you can create a BST for your string like that:

tree = []
for w in string.split():
    tree = insert(tree, w)

The easiest way to see the structure is to print the tree level by level:

def print_tree(x, shift):
    if len(x) == 0:
        return
    print_tree(x[0], shift + 2)
    print   * shift, x[2]
    print_right(x[1], shift + 2)

print_tree(tree, 0)

FYI. The above procedure performs so called in-order traversal.

python – converting a string into a tree

Leave a Reply

Your email address will not be published. Required fields are marked *