python数据结构与算法-14_树与二叉树

树和二叉树

前面我们讲了两种使用分治和递归解决排序问题的归并排序和快速排序,堆排序先就此打住,因为涉及到树的概念,所以我们先来讲讲树。
讲完了树之后后面我们开始介绍一种有用的数据结构堆(heap), 以及借助堆来实现的堆排序,相比前两种排序算法要稍难理解和实现一些。

这里先简单讲讲树的概念。树结构是一种包括节点(nodes)和边(edges)的拥有层级关系的一种结构, 它的形式和家谱树非常类似:

在这里插入图片描述

如果你了解 linux 文件结构(tree 命令),它的结构也是一棵树。我们快速看下树涉及到的一些概念:
在这里插入图片描述

  • 根节点(root): 树的最上层的节点,任何非空的树都有一个节点
  • 路径(path): 从起始节点到终止节点经历过的边
  • 父亲(parent):除了根节点,每个节点的上一层边连接的节点就是它的父亲(节点)
  • 孩子(children): 每个节点由边指向的下一层节点
  • 兄弟(siblings): 同一个父亲并且处在同一层的节点
  • 子树(subtree): 每个节点包含它所有的后代组成的子树
  • 叶子节点(leaf node): 没有孩子的节点成为叶子节点

二叉树

了解完树的结构以后,我们来看树结构里一种简单但是却比较常用的树-二叉树。
二叉树是一种简单的树,它的每个节点最多只能包含两个孩子,以下都是一些合法的二叉树:

在这里插入图片描述
在这里插入图片描述

通过上边这幅图再来看几个二叉树相关的概念:

  • 节点深度(depth): 节点对应的 level 数字
  • 树的高度(height): 二叉树的高度就是 level 数 + 1,因为 level 从 0开始计算的
  • 树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数
  • 树的 size:二叉树的节点总个数。

一棵 size 为 n 的二叉树高度最多可以是 n,最小的高度是 $ \lfloor lgn \rfloor + 1 $,这里 log 以 2 为底简写为
lgn,和算法导论保持一致。这个结果你只需要用高中的累加公式就可以得到。

一些特殊的二叉树

在了解了二叉树的术语和概念之后,我们来看看一些特殊的二叉树,后续章节我们会用到:

满二叉树(full binary tree)

如果每个内部节点(非叶节点)都包含两个孩子,就成为满二叉树。下边是一些例子,它可以有多种形状:

在这里插入图片描述

完美二叉树(perfect binary tree)

当所有的叶子节点都在同一层就是完美二叉树,毫无间隙填充了 h 层。

在这里插入图片描述

完全二叉树(complete binary tree)

当一个高度为 h 的完美二叉树减少到 h-1,并且最底层的槽被毫无间隙地从左到右填充,我们就叫它完全二叉树。
下图就是完全二叉树的例子:

在这里插入图片描述

二叉树的表示

说了那么多,那么怎么表示一棵二叉树呢?其实你发现会和链表有一些相似之处,一个节点,然后节点需要保存孩子的指针,我以构造下边这个二叉树为例子:
我们先定义一个类表示节点:

在这里插入图片描述

class BinTreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

当然和链表类似,root 节点是我们的入口,于是乎定义一个 二叉树:

class BinTree(object):
    def __init__(self, root=None):
        self.root = root

怎么构造上图中的二叉树呢,似乎其他课本没找到啥例子(有些例子是写了一堆嵌套节点来定义,很难搞清楚层次关系),我自己定义了一种方法,首先我们输入节点信息,仔细看下边代码,叶子节点的 left 和 right 都是 None,并且只有一个根节点 A:

node_list = [
    {'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
    {'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
    {'data': 'D', 'left': None, 'right': None, 'is_root': False},
    {'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
    {'data': 'H', 'left': None, 'right': None, 'is_root': False},
    {'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
    {'data': 'F', 'left': None, 'right': None, 'is_root': False},
    {'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
    {'data': 'I', 'left': None, 'right': None, 'is_root': False},
    {'data': 'J', 'left': None, 'right': None, 'is_root': False},
]

然后我们给 BinTreeNode 定义一个 build_from 方法,当然你也可以定义一种自己的构造方法:

class BinTree(object):
    def __init__(self, root=None):
        self.root = root

    @classmethod
    def build_from(cls, node_list):
        """通过节点信息构造二叉树
        第一次遍历我们构造 node 节点
        第二次遍历我们给 root 和 孩子赋值
        最后我们用 root 初始化这个类并返回一个对象

        :param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
        """
        node_dict = {}
        for node_data in node_list:
            data = node_data['data']
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])
            node.right = node_dict.get(node_data['right'])
        return cls(root)
btree = BinTree.build_from(node_list)

大功告成,这样我们就构造了一棵二叉树对象。下边我们看看它的一些常用操作。

二叉树的遍历

不知道你有没有发现,二叉树其实是一种递归结构,因为单独拿出来一个 subtree 子树出来,其实它还是一棵树。那遍历它就很方便啦,我们可以直接用递归的方式来遍历它。但是当处理顺序不同的时候,树又分为三种遍历方式:

  • 先(根)序遍历: 先处理根,之后是左子树,然后是右子树
  • 中(根)序遍历: 先处理左子树,之后是根,最后是右子树
  • 后(根)序遍历: 先处理左子树,之后是右子树,最后是根

我们来看下实现,其实算是比较直白的递归函数:

class BinTreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right


class BinTree(object):
    def __init__(self, root=None):
        self.root = root

    @classmethod
    def build_from(cls, node_list):
        """通过节点信息构造二叉树
        第一次遍历我们构造 node 节点
        第二次遍历我们给 root 和 孩子赋值

        :param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
        """
        node_dict = {}
        for node_data in node_list:
            data = node_data['data']
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])
            node.right = node_dict.get(node_data['right'])
        return cls(root)

    def preorder_trav(self, subtree):
        """ 先(根)序遍历

        :param subtree:
        """
        if subtree is not None:
            print(subtree.data)    # 递归函数里先处理根
            self.preorder_trav(subtree.left)   # 递归处理左子树
            self.preorder_trav(subtree.right)    # 递归处理右子树


node_list = [
    {'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
    {'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
    {'data': 'D', 'left': None, 'right': None, 'is_root': False},
    {'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
    {'data': 'H', 'left': None, 'right': None, 'is_root': False},
    {'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
    {'data': 'F', 'left': None, 'right': None, 'is_root': False},
    {'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
    {'data': 'I', 'left': None, 'right': None, 'is_root': False},
    {'data': 'J', 'left': None, 'right': None, 'is_root': False},
]
btree = BinTree.build_from(node_list)
btree.preorder_trav(btree.root)    # 输出 A, B, D, E, H, C, F, G, I, J

怎么样是不是挺简单的,比较直白的递归函数。如果你不明白,视频里我们会画个图来说明。

二叉树层序遍历

除了递归的方式遍历之外,我们还可以使用层序遍历的方式。层序遍历比较直白,就是从根节点开始按照一层一层的方式遍历节点。
我们可以从根节点开始,之后把所有当前层的孩子都按照从左到右的顺序放到一个列表里,下一次遍历所有这些孩子就可以了。

    def layer_trav(self, subtree):
        cur_nodes = [subtree]  # current layer nodes
        next_nodes = []
        while cur_nodes or next_nodes:
            for node in cur_nodes:
                print(node.data)
                if node.left:
                    next_nodes.append(node.left)
                if node.right:
                    next_nodes.append(node.right)
            cur_nodes = next_nodes  # 继续遍历下一层
            next_nodes = []

还有一种方式就是使用一个队列,之前我们知道队列是一个先进先出结构,如果我们按照一层一层的顺序从左往右把节点放到一个队列里,
也可以实现层序遍历:

    def layer_trav_use_queue(self, subtree):
        q = Queue()
        q.append(subtree)
        while not q.empty():
            cur_node = q.pop()
            print(cur_node.data)
            if cur_node.left:
                q.append(cur_node.left)
            if cur_node.right:
                q.append(cur_node.right)


from collections import deque
class Queue(object):  # 借助内置的 deque 我们可以迅速实现一个 Queue
    def __init__(self):
        self._items = deque()

    def append(self, value):
        return self._items.append(value)

    def pop(self):
        return self._items.popleft()

    def empty(self):
        return len(self._items) == 0

反转二叉树

之所以单拎出来说这个是因为 mac 下著名的 brew 工具作者据说是因为面试 google 白板编程没写出来反转二叉树跪了。然后人家就去了苹果 😂。其实吧和遍历操作相比也没啥太大区别,递归交换就是了:

    def reverse(self, subtree):
        if subtree is not None:
            subtree.left, subtree.right = subtree.right, subtree.left
            self.reverse(subtree.left)
            self.reverse(subtree.right)

练习题

  • 请你完成二叉树的中序遍历和后序遍历以及单元测试
  • 树的遍历我们用了 print,请你尝试换成一个 callback,这样就能自定义处理树节点的方式了。
  • 请问树的遍历操作时间复杂度是多少?假设它的 size 是 n
  • 你能用非递归的方式来实现树的遍历吗?我们知道计算机内部使用了 stack,如果我们自己模拟如何实现?请你尝试完成
  • 只根据二叉树的中序遍历和后序遍历能否确定一棵二叉树?你可以举一个反例吗?

源码

# -*- coding: utf-8 -*-


from collections import deque


class Queue(object):  # 借助内置的 deque 我们可以迅速实现一个 Queue
    def __init__(self):
        self._items = deque()

    def append(self, value):
        return self._items.append(value)

    def pop(self):
        return self._items.popleft()

    def empty(self):
        return len(self._items) == 0


class Stack(object):
    def __init__(self):
        self._items = deque()

    def push(self, value):
        return self._items.append(value)

    def pop(self):
        return self._items.pop()

    def empty(self):
        return len(self._items) == 0


class BinTreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right


class BinTree(object):
    def __init__(self, root=None):
        self.root = root

    @classmethod
    def build_from(cls, node_list):
        """build_from

        :param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
        """
        node_dict = {}
        for node_data in node_list:
            data = node_data['data']
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])
            node.right = node_dict.get(node_data['right'])
        return cls(root)

    def preorder_trav(self, subtree):
        if subtree is not None:
            print(subtree.data)
            self.preorder_trav(subtree.left)
            self.preorder_trav(subtree.right)

    def preorder_trav_use_stack(self, subtree):
        """递归的方式其实是计算机帮我们实现了栈结构,我们可以自己显示的用栈来实现"""
        s = Stack()
        if subtree:
            s.push(subtree)
            while not s.empty():
                top_node = s.pop()
                print(top_node.data)    # 注意这里我用了 print,你可以用 yield 产出值然后在调用的地方转成 list
                if top_node.right:
                    s.push(top_node.right)
                if top_node.left:
                    s.push(top_node.left)

    def inorder_trav(self, subtree):
        if subtree is not None:
            self.inorder_trav(subtree.left)
            print(subtree.data)
            self.inorder_trav(subtree.right)

    def yield_inorder(self, subtree):  # for val in yield_inorder(root): print(val)
        if subtree:
            yield from self.inorder(subtree.left)
            yield subtree.val
            yield from self.inorder(subtree.right)

    def reverse(self, subtree):
        if subtree is not None:
            subtree.left, subtree.right = subtree.right, subtree.left
            self.reverse(subtree.left)
            self.reverse(subtree.right)

    def layer_trav(self, subtree):
        cur_nodes = [subtree]
        next_nodes = []
        while cur_nodes or next_nodes:
            for node in cur_nodes:
                print(node.data)
                if node.left:
                    next_nodes.append(node.left)
                if node.right:
                    next_nodes.append(node.right)
            cur_nodes = next_nodes  # 继续遍历下一层
            next_nodes = []

    def layer_trav_use_queue(self, subtree):
        q = Queue()
        q.append(subtree)
        while not q.empty():
            cur_node = q.pop()
            print(cur_node.data)
            if cur_node.left:
                q.append(cur_node.left)
            if cur_node.right:
                q.append(cur_node.right)


node_list = [
    {'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
    {'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
    {'data': 'D', 'left': None, 'right': None, 'is_root': False},
    {'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
    {'data': 'H', 'left': None, 'right': None, 'is_root': False},
    {'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
    {'data': 'F', 'left': None, 'right': None, 'is_root': False},
    {'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
    {'data': 'I', 'left': None, 'right': None, 'is_root': False},
    {'data': 'J', 'left': None, 'right': None, 'is_root': False},
]


btree = BinTree.build_from(node_list)
print('====先序遍历=====')
btree.preorder_trav(btree.root)

print('====使用 stack 实现先序遍历=====')
btree.preorder_trav_use_stack(btree.root)

print('====层序遍历=====')
btree.layer_trav(btree.root)
print('====用队列层序遍历=====')
btree.layer_trav_use_queue(btree.root)

btree.reverse(btree.root)
print('====反转之后的结果=====')
btree.preorder_trav(btree.root)

延伸阅读

  • 《Data Structures and Algorithms in Python》 13 章 Binary Trees
  • https://www.geeksforgeeks.org/iterative-preorder-traversal/

Leetcode 练习

  • leetcode binary-tree-preorder-traversal
    二叉树的先序遍历

  • leetcode binary-tree-inorder-traversal/
    二叉树的中序遍历

  • leetcode binary-tree-postorder-traversal
    二叉树的后序遍历

  • leetcode binary-tree-right-side-view
    使用树的层序遍历我们能实现一个树的左右视图,比如从一个二叉树的左边能看到哪些节点。 请你尝试做这个练习题

  • leetcode construct-binary-tree-from-preorder-and-postorder-traversal
    根据二叉树的 前序和后序遍历,返回一颗完整的二叉树。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/180177.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

豪华程度堪比飞机头等舱?奔驰在北美发布Tourrider系列巴士

今年三月,奔驰工厂附近出现了一台特殊的测试车。其突出的前保险杠以及竖置双风挡等特殊配置,都在暗示着它并非是为欧洲市场打造。 根据特征推测,这台车应该是为北美市场打造。 就在昨天,奔驰发布了旗下全新Tourrider系列豪华客车&…

Unity中颜色空间Gamma与Linear

文章目录 前言一、人眼对光照的自适应1、光照强度与人眼所见的关系2、巧合的是,早期的电子脉冲显示屏也符合这条曲线3、这两条曲线都巧合的符合 y x^2.2^(Gamma2.2空间) 二、Gamma矫正1、没矫正前,人眼看电子脉冲显示屏&#xff…

二叉搜索树再升级——红黑树

二叉搜索树再升级——红黑树 红黑树的概念红黑树的插入uncle为granfather的右孩子uncle结点为红色uncle结点为空或黑色 uncle为granfather的左孩子 红黑树的概念 之前我们学习了AVL树,这是一种判断左右子树高度来严格控制总体树的高度的树。条件相对来说比较苛刻。…

黑马点评笔记 redis缓存三大问题解决

文章目录 缓存问题缓存穿透问题的解决思路编码解决商品查询的缓存穿透问题 缓存雪崩问题及解决思路缓存击穿问题及解决思路问题分析使用锁来解决代码实现 逻辑过期方案代码实现 缓存问题 我们熟知的是用到缓存就会遇到缓存三大问题: 缓存穿透缓存击穿缓存雪崩 接…

Kafka 常用功能总结(不断更新中....)

kafka 用途 业务中我们经常用来两个方面 1.发送消息 2.发送日志记录 kafka 结构组成 broker:可以理解成一个单独的服务器,所有的东西都归属到broker中 partation:为了增加并发度而做的拆分,相当于把broker拆分成不同的小块&…

基于Python实现汽车销售数据可视化+预测【500010086.1】

导入模块 import numpy as np import pandas as pd from pylab import mpl import plotly.express as px import matplotlib.pyplot as plt import seaborn as sns设置全局字体 plt.rcParams[font.sans-serif][kaiti]获取数据 total_sales_df pd.read_excel(r"./data/中…

从根到叶:随机森林模型的深入探索

一、说明 在本综合指南中,我们将超越基础知识。当您盯着随机森林模型的文档时,您将不再对“节点杂质”、“加权分数”或“成本复杂性修剪”等术语感到不知所措。相反,我们将剖析每个参数,阐明其作用和影响。通过理论和 Python 实践…

【STM32外设系列】GPS定位模块(ATGM336H)

🎀 文章作者:二土电子 🌸 关注公众号获取更多资料! 🐸 期待大家一起学习交流! 文章目录 一、GPS模块简介二、使用方法2.1 引脚介绍2.2 数据帧介绍2.3 关于不同的启动方式 三、前置知识3.1 strstr函数3.2…

【洛谷算法题】P5714-肥胖问题【入门2分支结构】

👨‍💻博客主页:花无缺 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5714-肥胖问题【入门2分支结构】🌏题目描述🌏输入格式&a…

实在智能携“TARS大模型”入选“2023中国数据智能产业AI大模型先锋企业”

近日,由数据猿与上海大数据联盟联合主办的“2023企业数智化转型升级发展论坛”在上海圆满收官。 论坛颁奖典礼上,《2023中国数据智能产业AI大模型先锋企业》等六大榜单正式揭晓,旨在表彰在AI领域为数智化升级取得卓越成就和突出贡献的企业&am…

【Flask使用】全知识md文档,4大部分60页第3篇:Flask模板使用和案例

本文的主要内容:flask视图&路由、虚拟环境安装、路由各种定义、状态保持、cookie、session、模板基本使用、过滤器&自定义过滤器、模板代码复用:宏、继承/包含、模板中特有变量和函数、Flask-WTF 表单、CSRF、数据库操作、ORM、Flask-SQLAlchemy…

深入浅出理解libevent——2万字总结

概述 libevent,libev,libuv都是c实现的异步事件库,注册异步事件,检测异步事件,根据事件的触发先后顺序,调用相对应回调函数处理事件。处理的事件包括:网络 io 事件、定时事件以及信号事件。这三个事件驱动着服务器的运…

中国智能汽车这一年,主打一个“卷”

文丨刘俊宏 “这才刚过去半年多,汽车行业又更新了一轮。”一位车评人在广州车展感叹道。 作为每年最后一个A级车展,广州车展向来被视为中国车市的“风向标”。相比上海车展“拥抱汽车行业新时代”、成都车展“驭见未来”的主题,广州车展“新…

为什么鼠标按键释放后才执行对应的动作?

如果你留心观察的话,你会发现这样一个事实:大部分的软件的用户体验中,一般都是在鼠标按键释放后,才会执行相应的动作,而不是按下的时候。例如,当我们按下开始菜单的时候,不会有任何动作发生&…

数据库基础入门 — SQL运算符

我是南城余!阿里云开发者平台专家博士证书获得者! 欢迎关注我的博客!一同成长! 一名从事运维开发的worker,记录分享学习。 专注于AI,运维开发,windows Linux 系统领域的分享! 本…

2023 年亚马逊黑色星期五和网络星期一的企业电子商务指南

亚马逊黑色星期五和网络星期一 周末即将到来!感恩节于 11 月 23 日举行,紧接着是 24 日黑色星期五和 27 日网络星期一。您的亚马逊业务准备好应对大量涌入了吗? 我们相信您已经准备好黑色星期五优惠并准备好库存,以确保您有足够的…

一键重装系统Win10专业版教程

在电脑操作过程中,用户如果遇到无法解决的系统问题,就可以考虑直接重新系统。现在,用户想要重新安装一下Win10专业版系统,但是不清楚具体的重装操作步骤。接下来小编给大家介绍轻松重装Win10专业版系统的详细步骤。 推荐下载 系统…

怎么快速卸载office365

怎么快速卸载office365 根据官网提供的两种解决方案即点即用或MSIMicrosoft Store 根据官网提供的两种解决方案 官网地址:https://support.microsoft.com/zh-cn/office/%E4%BB%8E-pc-%E5%8D%B8%E8%BD%BD-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8#OfficeVersio…

如何在AppLink配置金蝶云星空预算使用单流程

上一篇有提到金蝶云星空如何通过AppLink平台配置销售订单操作,这次来演示下如何“保存预算使用单”、“调拨单定时自动审核”以及“预算使用单反审核后删除”操作。 根据请求数据保存预算使用单 当webhook接收到数据时触发流程 步骤1:根据webhook的请…

监控员工上网有什么软件丨三款好用的员工上网管理软件推荐

监控员工上网行为是企业管理中不可或缺的一部分,因此,选择一款好的监控员工上网的软件至关重要。目前市场上存在多种监控员工上网的软件,它们具有各种特点和功能,但企业需要仔细评估和选择。 一、域之盾软件 这是一款优秀的监控员…