Счетчик частоты дерева двоичного поиска - PullRequest
Новая
       8

Счетчик частоты дерева двоичного поиска

0 голосов
/ 09 ноября 2018

Мне нужно прочитать текстовый файл, убрать ненужные знаки препинания, использовать строчные буквы и использовать функцию дерева двоичного поиска, чтобы создать дерево двоичного поиска слов, состоящее из слов в файле.

Нас просят подсчитать частоту повторяющихся слов и просят общее количество слов и общее количество уникальных слов.

Пока что у меня есть пунктуация, чтение файла, выполнение строчных букв, двоичное дерево поиска в основном, и мне просто нужно выяснить, как реализовать счетчик «частоты» в коде.

Мой код выглядит следующим образом: 

class BSearchTree :
class _Node :
    def __init__(self, word, left = None, right = None) :
        self._word = word
        self._count = 0
        self._left = left
        self._right = right

def __init__(self) :
    self._root = None
    self._wordc = 0
    self._each = 0

def isEmpty(self) :
    return self._root == None


def search(self, word) :
    probe = self._root
    while (probe != None) :
        if word == probe._word :
            return probe
        if word < probe._value :
            probe = probe._left
        else : 
            probe = probe._right
    return None     

def insert(self, word) :
    if self.isEmpty() :
        self._root = self._Node(word)
        self._root._freq += 1 <- is this correct?
        return

    parent = None               #to keep track of parent
                                #we need above information to adjust 
                                #link of parent of new node later

    probe = self._root
    while (probe != None) :
        if word < probe._word :     # go to left tree
            parent = probe          # before we go to child, save parent
            probe = probe._left
        elif word > probe._word :   # go to right tree
            parent = probe          # before we go to child, save parent
            probe = probe._right

    if (word < parent._word) :      #new value will be new left child
        parent._left = self._Node(word)
    else :    #new value will be new right child
        parent._right = self._Node(word)

потому что форматирование убивает меня, это последняя часть. 

class NotPresent(Exception) :
pass

def main():
t=BST()

file = open("sample.txt")           
line = file.readline()                      
file.close()                            


#for word in line:
#   t.insert(word)
# Line above crashes program because there are too many 
# words to add. Lines on bottom tests BST class
t.insert('all')
t.insert('high')
t.insert('fly')
t.insert('can')
t.insert('boars')
#t.insert('all') <- how do i handle duplicates by making 
t.inOrder()        #extras add to the nodes frequency?

Спасибо за помощь / попытку помочь!

1 Ответ

0 голосов
/ 09 ноября 2018

Во-первых, лучше инициализировать Node _freq на 1, чем сделать это в BST * insert()

(еще 1: в соглашении о кодировании в Python пробелы при записи значений аргументов по умолчанию не рекомендуются.) 

    def __init__(self, word, left=None, right=None) :
        self._word = word
        self._freq = 1
        self._left = left
        self._right = right

и просто добавьте последние 3 строки: 

    probe = self._root
    while (probe != None) :
        if word < probe._word :     # go to left tree
            parent = probe          # before we go to child, save parent
            probe = probe._left
        elif word > probe._word :   # go to right tree
            parent = probe          # before we go to child, save parent
            probe = probe._right
        else:
            probe._freq += 1
            return
...