python-二叉树的前序遍历、中序遍历和后序遍历

如何理解前序遍历、中序遍历和后序遍历？

前序遍历是指先访问根节点，然后依次访问左子树，最后访问右子树。

中序遍历是指先访问左子树，然后访问根节点，最后访问右子树。

后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。

举例展示三种遍历方式

例如，一棵二叉树如下：

     A/   \B     C/ \   / \
D   E  F   G

前序遍历：A B D E C F G

中序遍历：D B E A F C G

后序遍历：D E B F G C A

如何用python实现前序遍历、中序遍历和后序遍历？

前序遍历：

def preorder(tree):if tree:print(tree.getRootVal())preorder(tree.getLeftChild())preorder(tree.getRightChild())

中序遍历：

def inorder(tree):if tree != None:inorder(tree.getLeftChild())print(tree.getRootVal())inorder(tree.getRightChild())

后序遍历：

def postorder(tree):if tree != None:postorder(tree.getLeftChild())postorder(tree.getRightChild())print(tree.getRootVal())

为什么实现前序遍历、中序遍历和后序遍历的原理都是递归？

因为递归可以把复杂的问题分解为规模较小的相同问题，这样就可以把一个大问题分解成多个小问题，每个小问题都可以通过递归的方式解决。在二叉树的遍历中，每个节点都可以看成是一个小的子树，通过递归的方式可以轻松的实现前序遍历、中序遍历和后序遍历。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！