python - 接受整数列表作为输入，并将它们一一插入到python中的空二叉搜索树中

Question

我想接受一个整数列表作为输入，并将它们一一插入到一个空的 BST 中。讲师提供了一些代码供我修改。

我试图修改代码并卡住了。我已经接受了一个整数列表并用空格分隔并将其插入到一个列表中。现在我需要将列表中的元素添加到二叉树并获取前序、后序遍历。这是代码：

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

    # Return True if the element is in the tree
    def search(self, e):
        current = self.root # Start from the root

        while current != None:
            if e < current.element:
                current = current.left
            elif e > current.element:
                current = current.right
            else: # element matches current.element
                return True # Element is found

        return False

    # Insert element e into the binary search tree
    # Return True if the element is inserted successfully
    def insert(self, e):
        if self.root == None:
          self.root = self.createNewNode(e) # Create a new root
        else:
          # Locate the parent node
          parent = None
          current = self.root
          while current != None:
            if e < current.element:
              parent = current
              current = current.left
            elif e > current.element:
              parent = current
              current = current.right
            else:
              return False # Duplicate node not inserted

          # Create the new node and attach it to the parent node
          if e < parent.element:
            parent.left = self.createNewNode(e)
          else:
            parent.right = self.createNewNode(e)

        self.size += 1 # Increase tree size
        return True # Element inserted

    # Create a new TreeNode for element e
    def createNewNode(self, e):
      return TreeNode(e)
    """
    # Return the size of the tree
    def getSize(self):
      return self.size"""

    # Inorder traversal from the root
    def inorder(self):
      self.inorderHelper(self.root)

    # Inorder traversal from a subtree
    def inorderHelper(self, r):
      if r != None:
        self.inorderHelper(r.left)
        print(r.element, end = " ")
        self.inorderHelper(r.right)

    # Postorder traversal from the root
    def postorder(self):
      self.postorderHelper(self.root)

    # Postorder traversal from a subtree
    def postorderHelper(self, root):
      if root != None:
        self.postorderHelper(root.left)
        self.postorderHelper(root.right)
        print(root.element, end = " ")

    # Preorder traversal from the root
    def preorder(self):
      self.preorderHelper(self.root)

    # Preorder traversal from a subtree
    def preorderHelper(self, root):
      if root != None:
        print(root.element, end = " ")
        self.preorderHelper(root.left)
        self.preorderHelper(root.right)


    # Return true if the tree is empty
    def isEmpty(self):
      return self.size == 0

    # Remove all elements from the tree
    def clear(self):
      self.root == None
      self.size == 0

    # Return the root of the tree
    def getRoot(self):
      return self.root

class TreeNode:
    def __init__(self, e):
      self.element = e
      self.left = None # Point to the left node, default None
      self.right = None # Point to the right node, default None

    ####################### Main test binary tree

def main(size = 7):
    int_list=input('Enter a list of integers seperated by spaces: ')

    numbers =[int_list] 

    print ("\n\nInserting the following values:")  
    intTree = BinaryTree()
    for e in numbers:
      intTree.insert(e)
    print("\nPreorder traversal:")
    intTree.preorder()
    print("\n\nInorder traversal:")
    intTree.inorder()
    print("\n\nPostorder traversal:")
    intTree.postorder()


if __name__ == "__main__":
    main()

标签： pythonbinary-search-tree

Answer 1

From what I understand you have a list and you want to insert all the elements in a binary search tree. You can write a new function that takes as parameter an array, your list, and the you can iterate with a for loop and call the function insert(self, e) for every element that belongs to the array. Then outside the loop you can call whatever function you need (postorder, ...).