我实现了一个二叉树中序遍历函数。基本上有 3 个递归步骤:去左 child ，获取 cargo 数据，去右 child 。所以我设计了一个增量标志(属于 Node 类的属性)来记录在遍历过程中是否已经采取了特定节点上的步骤。如果我运行一次，这些标志运行良好。第二次运行时，这些标志违背了目的。
解决方案:我可以使用与我用来生成节点对象以重置标志的函数类似的函数。但这似乎很多余并且在重复我自己。您能否为我提供一个更好的解决方案来为遍历目的重置标志，或者提供一个完全不使用这些步骤的不同解决方案？
谢谢! 下面是 Python 中的实现:
"""implementation of Binary Tree"""
class BinaryTreeNode(object):
def __init__(self, data, left=None, right=None, parent=None):
self.data = data
self.left = left
self.right = right
self.parent = parent
self.traversal_step = int(0)
def __str__(self):
return str(self.data)
def get_data(self):
return self.data
def get_left(self):
return self.left
def get_right(self):
return self.right
def get_parent(self):
return self.parent
def set_left(self, left):
self.left = left
def set_right(self, right):
self.right = right
def set_parent(self, parent):
self.parent = parent
def set_traversal_step(self, reset=False):
if reset == False:
self.traversal_step += 1
else:
self.traversal_step = 0
def get_traversal_step(self):
return self.traversal_step
class BinaryTree(object):
"""implement a binary tree
Protocol:
any data has value less than value of its parent node
will be placed on the left child node. While the ones
greater, will be placed to the right child node
"""
def __init__(self):
self.root = None
self.tree_depth = int(0)
self.node_sum = int(0)
def insert(self, data):
new_node = BinaryTreeNode(data)
current_node = self.root
# print('begin inserting : ' + str(data))
if self.root:
# Determine left/right side should be chosen for the new node
fulfill_status = False
while not fulfill_status:
if data >= current_node.get_data():
if current_node.get_right():
# print('move to RIGHT, and dive to next level')
current_node = current_node.get_right()
else:
current_node.right = new_node
new_node.set_parent(current_node)
fulfill_status = True
else:
if current_node.get_left():
# print('move to LEFT, and dive to next level')
current_node = current_node.get_left()
else: # empty node slot found
current_node.left = new_node
new_node.set_parent(current_node)
fulfill_status = True
# 3. verify status on the current node
# print('Current parent node = ' + str(current_node.get_data()))
# print('Child status: '
# + 'left=' + str(current_node.get_left())
# + ' right=' + str(current_node.get_right()))
# print('new child\'s parent node is:' + str(new_node.get_parent()))
else:
# print('Building a new tree now, root = ' + str(data))
self.root = new_node
# print('Finishing inserting...' + '#' * 30)
def query(self, data):
"""check if the data presents in the Tree already"""
current_node = self.root
print('begin querying data : {} '.format(data) + '#' * 50)
if self.root:
# Determine left/right side should be chosen for the new node
found_status = False
while not found_status:
if data == current_node.get_data():
found_status = True
break
elif data > current_node.get_data():
if current_node.get_right():
# print('move to RIGHT, and dive to next level')
current_node = current_node.get_right()
else:
break # no existing node larger than the current node.
else:
if current_node.get_left():
# print('move to LEFT, and dive to next level')
current_node = current_node.get_left()
else:
break
if found_status:
print("The data entry: {} found ".format(str(data)) + '#' * 30)
# print('my parent node is '+ str(current_node.get_parent()))
else:
print("Attention! The data entry: {} is not found ".format(str(data)) + '#' * 30 + '\n')
return found_status
else:
print("Attention! The data entry: {} is not found because the tree doesn't exist ".format(str(data))
+ '#' * 30 + '\n' )
return False
def delete(self, data):
"""there are 3 possible scenarios:
1. the node has no child
delete the node and mark its parent node that 'node.next = None'
2. the node has 1 child.
delete the node and re-connect its parent node with its child node
3. the node has 2 children
find the Smallest key in the node's Right sub-tree
replace the node with the Smallest key
"""
current_node = self.root
print('begin deleting data : {} '.format(data) + '#' * 50)
if self.root:
# Determine left/right side should be chosen for the new node
found_status = False
while not found_status:
if data == current_node.get_data():
parent_node_data = current_node.get_parent().get_data()
print('Parent Node is ' + str(parent_node_data))
current_node = current_node.get_parent()
if data >= parent_node_data:
current_node.set_right(None)
print ('removing RIGHT')
else:
current_node.set_left(None)
print('removing LEFT')
found_status = True
break
elif data > current_node.get_data():
if current_node.get_right():
# print('move to RIGHT, and dive to next level')
current_node = current_node.get_right()
else:
break # no existing node larger than the current node.
else:
if current_node.get_left():
# print('move to LEFT, and dive to next level')
current_node = current_node.get_left()
else:
break
if found_status:
print("The data entry: {} found and deleted ".format(str(data)) + '#' * 30)
# print('my parent node is ' + str(current_node.get_parent()))
else:
print("Attention! The data entry: {} is not found ".format(str(data)) + '#' * 30 + '\n')
return found_status
else:
print("Attention! The data entry: {} is not found because the tree doesn't exist ".format(str(data))
+ '#' * 30 + '\n')
return False
def traverse_inOrder(self):
"""Steps:
1 Go Left
2 Process current node
3 Go right
"""
print('traversing tree(in-order)')
tree_node = self.root
result = []
while not (tree_node == self.root and self.root.get_traversal_step() > 1) :
if tree_node.get_traversal_step() < 3:
print('\ncurrent node is {}'.format(tree_node.get_data()))
print('steps: ' + str(tree_node.get_traversal_step()))
print('Left child is: ' + str(tree_node.get_left())) # for debugging
# step1
if tree_node.get_left():
tree_node.set_traversal_step()
while tree_node.get_left() and tree_node.get_left().get_traversal_step() < 3:
print('traversing to LEFT child')
tree_node = tree_node.get_left()
tree_node.set_traversal_step()
else:
print('attempted to go LEFT but failed')
tree_node.set_traversal_step()
# step2
print('getting node data:' + str(tree_node.get_data()))
result.append(tree_node.get_data())
tree_node.set_traversal_step()
#step3
if tree_node.get_right():
print('traversing to RIGHT child')
tree_node.set_traversal_step()
tree_node = tree_node.get_right()
else:
print('attempted to go RIGHT but failed')
tree_node.set_traversal_step()
# step4 fall back to parent node
else:
if tree_node != self.root:
print('reversing to parent node {}'.format(tree_node.get_parent().get_data()))
tree_node = tree_node.get_parent()
# step-final: reset all the step markers for the next traverse run.
print(result)
return result
def traverse_preorder(self):
level_result = []
result = {}
node = self.root
if node:
pass
else:
print('tree does not exist')
return result
if __name__ == '__main__':
INPUT_LIST = [50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 80, 2, 3, 70, 87]
b = BinaryTree()
for i in INPUT_LIST:
b.insert(i)
# print('Query match result : ' + str(b.query(87)))
b.traverse_inOrder()
b.query(3)
b.delete(3)
b.query(3)
b.query(80)
b.traverse_inOrder()
b.traverse_inOrder()
最佳答案
我认为您使事情变得比必要的复杂得多。您可以使用递归函数的执行框架来跟踪哪些节点在做什么:
def in_order_traversal(node):
if node is None:
return
in_order_traversal(node.left)
# do whatever you want to do on the current node here e.g.:
print(node.data)
in_order_traversal(node.right)
如果你不想使用递归，你可以通过使用堆栈将相同的算法变成迭代版本。下面是一个版本，它使用 list 作为堆栈来跟踪我们访问过但尚未自行处理的留下子节点的父节点:
def in_order_traversal_iterative(node):
stack = []
while node is not None or stack:
while node is not None:
stack.append(node)
node = node.left
node = stack.pop()
print(node.data) # process node
node = node.right
这些实现都不需要修改节点，因此您可以根据需要多次运行它们，它们都会起作用。
请注意，在我的示例代码中，我没有使用您节点的 get_X 或 set_Y 方法。在 Python 中通常不需要访问器方法，公共(public)属性要好得多。在其他语言(如 C++ 和 Java)中使用 getter 和 setter 的主要原因是让您有机会在不破坏类的公共(public) API 的情况下添加验证或更改属性的内部实现。在 Python 中，如果要添加验证或更改公共(public)属性的实现，可以使用 property 将属性查找转换为方法调用。
关于python - 二叉树遍历函数依赖于Steps，所以不能多次运行？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36261558/