Batata - 6 months ago 58
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 :
``````

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 .

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:
return
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.

Source (Stackoverflow)