EDIT：我已经全面完成了原来的问题。然而，我有一个小问题。我会打印出我所有的代码，向大家展示。目标是打印出列表中的所有二进制搜索树部分，再加上每个空白点。空点由None表示。问题是，代码打印出了列表，但是，最后还有三个额外的None。最好是你把代码拿到自己的电脑上运行，因为很难解释这一切。
class TreeNode:
def __init__(self, value, left_child=None, right_child=None, parent=None):
self.value = value
self.left_child = left_child
self.right_child = right_child
self.parent = parent
def __repr__(self):
return '{}'.format(self.value)
class binary_search_tree:
def __init__(self):
self.root=None
def insert(self, value):
if self.root==None:
self.root=TreeNode(value)
else:
self._insert(value, self.root)
def _insert(self, value, current_node):
if value < current_node.value:
if current_node.left_child==None:
current_node.left_child=TreeNode(value)
current_node.left_child.parent=current_node #set parent
else:
self._insert(value, current_node.left_child)
elif value > current_node.value:
if current_node.right_child==None:
current_node.right_child=TreeNode(value)
current_node.right_child.parent=current_node #set parent
else:
self._insert(value, current_node.right_child)
else:
print("Value already in tree")
def height(self):
if self.root!=None:
return self._height(self.root,0)
else:
return 0
def _height(self, current_node, current_height):
if current_node==None: return current_height
left_height=self._height(current_node.left_child,current_height+1)
right_height=self._height(current_node.right_child,current_height+1)
return max(left_height, right_height)
def height_iter(self):
current_node = self.root
if self.root != None:
pass
def print_tree(self):
line = []
if self.root!=None:
line.append(self._print_tree(self.root))
print(line)
def _print_tree(self, current_node):
if current_node!=None:
self._print_tree(current_node.left_child)
print(str(current_node.value))
if current_node.left_child!=None:
print(str(current_node.left_child.value))
if current_node.right_child!=None:
print(str(current_node.right_child.value))
#node.display(current_node)
self._print_tree(current_node.right_child)
#returns the node with the specified input value
def find(self, value):
if self.root!=None:
return self._find(value, self.root)
else:
return None
#private find
def _find(self, value, current_node):
if value==current_node.value:
return current_node
elif value<current_node.value and current_node.left_child!=None:
return self._find(value, current_node.left_child)
elif value>current_node.value and current_node.right_child!=None:
return self._find(value, current_node.right_child)
def delete_value(self, value):
return self.delete_node(self.find(value))
def delete_node(self, node):
#returns node with min in tree rooted at input node
def min_value_node(n):
current=n
while current.left_child!=None:
current=current.left_child
return current
#returns the number of children for the specified node
def num_children(n):
num_children=0
if n.left_child!=None:
num_children+=1
if n.right_child!=None:
num_children+=1
return num_children
#get the parent of the node to be deleted
node_parent = node.parent
#get the number of children of the node to be deleted
node_children = num_children(node)
#CASE 1 (node has no children)
if node_children == 0:
#remove the reference to the node from the parent
if node_parent.left_child==node:
node_parent.left_child=None
else:
node_parent.right_child=None
#CASE 2 (node has 1 child)
if node_children == 1:
#get the populated node
if node.left_child!=None:
child=node.left_child
else:
child=node.right_child
#replace the mode to be deleted with its child
if node_parent.left_child==node:
node_parent.left_child=child
else:
node_parent.right_child=child
child.parent=node_parent
#correct the parent pointer in node
child.parent=node_parent
#CASE 3 (node has two children)
if node_children == 2:
#get the in order successor of the deleted node
successor=min_value_node(node.right_child)
#copy the in order successor value to the node formerly
#holding the value we tried to delete.
node.value=successor.value
#delete in order successor now that the value copied to other node
self.delete_node(successor)
#returns true if the value exists in the tree
def search(self, value):
if self.root!=None:
return self._search(value, self.root)
else:
return False
def _search(self, value, current_node):
if value==current_node.value:
return True
elif value<current_node.value and current_node.left_child!=None:
return self._search(value, current_node.left_child)
elif value>current_node.value and current_node.right_child!=None:
return self._search(value, current_node.right_child)
return False
return type(value)
# def sibling(self,root):
# while root != self.root:
# if root < self.root:
# root = self.root.left_child
def search_iter(self, value):
# if self.root.value == None:
# return False
current_node = self.root
if current_node.value == None:
return False
else:
while (value != current_node.value):
if value < current_node.value:
if current_node.left_child != None:
current_node = current_node.left_child
else:
return False
elif value > current_node.value:
if current_node.right_child != None:
current_node = current_node.right_child
else:
return False
return True
#find the minimum element in the tree
def min(self):
if self.root == None:
return False
current_node = self.root
while (current_node.left_child != None):
current_node = current_node.left_child
return current_node.value
def min_rec(self):
if self.root != None:
return self._min_rec(self.root.left_child)
else:
return self.root.value
def _min_rec(self, current_node):
if current_node == None:
return False
elif current_node.left_child == None:
return current_node.value
else:
return self._min_rec(current_node.left_child)
def max_rec(self):
if self.root != None:
return self._max_rec(self.root.right_child)
else:
return self.root.value
def _max_rec(self, current_node):
if current_node.value == None:
return False
elif current_node.right_child == None:
return current_node.value
else:
return self._max_rec(current_node.right_child)
# while (current_node.left_child != None):
# current_node = current_node.left_child
# return current_node.value
def max(self):
if self.root == None:
return False
current_node = self.root
while (current_node.right_child != None):
current_node = current_node.right_child
return current_node.value
# Function to print level order traversal of tree
def printLevelOrder(self):
from collections import deque
level_lst = []
queue = deque([ self.root ])
while len(queue):
node = queue.popleft()
if node != None:
level_lst.append(node.value)
else:
while node == None:
level_lst.append(None)
node = queue.popleft()
if node != None:
level_lst.append(node.value)
if len(queue) == 0:
break
if node == None:
if len(queue) == 0:
print (level_lst)
break
if node.left_child != None:
queue.append(node.left_child)
else:
queue.append(None)
if node.right_child != None:
queue.append(node.right_child)
else:
queue.append(None)
# root = self.root
# level_lst = []
# if not root:
# return level_lst
# stack = []
# while stack:
# stack.append(root.value)
# root = self.root.left_child
# level = stack.pop()
# curr_level = []
# next_level = []
# for node in level:
# curr_level.append(node.value)
# if node.left_child:
# next_level.append(node.left_child)
# if node.right_child:
# next_level.append(node.right_child)
# level_lst.append(curr_level)
# if next_level:
# stack.append(next_level)
# return level_lst
# root = self.root
# level_lst = []
# queue = []
# queue.append(root.value)
# heigh = self.height()
# while queue:
# count = len(queue)
# level_lst.append(root)
# queue.append(root.value)
# while count > 0:
# queue.append(root.value)
# queue.pop(root.value)
# level_lst.append(root.value)
# if root.left_child == None:
# if root.right_child != None:
# root = root.right_child
# queue.append(root.value)
# elif root.right_child == None:
# root = root.parent.right_child
# else:
# root = root.left_child
# queue.append(root.value)
# print(level_lst)
# def printLevelOrder(self,root):
# if self.root != root:
# h = tree.height()
# for i in range(1, h+1):
# self.printGivenLevel(self.root.value, i)
# def printGivenLevel(self, root , level):
# if root is None:
# return
# if level == 1:
# print(root,end=" ")
# elif level > 1:
# self.printGivenLevel(self.root.left_child , level-1)
# self.printGivenLevel(self.root.right_child , level-1)
#manually populate tree
tree = binary_search_tree()
#Fill tree with 100 random integers
def fill_tree(tree, num_elems, max_int):
from random import randint
for _ in range(num_elems):
cur_elem = randint(0, max_int)
tree.insert(cur_elem)
return tree
#function to draw the tree
def drawtree(root):
def height(root):
return 1 + max(height(root.left_child), height(root.right_child)) if root else -1
def jumpto(x, y):
t.penup()
t.goto(x, y)
t.pendown()
def draw(node, x, y, dx):
if node:
t.goto(x, y)
jumpto(x, y-20)
t.write(node.value, align='center', font=('Arial', 12, 'normal'))
draw(node.left_child, x-dx, y-60, dx/2)
jumpto(x, y-20)
draw(node.right_child, x+dx, y-60, dx/2)
import turtle
t = turtle.Turtle()
t.speed(0); turtle.delay(2)
h = height(root)
jumpto(0, 30*h)
draw(root, 0, 30*h, 40*h)
t.hideturtle()
turtle.mainloop()
####################################
#BUILD A TREE (manual or automatic)
####################################
#Automatic Fill
# tree = binary_search_tree()
# tree = fill_tree(tree,100,100)
# #manually populate tree
# tree = binary_search_tree()
#order of insertion matters in terms of the tree you get : monotonically decreasing insertions
# tree.insert(12)
# tree.insert(10)
# tree.insert(7)
# tree.insert(5)
# tree.insert(2)
# tree.insert(1)
# #tree.insert(0)
# #add some extras and see what happens
# # tree.insert(4)
# # tree.insert(3)
# # tree.insert(7)
# tree.insert(20)
#here's another order of insertion, more mixed - try both to see the result
tree.insert(5)
tree.insert(1)
tree.insert(3)
tree.insert(2)
tree.insert(10)
tree.insert(0)
tree.insert(20)
tree.insert(7)
tree.insert(4)
#query the tree (for monotonically decreasing insertions)
# print(tree.root)
# print(tree.root.left_child)
# print(tree.root.left_child.left_child)
# print(tree.root.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child.left_child.left_child)
#tree height
print("tree height: ",str(tree.height()))
# print("sibling of 10 is",tree.sibling(10))
#minimum element
print("minimum element in tree: ", tree.min())
print("maximum element in tree: ", tree.max_rec())
#print("maximum element in tree: ", tree.max())
print(tree.search_iter(1))
tree.printLevelOrder()
#print(tree.find(10))
#tree.delete_value(3)
#tree.delete_value(2)
#############
#DRAW A TREE
#############
drawtree(tree.root)
您只需要以下内容：
from collections import deque
def printLevelOrder(self):
queue = deque([ self.root ])
while len(queue):
node = queue.popleft()
print(node.value)
if node.left_child != None:
queue.append( ( node.left_child)
if node.right_child != None:
queue.append(node.right_child)
如果你也想要水平，
from collections import deque
def printLevelOrder(self):
queue = deque([ ( 0, self.root ) ])
while len(queue):
state = queue.popleft()
level = state[0]
node = state[1]
print(level, node.value)
if node.left_child != None:
queue.append( ( level+1, node.left_child ) )
if node.right_child != None:
queue.append( ( level+1, node.right_child ) )
返回按级别分组的值是另一个简单的修改。
from collections import deque
def printLevelOrder(self):
grouped = []
queue = deque([ ( 0, self.root ) ])
while len(queue):
state = queue.popleft()
level = state[0]
node = state[1]
if len(grouped) == level:
grouped.append([])
grouped[level].append(node.value)
if node.left_child != None:
queue.append( ( level+1, node.left_child ) )
if node.right_child != None:
queue.append( ( level+1, node.right_child ) )
return grouped