python二叉树的深度遍历和广度遍历

image description

python二叉树的深度遍历和广度遍历

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

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

深度遍历顺序: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)

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

    ArithmeticJia         3         1558         Python         2369    

David Ramon

ArithmeticJia

www.guanacossj.com

Life is Short,You need Python

Related Posts

You may like these post too

image description

python中的GIL锁

为什么我们说python中无法实现真正的多线程呢,这是因为在C语言写的python解释器中存在全局解释器锁,由于全局解释器锁的存在,在同一时间内,python解释器只能运行一个线程的代码,这大大影响了python多线程的性能。而这个解释器锁由于历史原因,现在几乎无法消除。 python GIL

image description

python多进程和进程池

##写在最前面: linux下可使用 fork 函数 通常使用 multiprocessing更常见 我们分别使用单进程和多进程处理run函数 ```python import time,os from multiprocessing import P

Comments on this post

3 comments

image description

18011834

ccc

image description

林海里的帆

发现新大陆,这个博客页面和动效都做的很漂亮,但是有些小bug,比如很多网页点进去是404,然后有些(蛮多)评论点不开,但是前端的页面设计真的很赞,干净清爽,黑白橙搭在一起爱了!

REPLY

Leave a comment

it’s easy to post a comment

image description
image description
image description
image description
image description
image description
image description
image description
image description

Copyright © 2019.Company name All rights reserved.苏ICP备19007197号