Python|二叉树的三种深度遍历

算法与编程之美

修改于 2020-04-15 15:30:24

5240

修改于 2020-04-15 15:30:24

文章被收录于专栏：算法与编程之美

1 前言

上次用python代码实现了二叉树，这次将会实现二叉树的几种遍历方法，来更好的解析二叉树的结构特点。分别是一种广度遍历(上篇博客已经提到)，和三种深度遍历方法：先序遍历，中序遍历，后序遍历。

2 遍历方法的实现

先序遍历

遍历顺序：根==》左子树==》右子树

实现代码：


def pre(self,node):#定义一个先序遍历的方法

if node is None:#判断节点是否为空，为空则返回

    return

    print(node.elem,end=' ')#打印遍历的节点

self.pre(node.left)#递归左子树

    self.pre(node.right)#递归右子树

中序遍历

遍历顺序：左子树==》根 ==》右子树

实现代码：


def md(self,node):#定义一个中序遍历的方法

    if node is None: #判断节点是否为空，为空则返回

        return

    self.md(node.left) #递归左子树

    print(node.elem,end=' ') #打印遍历的节点

    self.md(node.right) #递归右子树

后序遍历

遍历顺序：左子树==》右子树==》根

实现代码：


def bhd(self,node):#定义一个后序遍历的方法

    if node is None:#判断节点是否为空，为空返回

        return

    self.bhd(node.left)#递归左子树

    self.bhd(node.right)#递归右子树

    print(node.elem,end=' ')#打印遍历的节点

打印结果：


if __name__ == "__main__":

    tree=Tree()

    tree.add(0)

    tree.add(1)

    tree.add(2)   

    tree.add(3)

    tree.add(4)

    tree.add(5)

    tree.add(6)

    tree.add(7)

    tree.add(8)

    tree.pre(tree.root)#打印先序遍历的值

    print(' ')

    tree.md(tree.root)#打印中序遍历的值

    print(' ')

    tree.bhd(tree.root)#打印后序遍历的值

    print(' ')

#输出：

# 0 1 3 7 8 4 2 5 6 先序遍历的值

# 7 3 8 1 4 0 5 2 6 中序遍历的值

# 7 8 3 4 1 5 6 2 0 后序遍历的值

3 总结

二叉树的三种深度遍历的实现主要是利用了递归，利用不同的遍历顺序来改变递归的顺序和节点打印的顺序来实现，利用这一特点就可以用python快速的实现三种遍历方法了。

END

主编 | 王文星

责编 | 王卓越

where2go 团队

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-04-04，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树