python - 如何使用二叉搜索树附加值

Question

我正在 Python 3.2.3 中使用二叉搜索树，这是我用于创建二叉搜索树的两个文件(由老师提供)。

但首先我会解释我遇到的问题。首先，我读取文件并将新单词附加到 BST，并以电影标题作为它们的值。但是，我在如何处理 else 语句方面遇到了问题。我相信我需要附加二元搜索树中已经存在的单词，我们说“A”，因为它出现很多，并将其附加到电影标题的另一个值，以便一个键附加到多个值。

我不知道该怎么做，这就是我的 Read 函数中 else 语句所在的位置。任何帮助将不胜感激。

谢谢

树节点:

class TreeNode:
   def __init__(self,key,val,left=None,right=None,
                                       parent=None):
      self.key = key
      self.payload = val
      self.leftChild = left
      self.rightChild = right
      self.parent = parent

   def hasLeftChild(self):
      return self.leftChild

   def hasRightChild(self):
      return self.rightChild

   def isLeftChild(self):
      return self.parent and \
             self.parent.leftChild == self

   def isRightChild(self):
      return self.parent and \
             self.parent.rightChild == self

   def isRoot(self):
      return not self.parent

   def isLeaf(self):
      return not (self.rightChild or self.leftChild)

   def hasAnyChildren(self):
      return self.rightChild or self.leftChild

   def hasBothChildren(self):
      return self.rightChild and self.leftChild

   def replaceNodeData(self,key,value,lc,rc):
      self.key = key
      self.payload = value
      self.leftChild = lc
      self.rightChild = rc
      if self.hasLeftChild():
          self.leftChild.parent = self
      if self.hasRightChild():
          self.rightChild.parent = self

   def __iter__(self):

      if self:
         if self.hasLeftChild():
              for elem in self.leftChild:
                 yield elem
         yield self.key
         if self.hasRightChild():
              for elem in self.rightChild:
                 yield elem

   def findSuccessor(self):
      succ = None
      if self.hasRightChild():
          succ = self.rightChild.findMin()
      else:
          if self.parent:
              if self.isLeftChild():
                  succ = self.parent
              else:
                  self.parent.rightChild = None
                  succ = self.parent.findSuccessor()
                  self.parent.rightChild = self
      return succ

   def findMin(self):
      current = self
      while current.hasLeftChild():
          current = current.leftChild
      return current

   def spliceOut(self):
      if self.isLeaf():
         if self.isLeftChild():
            self.parent.leftChild = None
         else:
            self.parent.rightChild = None
      elif self.hasAnyChildren():
         if self.hasLeftChild():
            if self.isLeftChild():
               self.parent.leftChild = self.leftChild
            else:
               self.parent.rightChild = self.leftChild
            self.leftChild.parent = self.parent
         else:
            if self.isLeftChild():
               self.parent.leftChild = self.rightChild
            else:
               self.parent.rightChild = self.rightChild
            self.rightChild.parent = self.parent

二叉搜索树:

from tree_node import TreeNode

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def __str__(self):
        """Returns a string representation of the tree
           rotated 90 degrees counter-clockwise"""

        def strHelper(root, level):
            resultStr = ""
            if root:
                resultStr += strHelper(root.rightChild, level+1)
                resultStr += "| " * level
                resultStr += str(root.key) + "\n"
                resultStr += strHelper(root.leftChild, level+1)                
            return resultStr


        return strHelper(self.root, 0)


    def __contains__(self,key):
        if self._get(key,self.root):
            return True
        else:
            return False

    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
        return self.get(key) 

    def __setitem__(self,k,v):
        self.put(k,v)

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,
                                          parent=currentNode)
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,
                                          parent=currentNode)

    def delete(self,key):
      if self.size > 1:
          nodeToRemove = self._get(key,self.root)
          if nodeToRemove:
              self.remove(nodeToRemove)
              self.size = self.size-1
          else:
              raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
          self.root = None
          self.size = self.size - 1
      else:
          raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
        self.delete(key)


    def remove(self,currentNode):
      if currentNode.isLeaf(): #leaf
        if currentNode == currentNode.parent.leftChild:
            currentNode.parent.leftChild = None
        else:
            currentNode.parent.rightChild = None
      elif currentNode.hasBothChildren(): #interior
        succ = currentNode.findSuccessor()
        succ.spliceOut()
        currentNode.key = succ.key
        currentNode.payload = succ.payload

      else: # this node has one child
        if currentNode.hasLeftChild():
          if currentNode.isLeftChild():
              currentNode.leftChild.parent = currentNode.parent
              currentNode.parent.leftChild = currentNode.leftChild
          elif currentNode.isRightChild():
              currentNode.leftChild.parent = currentNode.parent
              currentNode.parent.rightChild = currentNode.leftChild
          else:
              currentNode.replaceNodeData(currentNode.leftChild.key,
                                 currentNode.leftChild.payload,
                                 currentNode.leftChild.leftChild,
                                 currentNode.leftChild.rightChild)

        else:
          if currentNode.isLeftChild():
              currentNode.rightChild.parent = currentNode.parent
              currentNode.parent.leftChild = currentNode.rightChild
          elif currentNode.isRightChild():
              currentNode.rightChild.parent = currentNode.parent
              currentNode.parent.rightChild = currentNode.rightChild
          else:
              currentNode.replaceNodeData(currentNode.rightChild.key,
                                 currentNode.rightChild.payload,
                                 currentNode.rightChild.leftChild,
                                 currentNode.rightChild.rightChild)




def main():
    t = BinarySearchTree()
    t.put(5,5)
    t.put(3,3)
    t.put(8,8)
    t.put(10, 10)
    t.put(7,7)
    print(t)

    return t

if __name__ == "__main__": t = main()

我需要帮助的代码:

from binary_search_tree import BinarySearchTree
from tree_node import TreeNode

MovieTree = BinarySearchTree()
MovieList = []

def Read(filename):
    file = open('movieData.txt')
    for line in file:
        line = line.strip()
        words = line.lower().split(' ')
        for word in words:
            if word not in MovieTree:
                MovieTree.put(word, [line])
            else:
                pass
                #attach word that is already in BST to another value
                # which is this case is a movie title.

def Main():
    Read('movieData.txt')
    #print(MovieTree)
    #print (MovieList)

Main()

如果需要的话，这里是我正在阅读的内容的一个小样本:

A Bad Day <2006>
A Baleia Branca - Uma Ideia de Deus <2007>
A Batalha das Flores no Campo Grande <1907>
A Bear Named Winnie <2004>
A Beautiful Daze <2008>
A Beautiful Mind <2001>
A Bell for Adano <1945>
A Better Place <1997>
A Big Hand for Sooty <1998>
A Big Hand for the Little Lady <1966>
A Big Mistake! <2009>
A Bill of Divorcement <1932> <1940>
A Bird in a Bonnet <1958>
A Bird in a Guilty Cage <1952>
A Bird in the Head <1946>
A Bit of Scarlet <1997>
A Black Widow <2009>
A Blind Bargain <1922>
A Blue Collapse <2008>
A Blue Note <2009>

Answer 1

如果我正确理解了要求，我认为你想要MovieTree.get(word).append(line)

get(word) 部分返回与该单词关联的标题列表(即二叉搜索树中匹配单词的有效负载)，而 .append(line) 将行添加到列表末尾。