Python递归和非递归实现二叉搜索树的三种遍历

本文阅读 1 分钟
首页 Python笔记 正文

利用递归以及非递归的方式实现二叉搜索树的前序遍历、中序遍历和后序遍历

  1. class TreeNode:
  2. def __init__(self, x):
  3. self.val = x
  4. self.left = None
  5. self.right = None
  6. class Tranversal:
  7. # preorder without recursion
  8. def preOrder(self, root):
  9. if root == None:
  10. return None
  11. pNode, treeStack = root, []
  12. while pNode or len(treeStack) > 0:
  13. while pNode:
  14. print(pNode.val)
  15. treeStack.append(pNode)
  16. pNode = pNode.left
  17. if len(treeStack) > 0:
  18. pNode = treeStack.pop()
  19. pNode = pNode.right
  20. # preorder with recursion
  21. def preOrderRec(self, root):
  22. if root != None:
  23. print(root.val)
  24. self.preOrderRec(root.left)
  25. self.preOrderRec(root.right)
  26. # inorder without recursion
  27. def inOrder(self, root):
  28. if root == None:
  29. return
  30. pNode, treeStack = root, []
  31. while pNode or len(treeStack) > 0:
  32. while pNode:
  33. treeStack.append(pNode)
  34. pNode = pNode.left
  35. if len(treeStack) > 0:
  36. pNode = treeStack.pop()
  37. print(pNode.val)
  38. pNode = pNode.right
  39. # inorder with recursion
  40. def inOrderRec(self, root):
  41. if root != None:
  42. self.inOrderRec(root.left)
  43. print(root.val)
  44. self.inOrderRec(root.right)
  45. # postorder without recursion
  46. def postOrder(self, root):
  47. if root == None:
  48. return
  49. cur, pre, treeStack = root, None, [] # cur:current Node, pre: pre visited Node
  50. treeStack.append(root)
  51. while len(treeStack) > 0:
  52. cur = treeStack[-1]
  53. # current node doesn't have child nodes or child nodes have been visited
  54. if (cur.left == None and cur.right == None) or (pre != None and (pre == cur.left or pre == cur.right)):
  55. print(cur.val)
  56. pre = treeStack.pop()
  57. else:
  58. if cur.right != None:
  59. treeStack.append(cur.right)
  60. if cur.left != None:
  61. treeStack.append(cur.left)
  62. # postorder with cursion
  63. def postOrderRec(self, root):
  64. if root:
  65. self.postOrderRec(root.left)
  66. self.postOrderRec(root.right)
  67. print(root.val)
  68. pNode1 = TreeNode(10)
  69. pNode2 = TreeNode(6)
  70. pNode3 = TreeNode(14)
  71. pNode4 = TreeNode(4)
  72. pNode5 = TreeNode(8)
  73. pNode6 = TreeNode(12)
  74. pNode7 = TreeNode(16)
  75. pNode1.left = pNode2
  76. pNode1.right = pNode3
  77. pNode2.left = pNode4
  78. pNode2.right = pNode5
  79. pNode3.left = pNode6
  80. pNode3.right = pNode7
  81. S = Tranversal()
  82. S.postOrder(pNode1)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python输出连续质数序列
« 上一篇 01-21
Python求树的宽度
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18490 篇
  • 评论总数:
    53245 条
  • 标签总数:
    8863 个
  • 总浏览量:
    21544419 次
  • 最后更新:
    2天前

最多点赞

随便看看

标签TAG