打印 AVL 树中叶子的路径
Printing a Path to a Leaf in an AVL Tree
我正在尝试打印此 AVL 树中每一片叶子的路径。我的问题是：为什么程序吐出元素的内存位置和文件名而不是元素？
from BinaryTree import BinaryTree
from BinaryTree import TreeNode
class AVLTree(BinaryTree):
def __init__(self):
BinaryTree.__init__(self)
# Override the createNewNode method to create an AVLTreeNode
def createNewNode(self, e):
return AVLTreeNode(e)
def getPath(self, o):
path = BinaryTree.path(self, o);
return path
# Override the insert method to balance the tree if necessary
def insert(self, o):
successful = BinaryTree.insert(self, o)
if not successful:
return False # o is already in the tree
else:
self.balancePath(o) # Balance from o to the root if necessary
return True # o is inserted
# Update the height of a specified node
def updateHeight(self, node):
if node.left == None and node.right == None: # node is a leaf
node.height = 0
elif node.left == None: # node has no left subtree
node.height = 1 + (node.right).height
elif node.right == None: # node has no right subtree
node.height = 1 + (node.left).height
else:
node.height = 1 + max((node.right).height, (node.left).height)
# Balance the nodes in the path from the specified
# node to the root if necessary
def balancePath(self, o):
path = BinaryTree.path(self, o)
for i in range(len(path) - 1, -1, -1):
A = path[i]
self.updateHeight(A)
parentOfA = None if (A == self.root) else path[i - 1]
if self.balanceFactor(A) == -2:
if self.balanceFactor(A.left) <= 0:
self.balanceLL(A, parentOfA) # Perform LL rotation
else:
self.balanceLR(A, parentOfA) # Perform LR rotation
elif self.balanceFactor(A) == +2:
if self.balanceFactor(A.right) >= 0:
self.balanceRR(A, parentOfA) # Perform RR rotation
else:
self.balanceRL(A, parentOfA) # Perform RL rotation
# Return the balance factor of the node
def balanceFactor(self, node):
if node.right == None: # node has no right subtree
return -node.height
elif node.left == None: # node has no left subtree
return +node.height
else:
return (node.right).height - (node.left).height
# Balance LL (see Figure 14.2)
def balanceLL(self, A, parentOfA):
B = A.left # A is left-heavy and B is left-heavy
if A == self.root:
self.root = B
else:
if parentOfA.left == A:
parentOfA.left = B
else:
parentOfA.right = B
A.left = B.right # Make T2 the left subtree of A
B.right = A # Make A the left child of B
self.updateHeight(A)
self.updateHeight(B)
def getSearch(self, o):
return BinaryTree.search(self, o)
# Balance LR (see Figure 14.2(c))
def balanceLR(self, A, parentOfA):
B = A.left # A is left-heavy
C = B.right # B is right-heavy
if A == self.root:
self.root = C
else:
if parentOfA.left == A:
parentOfA.left = C
else:
parentOfA.right = C
A.left = C.right # Make T3 the left subtree of A
B.right = C.left # Make T2 the right subtree of B
C.left = B
C.right = A
# Adjust heights
self.updateHeight(A)
self.updateHeight(B)
self.updateHeight(C)
# Balance RR (see Figure 14.2(b))
def balanceRR(self, A, parentOfA):
B = A.right # A is right-heavy and B is right-heavy
if A == self.root:
self.root = B
else:
if parentOfA.left == A:
parentOfA.left = B
else:
parentOfA.right = B
A.right = B.left # Make T2 the right subtree of A
B.left = A
self.updateHeight(A)
self.updateHeight(B)
# Balance RL (see Figure 14.2(d))
def balanceRL(self, A, parentOfA):
B = A.right # A is right-heavy
C = B.left # B is left-heavy
if A == self.root:
self.root = C
else:
if parentOfA.left == A:
parentOfA.left = C
else:
parentOfA.right = C
A.right = C.left # Make T2 the right subtree of A
B.left = C.right # Make T3 the left subtree of B
C.left = A
C.right = B
# Adjust heights
self.updateHeight(A)
self.updateHeight(B)
self.updateHeight(C)
# Delete an element from the binary tree.
# Return True if the element is deleted successfully
# Return False if the element is not in the tree
def delete(self, element):
if self.root == None:
return False # Element is not in the tree
# Locate the node to be deleted and also locate its parent node
parent = None
current = self.root
while current != None:
if element < current.element:
parent = current
current = current.left
elif element > current.element:
parent = current
current = current.right
else:
break # Element is in the tree pointed by current
if current == None:
return False # Element is not in the tree
# Case 1: current has no left children (See Figure 23.6)
if current.left == None:
# Connect the parent with the right child of the current node
if parent == None:
root = current.right
else:
if element < parent.element:
parent.left = current.right
else:
parent.right = current.right
# Balance the tree if necessary
self.balancePath(parent.element)
else:
# Case 2: The current node has a left child
# Locate the rightmost node in the left subtree of
# the current node and also its parent
parentOfRightMost = current
rightMost = current.left
while rightMost.right != None:
parentOfRightMost = rightMost
rightMost = rightMost.right # Keep going to the right
# Replace the element in current by the element in rightMost
current.element = rightMost.element
# Eliminate rightmost node
if parentOfRightMost.right == rightMost:
parentOfRightMost.right = rightMost.left
else:
# Special case: parentOfRightMost is current
parentOfRightMost.left = rightMost.left
# Balance the tree if necessary
self.balancePath(parentOfRightMost.element)
self.size -= 1 # One element deleted
return True # Element inserted
def getLeafNodes(self):
return BinaryTree.leafNodes(self)
# AVLTreeNode is TreeNode plus height
class AVLTreeNode(TreeNode):
def __init__(self, e):
self.height = 0 # New data field
TreeNode.__init__(self, e)
这是它调用的二叉树
class BinaryTree:
def __init__(self):
self.counter = -1
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
def __iter__(self):
return self
def __next__(self):
x = self.inorder()
self.num = []
for i in range(x.getSize()):
self.num.append(x.pop())
self.num.reverse()
while True:
self.counter += 1
break
return self.num[self.counter]
# 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)
# Returns a path from the root leading to the specified element
def path(self, e):
path = []
current = self.root # Start from the root
while current != None:
path.append(current) # Add the node to the list
if e < current.element:
current = current.left
elif e > current.element:
current = current.right
else:
break
return path # Return an array of nodes
# Delete an element from the binary search tree.
# Return True if the element is deleted successfully
# Return False if the element is not in the tree
def delete(self, e):
# Locate the node to be deleted and its 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:
break # Element is in the tree pointed by current
if current == None:
return False # Element is not in the tree
# Case 1: current has no left children
if current.left == None:
# Connect the parent with the right child of the current node
if parent == None:
self.root = current.right
else:
if e < parent.element:
parent.left = current.right
else:
parent.right = current.right
else:
# Case 2: The current node has a left child
# Locate the rightmost node in the left subtree of
# the current node and also its parent
parentOfRightMost = current
rightMost = current.left
while rightMost.right != None:
parentOfRightMost = rightMost
rightMost = rightMost.right # Keep going to the right
# Replace the element in current by the element in rightMost
current.element = rightMost.element
# Eliminate rightmost node
if parentOfRightMost.right == rightMost:
parentOfRightMost.right = rightMost.left
else:
# Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left
self.size -= 1
return True # Element deleted
def leafNodes(self):
self.leaves = []
return self.leafNodesHelper(self.root)
def leafNodesHelper(self, root):
if root != None:
if root.left == None and root.right == None:
self.leaves.append(root.element)
else:
self.leafNodesHelper(root.left)
self.leafNodesHelper(root.right)
return self.leaves
# 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
这是让我很沮丧的测试程序
from AVLTree20_3 import AVLTree
tree = AVLTree()
for i in range(1, 101):
tree.insert(i)
x = tree.getLeafNodes()
for i in range(len(x)):
path = tree.getPath(x[i])
print(path)
请帮我弄清楚为什么这行不通。我尝试了调试器并从所有三个文件中打印，但 none 似乎可以正确打印出来，这是为什么？
你的问题是路径方法returns一个节点列表。
有两个解决方案在节点 class 中定义第一个覆盖方法 (str)。
或者如下划线：
from AVLTree20_3 import AVLTree
tree = AVLTree()
for i in range(1, 101):
tree.insert(i)
x = tree.getLeafNodes()
for i in range(len(x)):
path = [x.element for x in tree.getPath(x[i])]
print(path,"\n---------------------")
我正在尝试打印此 AVL 树中每一片叶子的路径。我的问题是：为什么程序吐出元素的内存位置和文件名而不是元素？
from BinaryTree import BinaryTree
from BinaryTree import TreeNode
class AVLTree(BinaryTree):
def __init__(self):
BinaryTree.__init__(self)
# Override the createNewNode method to create an AVLTreeNode
def createNewNode(self, e):
return AVLTreeNode(e)
def getPath(self, o):
path = BinaryTree.path(self, o);
return path
# Override the insert method to balance the tree if necessary
def insert(self, o):
successful = BinaryTree.insert(self, o)
if not successful:
return False # o is already in the tree
else:
self.balancePath(o) # Balance from o to the root if necessary
return True # o is inserted
# Update the height of a specified node
def updateHeight(self, node):
if node.left == None and node.right == None: # node is a leaf
node.height = 0
elif node.left == None: # node has no left subtree
node.height = 1 + (node.right).height
elif node.right == None: # node has no right subtree
node.height = 1 + (node.left).height
else:
node.height = 1 + max((node.right).height, (node.left).height)
# Balance the nodes in the path from the specified
# node to the root if necessary
def balancePath(self, o):
path = BinaryTree.path(self, o)
for i in range(len(path) - 1, -1, -1):
A = path[i]
self.updateHeight(A)
parentOfA = None if (A == self.root) else path[i - 1]
if self.balanceFactor(A) == -2:
if self.balanceFactor(A.left) <= 0:
self.balanceLL(A, parentOfA) # Perform LL rotation
else:
self.balanceLR(A, parentOfA) # Perform LR rotation
elif self.balanceFactor(A) == +2:
if self.balanceFactor(A.right) >= 0:
self.balanceRR(A, parentOfA) # Perform RR rotation
else:
self.balanceRL(A, parentOfA) # Perform RL rotation
# Return the balance factor of the node
def balanceFactor(self, node):
if node.right == None: # node has no right subtree
return -node.height
elif node.left == None: # node has no left subtree
return +node.height
else:
return (node.right).height - (node.left).height
# Balance LL (see Figure 14.2)
def balanceLL(self, A, parentOfA):
B = A.left # A is left-heavy and B is left-heavy
if A == self.root:
self.root = B
else:
if parentOfA.left == A:
parentOfA.left = B
else:
parentOfA.right = B
A.left = B.right # Make T2 the left subtree of A
B.right = A # Make A the left child of B
self.updateHeight(A)
self.updateHeight(B)
def getSearch(self, o):
return BinaryTree.search(self, o)
# Balance LR (see Figure 14.2(c))
def balanceLR(self, A, parentOfA):
B = A.left # A is left-heavy
C = B.right # B is right-heavy
if A == self.root:
self.root = C
else:
if parentOfA.left == A:
parentOfA.left = C
else:
parentOfA.right = C
A.left = C.right # Make T3 the left subtree of A
B.right = C.left # Make T2 the right subtree of B
C.left = B
C.right = A
# Adjust heights
self.updateHeight(A)
self.updateHeight(B)
self.updateHeight(C)
# Balance RR (see Figure 14.2(b))
def balanceRR(self, A, parentOfA):
B = A.right # A is right-heavy and B is right-heavy
if A == self.root:
self.root = B
else:
if parentOfA.left == A:
parentOfA.left = B
else:
parentOfA.right = B
A.right = B.left # Make T2 the right subtree of A
B.left = A
self.updateHeight(A)
self.updateHeight(B)
# Balance RL (see Figure 14.2(d))
def balanceRL(self, A, parentOfA):
B = A.right # A is right-heavy
C = B.left # B is left-heavy
if A == self.root:
self.root = C
else:
if parentOfA.left == A:
parentOfA.left = C
else:
parentOfA.right = C
A.right = C.left # Make T2 the right subtree of A
B.left = C.right # Make T3 the left subtree of B
C.left = A
C.right = B
# Adjust heights
self.updateHeight(A)
self.updateHeight(B)
self.updateHeight(C)
# Delete an element from the binary tree.
# Return True if the element is deleted successfully
# Return False if the element is not in the tree
def delete(self, element):
if self.root == None:
return False # Element is not in the tree
# Locate the node to be deleted and also locate its parent node
parent = None
current = self.root
while current != None:
if element < current.element:
parent = current
current = current.left
elif element > current.element:
parent = current
current = current.right
else:
break # Element is in the tree pointed by current
if current == None:
return False # Element is not in the tree
# Case 1: current has no left children (See Figure 23.6)
if current.left == None:
# Connect the parent with the right child of the current node
if parent == None:
root = current.right
else:
if element < parent.element:
parent.left = current.right
else:
parent.right = current.right
# Balance the tree if necessary
self.balancePath(parent.element)
else:
# Case 2: The current node has a left child
# Locate the rightmost node in the left subtree of
# the current node and also its parent
parentOfRightMost = current
rightMost = current.left
while rightMost.right != None:
parentOfRightMost = rightMost
rightMost = rightMost.right # Keep going to the right
# Replace the element in current by the element in rightMost
current.element = rightMost.element
# Eliminate rightmost node
if parentOfRightMost.right == rightMost:
parentOfRightMost.right = rightMost.left
else:
# Special case: parentOfRightMost is current
parentOfRightMost.left = rightMost.left
# Balance the tree if necessary
self.balancePath(parentOfRightMost.element)
self.size -= 1 # One element deleted
return True # Element inserted
def getLeafNodes(self):
return BinaryTree.leafNodes(self)
# AVLTreeNode is TreeNode plus height
class AVLTreeNode(TreeNode):
def __init__(self, e):
self.height = 0 # New data field
TreeNode.__init__(self, e)
这是它调用的二叉树
class BinaryTree:
def __init__(self):
self.counter = -1
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
def __iter__(self):
return self
def __next__(self):
x = self.inorder()
self.num = []
for i in range(x.getSize()):
self.num.append(x.pop())
self.num.reverse()
while True:
self.counter += 1
break
return self.num[self.counter]
# 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)
# Returns a path from the root leading to the specified element
def path(self, e):
path = []
current = self.root # Start from the root
while current != None:
path.append(current) # Add the node to the list
if e < current.element:
current = current.left
elif e > current.element:
current = current.right
else:
break
return path # Return an array of nodes
# Delete an element from the binary search tree.
# Return True if the element is deleted successfully
# Return False if the element is not in the tree
def delete(self, e):
# Locate the node to be deleted and its 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:
break # Element is in the tree pointed by current
if current == None:
return False # Element is not in the tree
# Case 1: current has no left children
if current.left == None:
# Connect the parent with the right child of the current node
if parent == None:
self.root = current.right
else:
if e < parent.element:
parent.left = current.right
else:
parent.right = current.right
else:
# Case 2: The current node has a left child
# Locate the rightmost node in the left subtree of
# the current node and also its parent
parentOfRightMost = current
rightMost = current.left
while rightMost.right != None:
parentOfRightMost = rightMost
rightMost = rightMost.right # Keep going to the right
# Replace the element in current by the element in rightMost
current.element = rightMost.element
# Eliminate rightmost node
if parentOfRightMost.right == rightMost:
parentOfRightMost.right = rightMost.left
else:
# Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left
self.size -= 1
return True # Element deleted
def leafNodes(self):
self.leaves = []
return self.leafNodesHelper(self.root)
def leafNodesHelper(self, root):
if root != None:
if root.left == None and root.right == None:
self.leaves.append(root.element)
else:
self.leafNodesHelper(root.left)
self.leafNodesHelper(root.right)
return self.leaves
# 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
这是让我很沮丧的测试程序
from AVLTree20_3 import AVLTree
tree = AVLTree()
for i in range(1, 101):
tree.insert(i)
x = tree.getLeafNodes()
for i in range(len(x)):
path = tree.getPath(x[i])
print(path)
请帮我弄清楚为什么这行不通。我尝试了调试器并从所有三个文件中打印，但 none 似乎可以正确打印出来，这是为什么？
你的问题是路径方法returns一个节点列表。 有两个解决方案在节点 class 中定义第一个覆盖方法 (str)。 或者如下划线：
from AVLTree20_3 import AVLTree
tree = AVLTree()
for i in range(1, 101):
tree.insert(i)
x = tree.getLeafNodes()
for i in range(len(x)):
path = [x.element for x in tree.getPath(x[i])]
print(path,"\n---------------------")