二叉树遍历函数在Steps上回复，那么运行不能不止一次吗？
Binary tree traversing function replies on Steps, so can't run it more than once?
我实现了一个二叉树 in-order 遍历函数。本质上有 3 个递归步骤：向左走 child，获取货物数据，向右走 child。所以我设计了一个incremental flags(a 属性 belong to Node class) 来记录遍历过程中某个节点上的步数是否被执行过。如果我 运行 它一次，标志 运行 很好。当 运行 第二次出现时，这些标志违背了目的。
解决方案：我可以使用与我用来生成节点 objects 的功能类似的功能来重置标志。但这似乎很多余并且在重复我自己。您能否为我提供一个更好的解决方案来重置标志以用于遍历目的，或者提供一个完全不使用这些步骤的不同解决方案？
谢谢！
下面是 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 的主要原因是让您有机会添加验证或更改属性的内部实现，而不会破坏 class 的 public API。在 Python 中，如果要添加验证或更改 public 属性的实现，可以使用 property 将属性查找转换为方法调用。
我实现了一个二叉树 in-order 遍历函数。本质上有 3 个递归步骤：向左走 child，获取货物数据，向右走 child。所以我设计了一个incremental flags(a 属性 belong to Node class) 来记录遍历过程中某个节点上的步数是否被执行过。如果我 运行 它一次，标志 运行 很好。当 运行 第二次出现时，这些标志违背了目的。
解决方案：我可以使用与我用来生成节点 objects 的功能类似的功能来重置标志。但这似乎很多余并且在重复我自己。您能否为我提供一个更好的解决方案来重置标志以用于遍历目的，或者提供一个完全不使用这些步骤的不同解决方案？
谢谢！ 下面是 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 的主要原因是让您有机会添加验证或更改属性的内部实现，而不会破坏 class 的 public API。在 Python 中，如果要添加验证或更改 public 属性的实现，可以使用 property 将属性查找转换为方法调用。