Python Forum
Binary tree for words and simbols
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Binary tree for words and simbols
#1
Essence of the question
construct a binary tree in which the cells would represent 1 letter from the word. but only with one slightly illogical detail.

Here is an example of a tree that should be made up: https://i.imgur.com/DVzakd3.png

in the beginning there was added 'test', then 'term'. and as you can see, r should go not after e, but after s. if now add the word 'tell' there - the letter l will go to the rith-child from r.

here's my code: https://hastebin.com/sohozozaho.py

the problem is immediately noticeable by the fact that when the tree is displayed, 1 symbol is displayed. that is, the tree does not want to write anywhere except at the root. I tried to use debug in PyCharm - I still do not understand where I made a mistake.
Reply
#2
Okay, I'll try again. I did smething, and now it makes tree, but not correct.
[Image: rEtP4hf.png]
here is all code. just in case
class Node:
    def __init__(self, value=None, left_child=None, right_child=None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child
        self.isword = ''


class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, word):
        char_list = list(word)
        if self.root is None:
            self.root = Node(char_list[0])
            del char_list[0]
        end_node = self._insert(char_list, self.root)
        end_node = word

    def _insert(self, char_list, cur_node):
        for char in char_list:
            if cur_node.value is None:
                cur_node.value = char
                del char_list[0]
                if len(char_list) == 0:
                    return cur_node.isword
                cur_node.left_child = Node()
                return self._insert(char_list, cur_node.left_child)
            elif char == cur_node.value:
                del char_list[0]
                if len(char_list) == 0:
                    return cur_node.isword
                cur_node.left_child = Node()
                return self._insert(char_list, cur_node.left_child)
            # elif char != cur_node:
            else:
                cur_node.right_child = Node()
                return self._insert(char_list, cur_node.right_child)

    def search(self, word):
        if self.root is None:
            return False
        else:
            return self._search(word, cur_node=self.root)

    def _search(self, word, cur_node, char_list=None):
        if char_list is None:
            char_list = list(word)
        elif len(char_list) == 0:
            return False

        if cur_node.value is None:
            return False
        elif cur_node.value != char_list[0]:
            self._search(word, cur_node.right_child, char_list)
        elif cur_node.value == char_list[0]:
            if cur_node.isword == word:
                return True
            del char_list[0]
            self._search(word, cur_node.left_child, char_list)

    def print_tree(self):
        if self.root is None:
            print('Tree is empty!')
        else:
            self._print_tree(self.root)

    def _print_tree(self, cur_node):
        if cur_node is None:
            # print('Node is empty')
            pass
        else:
            self._print_tree(cur_node.left_child)
            print(str(cur_node.value))
            self._print_tree(cur_node.right_child)


tree = BinaryTree()
tree.insert('tesa')
tree.insert('term')
# tree.insert('tell')

# print(tree.search('test'))

tree.print_tree()
print()
print(tree.root.value)
where my mistake?
Reply
#3
If interested, There are some really good btree examples in python with diagrams here: http://www.laurentluce.com/posts/binary-...in-python/
Reply
#4
Well, I know what is binary tree, I can make it with numbers easyly. but this one - with simbols.
Reply
#5
so... I'm sory, but could someone say me where exactly I am wrong?
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Print Binary Tree - Python Daniel94 1 2,614 Jan-08-2020, 09:54 PM
Last Post: ichabod801
  Return size of binary tree Daniel94 1 1,905 Jan-05-2020, 04:09 PM
Last Post: ichabod801

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020