Batata Batata - 8 months ago 66
Python Question

converting a string into a tree

I want to convert a given string into a tree according to the Python's lexicographic order of strings as the order string , where each word will be compared with next word (root not included ) . That is, a word w is inserted or searched in the left subtree of a node [lefttree, righttree, word] if the comparison w

strings will be like this :
string = "sad adsa dqwe fdsf erwa"

I did not do anything so far , but i have an idea , which is by splitting the given string string.split , assign the first word as a root and for the next words check recursively if the condition returns True .

Answer Source

If I understand your goal accurately, all you need is a Binary Search Tree (BST) of strings. The simple way to create it is the following. Start with a simple class that represents the node of the tree:

class Node:
    def __init__(self, word):
        self.word = word
        self.left, self.right = None, None

Than 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 x is None:
        return Node(word)
    if word < x.word:
        x.left = insert(x.left, word)
    elif x.word < word:
        x.right = insert(x.right, word)
    return x

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

tree = None
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 x is None:
    print_tree(x.left, shift + 2)
    print " " * shift, x.word
    print_right(x.right, shift + 2)

print_tree(tree, 0)

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