首页 > 代码库 > 用递归方式遍历二叉树
用递归方式遍历二叉树
问题
用递归方式遍历二叉树
思路说明
遍历二叉树的方法有广度优先和深度优先两类,下面阐述的是深度优先。
以下图的二叉树为例:
先定义三个符号标记:
- 访问结点本身(N)
- 遍历该结点的左子树(L)
- 遍历该结点的右子树(R)
- 前序遍历(PreorderTraversal,NLR):先访问根结点,然后遍历其左右子树
- 中序遍历(InorderTraversal,LNR):先访问左子树,然后访问根节点,再访问右子树
- 后序遍历(PostorderTraversal,LRN):先访问左右子树,再访问根结点
- 层序遍历(levelorderTraversal):按照从上到下的层顺序访问
上面的数,按照以上四种方式遍历,得到的结果依次是:
1. preorder: 1 2 4 7 5 3 6 8 9
2. inorder: 7 4 2 5 1 8 6 9 3
3. postorder: 7 4 5 2 8 9 6 3 1
4. level-order: 1 2 3 4 5 6 7 8 9
下面用递归的方式,解决此题。
解决(Python)
#! /usr/bin/env python #coding:utf-8 from collections import namedtuple from sys import stdout Node = namedtuple('Node', 'data, left, right') tree = Node(1, Node(2, Node(4, Node(7, None, None), None), Node(5, None, None)), Node(3, Node(6, Node(8, None, None), Node(9, None, None)), None)) #前序(NLR) def preorder(node): if node is not None: print node.data, preorder(node.left) preorder(node.right) #中序(LNR) def inorder(node): if node is not None: inorder(node.left) print node.data, inorder(node.right) #后序(LRN) def postorder(node): if node is not None: postorder(node.left) postorder(node.right) print node.data, #层序(levelorder) def levelorder(node, more=None): if node is not None: if more is None: more = [] more += [node.left, node.right] print node.data, if more: levelorder(more[0], more[1:]) if __name__=="__main__" print ' preorder: ', preorder(tree) print '\t\n inorder: ', inorder(tree) print '\t\n postorder: ', postorder(tree) print '\t\nlevelorder: ', levelorder(tree) print '\n'
声明
源码请到我的github中的algorithm查找,文件名为:binary_tree_traversal.py。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。