class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class CreatTree(object):
"""根据列表生成树"""
def __init__(self, li):
self.li = li
if not li:
self.root = None
self.root = TreeNode(li.pop(0))
self.queue = [self.root]
self._creat_tree()
def _creat_tree(self):
while self.queue:
inner_queue = []
for node in self.queue[::]:
if not self.li:
return
left_val = self.li.pop(0)
if left_val is not None:
node.left = TreeNode(left_val)
inner_queue.append(node.left)
if not self.li:
return
right_val = self.li.pop(0)
if right_val is not None:
node.right = TreeNode(right_val)
inner_queue.append(node.right)
self.queue = inner_queue
class TreeCode(object):
"""关于tree 的遍历"""
def middle(self, root, result):
# 中序遍历
if not root:
return
self.middle(root.left, result)
result.append(root.val)
self.middle(root.right, result)
@classmethod
def middle_stark(cls, root):
""" 中序遍历的使用栈版本 """
result = []
if not root:
return result
stark = []
while root or stark:
while root:
stark.append(root)
root = root.left
root = stark.pop()
result.append(root.val)
root = root.right
return result
def preorder(self, root, result: list):
"""前序遍历"""
if not root:
return
result.append(root.val)
self.preorder(root.left, result)
self.preorder(root.right, result)
@classmethod
def preorder_stark(cls, root):
"""前序遍历的栈版本"""
if not root:
return []
result = []
stark = [root]
while stark:
node = stark.pop()
result.append(node.val)
if node.right:
stark.append(node.right)
if node.left:
stark.append(node.left)
return result
def postorder(self, root, result):
"""后序遍历"""
if not root:
return
self.postorder(root.left, result)
self.postorder(root.right, result)
result.append(root.val)
@classmethod
def postorder_stark(cls, root):
"""后续遍历的非递归版本"""
result = []
if not root:
return result
stark = [root]
res = []
while stark:
node = stark.pop()
if node.left or node.right:
res.append(node) # 有子节点的根节点先入栈
if node.left:
stark.append(node.left)
if node.right: # 右节点后入 保证右节点先如第二个栈(在第二个栈中后出)
stark.append(node.right)
else:
res.append(node) # 没有根节点的节点再入栈
while res:
node = res.pop()
result.append(node.val)
return result
if __name__ == '__main__':
data_list = [1, 2, 3, None, 4, 5, 6, 7]
data_list = [5, 2, 3, None, None, 2, 4, 3, 1]
tree = CreatTree(data_list).root
print(tree)
tree_code = TreeCode()
result_ = []
tree_code.middle(tree, result_)
print(result_)
print(tree_code.middle_stark(tree))
result_ = []
tree_code.preorder(tree, result_)
print(result_)
print(tree_code.preorder_stark(tree))
result_ = []
tree_code.postorder(tree, result_)
print(result_)
print(tree_code.postorder_stark(tree))
| 
转播
