程序应该首先初始化一个空的 AVL 树。该程序采用一行作为输入。这 输入行包含 n 个由空格分隔的“修改动作”(1 ≤ n ≤ 100)。可用的修改 动作是：
您的输入后面紧跟着一种遍历模式（PRE 或 POST 或 IN）：如果模式是 PRE， 那么你应该在预订时打印出树（在当前情况下）。如果树为空，则打印出 空的。否则，打印出由空格分隔的值。 POST 和 IN 的处理方式类似。
以下是我的main.py：
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
self.height = 1
class AVL_Tree:
def insert(self, root, key):
# Step 1: Perform normal BST insertion
if not root:
return Node(key)
elif key < root.val:
root.left = self.insert(root.left, key)
elif key > root.val:
root.right = self.insert(root.right, key)
else:
# Duplicate keys are not allowed in the AVL tree
return root
# Step 2: Update the height of the ancestor node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Step 3: Get the balance factor
balance = self.getBalance(root)
# Step 4: If the node becomes unbalanced, then try out the 4 cases
# Left Left Case
if balance > 1 and key < root.left.val:
return self.rightRotate(root)
# Right Right Case
if balance < -1 and key > root.right.val:
return self.leftRotate(root)
# Left Right Case
if balance > 1 and key > root.left.val:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Right Left Case
if balance < -1 and key < root.right.val:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def delete(self, root, key):
if not root:
return root
if key < root.val:
root.left = self.delete(root.left, key)
elif key > root.val:
root.right = self.delete(root.right, key)
else:
# Nodes with only one child or no child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children: Get the inorder successor (smallest in the right subtree)
temp = self.getMinValueNode(root.right)
root.val = temp.val
root.right = self.delete(root.right, temp.val)
# If the tree had only one node then return
if root is None:
return root
# Update the height of the current node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Get the balance factor
balance = self.getBalance(root)
# If the node becomes unbalanced, then try out the 4 cases
# Left Left Case
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
# Left Right Case
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Right Right Case
if balance < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
# Right Left Case
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rightRotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def getMinValueNode(self, root):
current = root
while current.left is not None:
current = current.left
return current
def preOrder(self, root):
res = []
if root:
res.append(root.val)
res.extend(self.preOrder(root.left))
res.extend(self.preOrder(root.right))
return res
def inOrder(self, root):
res = []
if root:
res.extend(self.inOrder(root.left))
res.append(root.val)
res.extend(self.inOrder(root.right))
return res
def postOrder(self, root):
res = []
if root:
res.extend(self.postOrder(root.left))
res.extend(self.postOrder(root.right))
res.append(root.val)
return res
def process_commands(input_line):
commands = input_line.split()
tree = AVL_Tree()
root = None
for command in commands[:-1]: # Last command is the type of traversal
if command.startswith('A'):
value = int(command[1:])
root = tree.insert(root, value)
elif command.startswith('D'):
value = int(command[1:])
root = tree.delete(root, value)
# Determine the type of traversal
traversal_command = commands[-1]
if traversal_command == "PRE":
result = tree.preOrder(root)
elif traversal_command == "IN":
result = tree.inOrder(root)
elif traversal_command == "POST":
result = tree.postOrder(root)
if not result:
return "EMPTY"
return " ".join(map(str, result))
# To run the program, you would typically wrap this in a block that takes input, e.g.:
input_line = input()
output = process_commands(input_line)
print(output)
现在作为示例，如果我输入以下内容作为输入： A1 A2 A3 A5 D3 D5 输入
输出应该是： 1 2
它似乎适用于任何遍历模式为 IN 的情况，但仅当遍历模式为 PRE 或 POST 时才部分有效。这就是我陷入困境的地方，因为我已经梳理了代码，但我无法理解问题似乎出在哪里。我只是真的想要一双新的眼睛来审视我的代码并告诉我哪里出了问题。我问过 chatGPT，但当我问任何复杂的问题时，它似乎会产生幻觉。
你得到答案了吗？ 这是邮购代码
def postorder(root):
#if root is None return
if root==None:
return
#traverse left subtree
postorder(root.leftChild)
#traverse right subtree
postorder(root.rightChild)
#traverse root
print(root.data)