python实现二叉树数据结构的多种遍历方式-阿里云开发者社区

开发者社区> python之战> 正文

python实现二叉树数据结构的多种遍历方式

简介: 二叉树的遍历比较有意思,首先是遍历的方式比较多,大的来说分为深度遍历和广度遍历,深度遍历又分为先序遍历/中序遍历/后序遍历,其中深度遍历用递归来实现,广度遍历用队列来实现。 深度遍历和广度遍历是相对的概念,深度遍历是沿着树的深度遍历树的节点,尽可能深的搜索树的分支;广度遍历是从树的根层级开始一层一...
+关注继续查看

二叉树的遍历比较有意思,首先是遍历的方式比较多,大的来说分为深度遍历和广度遍历,深度遍历又分为先序遍历/中序遍历/后序遍历,其中深度遍历用递归来实现,广度遍历用队列来实现。

深度遍历和广度遍历是相对的概念,深度遍历是沿着树的深度遍历树的节点,尽可能深的搜索树的分支;广度遍历是从树的根层级开始一层一层的遍历,遍历完上一层再遍历下一层;如下:

2019-04-12-22_56_01.png

深度遍历顺序:0-1-3-7-8-4-9-2-5-6(先序遍历)

广度遍历顺序:0-1-2-3-4-5-6-7-8-9


但对于深度遍历而言还有三种方式:先序遍历/中序遍历/后序遍历;先序遍历的顺序为:根节点->左子树->右子树;中序遍历为:左子树->根节点->右子树;当然后序遍历是:左子树->右子树->根节点;其中的序指的是根节点相对于左右节点的遍历位置。

在上二叉树中我们按照深度遍历的三种方式得到的顺序如下:

先序遍历:0-1-3-7-8-4-9-2-5-6

中序遍历:7-3-8-1-9-4-0-5-2-6

后序遍历:7-8-3-9-4-1-5-6-2-0

注意:先序遍历是从上往下看,中序遍历和后续遍历是从下往上看,从哪里开始就决定了什么相对简单二叉树的权重。

深度遍历的实现:

class Node:
    """节点类"""
    def __init__(self, elem, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """树类"""
    def __init__(self, root=None):
        self._root = root

    def add(self, item):
        node = Node(item)
        if not self._root:
            self._root = node
            return
        queue = [self._root]
        while queue:
            cur = queue.pop(0)
            if not cur.lchild:
                cur.lchild = node
                return
            elif not cur.rchild:
                cur.rchild = node
                return
            else:
                queue.append(cur.rchild)
                queue.append(cur.lchild)

    def preorder(self, root):
        """
        先序遍历-递归实现
        :param root:
        :return:
        """

        if not root:
            raise ValueError("ROOT ERROR")
        print(root.elem)
        self.preorder(root.lchild)
        self.preorder(root.rchild)

    def inorder(self, root):
        """
        中序遍历-递归实现
        :param root:
        :return:
        """

        if not root:
            raise ValueError("ROOT ERROR")
        self.inorder(root.lchild)
        print(root.elem)
        self.inorder(root.rchild)

    def postorder(self, root):
        """
        后序遍历-递归实现
        :param root: 
        :return: 
        """

        if not root:
            raise ValueError("ROOT ERROR")
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.elem)


广度遍历的实现;

class Node:
    """节点类"""
    def __init__(self, elem, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """树类"""
    def __init__(self, root=None):
        self._root = root

    def breadth_travel(self, root):
        """
        广度优先-队列实现
        :param root:
        :return:
        """

        if not root:
            raise ValueError("ROOT ERROR")
        queue = [root]
        while queue:
            node = queue.pop(0)
            print(node.elem)
            if node.lchild:
                queue.append(node.lchild)
            elif node.rchild:
                queue.append(node.rchild)


递归函数使得二叉树的遍历操作更加的简洁,上面的深度遍历的三种方式除了递归以外,还可以使用堆栈的结构来实现,如果感兴趣可自行实现。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构之树、森林和二叉树的转换
树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。
759 0
采用栈数据结构的二叉树非递归遍历
  【前言】树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历。对于二叉树,每个节点至多有两个子节点(特别的称为左,右子节点),又有中序遍历。由于树自身具有的递归性,这些遍历函数使用递归函数很容易实现,代码也非常简洁。
892 0
数据结构之Trie树
1、什么是Trie树    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
803 0
Python数据结构
说实话,数据结构是一门很难的课程,我也没有系统的学过,如果有兴趣的同学可以去看看数据结构的书籍,以后可以和我讨论一下,在这里说说我自己的理解吧。 数据结构就是数据以什么样的形式存储;而以什么样的形式存储就得用相应的方法去处理分析数据(这是最近看数据分析的一点小体会),今天不过多的展开,介绍4个python的内置数据结构,分别是列表(list),字典(dict),元组(tuple),集合(set)。
599 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
8478 0
SpringCloud实现分库分表模式下,数据库实时扩容方案
本文源码:GitHub·点这里 || GitEE·点这里 一、项目结构 1、工程结构 2、模块命名 shard-common-entity: 公共代码块 shard-open-inte: 开放接口管理 shard-eureka-7001: 注册中心 shard-tw...
3047 0
C++、Python、数据结构与算法、计算机基础、数据库教程汇总!
C++、Python、数据结构与算法、计算机基础、数据库教程汇总!
41 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载