题目标题

遍历二叉树

参考解析
  1. class Node():
  2. # 节点类
  3. def __init__(self, data=-1):
  4. self.data = data
  5. self.left = None
  6. self.right = None
  7. class Tree():
  8. # 树类
  9. def __init__(self):
  10. self.root = Node()
  11. def add(self, data):
  12. # 为树加入节点
  13. node = Node(data)
  14. if self.root.data == -1: # 如果树为空,就对根节点赋值
  15. self.root = node
  16. else:
  17. myQueue = []
  18. treeNode = self.root
  19. myQueue.append(treeNode)
  20. while myQueue: # 对已有的节点进行层次遍历
  21. treeNode = myQueue.pop(0)
  22. if not treeNode.left:
  23. treeNode.left = node
  24. return
  25. elif not treeNode.right:
  26. treeNode.right = node
  27. return
  28. else:
  29. myQueue.append(treeNode.left)
  30. myQueue.append(treeNode.right)
  31. def DFS(self,root): #递归实现深度优先遍历
  32. if root == None:
  33. return
  34. print(root.data)
  35. self.DFS(root.left)
  36. self.DFS(root.right)
  37. def DFS_STACK(self,root): #基于栈数据结构实现的深度遍历
  38. if root == None:
  39. return
  40. stack = []
  41. stack.append(root)
  42. while stack:
  43. now_node = stack.pop()
  44. print(now_node.data)
  45. if now_node.right != None:
  46. stack.append(now_node.right)
  47. if now_node.left != None:
  48. stack.append(now_node.left)
  49. if __name__ == '__main__':
  50. # 主函数
  51. datas = [1,2, 3, 4, 5, 6, 7, 8, 9]
  52. tree = Tree() # 新建一个树对象
  53. for data in datas:
  54. tree.add(data) # 逐个加入树的节点
  55. print('递归实现前序遍历:')
  56. tree.DFS_STACK(tree.root)