首页 > 编程语言 >Python 数据结构——二叉树(最最最最最实用的二叉树教程)

Python 数据结构——二叉树(最最最最最实用的二叉树教程)

时间:2024-09-01 12:56:52浏览次数:13  
标签:node 最最 遍历 result Python right 二叉树 root left

本文章以实用为主,所以不多废话直接开整

本文所介绍的二叉树是最基础的二叉树,不是二叉搜索树,也不是平衡二叉树,就基本的二叉树

二叉树的创建

基本二叉树的创建其实比链表还要简单,只需创建一个节点的类即可,随后用指针将其串起来。不同于链表的是,二叉树为一个父节点连接到两个子节点,若还要加入新的节点,那么此时的子节点将会变成新加入节点的父节点,以此类推,每一个父节点最多只有两个节点(所以叫二叉树)
 

我们将上述图中的二叉树写成代码的形式(如下) 

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

tree = node(3)
tree.left = node(5)
tree.right = node(1)
tree.left.left = node(6)
tree.left.right = node(2)
tree.right.left = node(0)
tree.right.right = node(8)
tree.left.right.left = node(7)
tree.left.right.right = node(4)

创建基础二叉树代码

tree = node(data)  #  表示最初的祖先节点

tree.left = node(data)  #  表示祖先节点的左孩子

tree.right = node(data)  #  表示祖先节点的右孩子

tree.left.left = node(data)  #  表示祖先节点的左孩子的左孩子

..............................

以此类推即可,有点类似于套娃

二叉树的遍历

二叉树的遍历有别于线性表的遍历,很明显,二叉树是一个复杂的二维结构,所以二叉树有很多不同的遍历方法,其中常见的是:先序遍历中序遍历后序遍历以及层序遍历

先序遍历

先序遍历中序遍历后序遍历其实本质上都差不多,只不过是遍历顺序的不同罢了

先序遍历:就是先遍历根节点,其次是左孩子,最后是右孩子

def preorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.append(root.data)
        result.extend(preorder_traversal(root.left))
        result.extend(preorder_traversal(root.right))
        return result

上述代码中,我们通过递归的方式遍历二叉树,可能有点小难懂,我来仔细解释一下:

此函数其实每次都会往 result 内塞入一个节点,即当前节点,随后对左子树进行递归,然后对子树进行递归,即可完成  根->左->右  的遍历,即先序遍历

知道上述代码的逻辑之后,稍微修改一些即可得到中序遍历以及后序遍历

中序遍历

中序遍历:就是先遍历左孩子,其次是根节点,最后是右孩子

def inorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.extend(inorder_traversal(root.left))
        result.append(root.data)
        result.extend(inorder_traversal(root.right))
        return result

有没有发现上述代码和有点小眼熟,其实上述代码就是先序遍历的代码只不过调换了 result 元素纳入的顺序罢了,即交换了两行代码而已,就可得到中序遍历的代码

后序遍历

后序遍历:就是先遍历左孩子,其次是右孩子,最后是根节点

def postorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.extend(postorder_traversal(root.left))
        result.extend(postorder_traversal(root.right))
        result.append(root.data)
        return result

此时或许你已经可以举一反三了,也不用我过多的解释了,将根节点的插入放到最后即可得到后序遍历的代码

层次遍历

在这里你就要稍微注意一下了,层序遍历有别于先序中序后序遍历,层序遍历是按树的高度进行遍历的,即现遍历最上面的一层,随后是第二层,再就是第三层.......等等等等

def level_order_traversal(root):
    if root is None:
        return
    else:
        result = []
        queue = [root]
        while queue:
            current_level = []
            for i in range(len(queue)):
                node = queue.pop(0)
                current_level.append(node.data)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(current_level)
        return result

我们可以借助队列,队列的性质是先进先出(FIFO),首先将根节点加入到队列中,随后开始遍历,不过要注意的是,此时的队列是动态的:

node存在左节点或者右节点的时候队列queue将会把node的左右孩子存入其中(哪个孩子存在,就将哪个孩子存入其中),随后继续进行遍历

上述代码中最后返回为一个二维数组,当然如果你需要也可以将其改为一维数组,删除current_level即可

常见的二叉树操作

在LeetCode上刷题你就会发现,那些基础题的解决方法大差不差,其本质是以下三种方法的变式而已,只要熟练下列常规操作,你就可以秒杀绝大多数基础题

返回树的深度

聪明的你已经返现了,当你熟练掌握二叉树的层序遍历后,只要你能得到层序遍历的层数,你就能得到二叉树的深度

def root_depth(root):
    return len(level_order_traversal(root))

没错,就是这么简单 

返回树的节点个数

聪明的你又发现了,当你熟练掌握二叉树的  先序遍历/中序遍历/后序遍历  之后,你就会发现,其实只要你知道遍历后返回的数组或者列表内的元素个数即可

def node_nums(root):
    return len(inorder_traversal(root))

没错,就是这么的简单 

寻找某个节点的父节点

其实不会有问题问你让你在某二叉树中寻找一个已知的节点,她会变着法的靠你对二叉树遍历的熟练度,比如找某两个节点公共祖先等等等等,所以与其掌握如何知道一个已知节点的位置,不如掌握如何知道一个未知节点的值

聪明的你又发现了,这道题可能有点小难,不过你思考之后发现其本质和二叉树的遍历类似,只要让其在特等条件下返回某个值即可

def find_ancestor(root, num):
    if root is None:
        return None
    if root.data == num or (root.left and root.left.data == num) or (root.right and root.right.data == num):
        return root.data
    left = find_ancestor(root.left, num)
    right = find_ancestor(root.right, num)
    if left:
        return left
    return right

完整代码

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

def preorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.append(root.data)
        result.extend(preorder_traversal(root.left))
        result.extend(preorder_traversal(root.right))
        return result


def inorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.extend(inorder_traversal(root.left))
        result.append(root.data)
        result.extend(inorder_traversal(root.right))
        return result

def postorder_traversal(root):
    if root is None:
        return []
    else:
        result = []
        result.extend(postorder_traversal(root.left))
        result.extend(postorder_traversal(root.right))
        result.append(root.data)
        return result

def level_order_traversal(root):
    if root is None:
        return
    else:
        result = []
        queue = [root]
        while queue:
            current_level = []
            for i in range(len(queue)):
                node = queue.pop(0)
                current_level.append(node.data)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(current_level)
        return result


def root_depth(root):
    return len(level_order_traversal(root))

def node_nums(root):
    return len(inorder_traversal(root))


def find_ancestor(root, num):
    if root is None:
        return None
    if root.data == num or (root.left and root.left.data == num) or (root.right and root.right.data == num):
        return root.data
    left = find_ancestor(root.left, num)
    right = find_ancestor(root.right, num)
    if left:
        return left
    return right



tree = node(3)
tree.left = node(5)
tree.right = node(1)
tree.left.left = node(6)
tree.left.right = node(2)
tree.right.left = node(0)
tree.right.right = node(8)
tree.left.right.left = node(7)
tree.left.right.right = node(4)


print(preorder_traversal(tree))
print(inorder_traversal(tree))
print(postorder_traversal(tree))
print(level_order_traversal(tree))
print(root_depth(tree))
print(find_ancestor(tree, 4))
print(node_nums(tree))

希望本文章对你有所帮助,也请你点点关注支持一下博主,若有什么问题可在评论区评论,博主会第一时间赶到现场,下期博主会带来二叉搜索树与平衡二叉树等更高级二叉树的运用,当然也不要忘了最最重要的,那就是:

自己试试看吧,你会做得更好!

标签:node,最最,遍历,result,Python,right,二叉树,root,left
From: https://blog.csdn.net/Ahjol171/article/details/141751707

相关文章

  • 用Python解决预测问题_对数线性模型模板
    对数线性模型(Log-linearmodel)是统计学中用于分析计数数据或频率数据的一类模型,特别是在多维列联表(contingencytables)分析中非常常见。这种模型通过取对数将乘法关系转换为加法关系,从而简化了数据分析。在对数线性模型中,我们通常对观测频数的对数进行建模,模型的形式可以表示......
  • 【Python系列】signal信号处理
    ......
  • 【Python系列】 参数默认规则
    ......
  • 20240901_113250 python 知识点列表
    开发环境20240901_113224python环境依赖的备份与导入_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/1188873020240901_114639填空题环境的备份与导入_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/11888767......
  • 【Python】标准库的使用
    Python通过模块来体现“库”降低了程序猿的学习成本提高了程序的开发效率库就是是别人已经写好了的代码,可以让我们直接拿来用荀子曰:“君子性非异也,善假于物也”一个编程语言能不能流行起来,一方面取决于语法是否简单方便容易学习,一方面取决于生态是否完备所谓的......
  • 20240901_113224 python 环境依赖的备份与导入
    20240830_173845python当前环境依赖包导出到文件中_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/1187710920240830_183845python从依赖包记录文件中批量安装包_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/11877185......
  • Python 潮流周刊#67:uv 的重磅更新(摘要)
    本周刊由Python猫出品,精心筛选国内外的250+信息源,为你挑选最值得分享的文章、教程、开源项目、软件工具、播客和视频、热门话题等内容。愿景:帮助所有读者精进Python技术,并增长职业和副业的收入。分享了12篇文章,12个开源项目,全文2000字。以下是本期摘要:......
  • 对称二叉树-101
    题目描述给你一个二叉树的根节点root,检查它是否轴对称。解题思路这里我们相当于是比较根节点左右两颗子树,我们依次向左右子树的左右两个方向进行遍历,我们比较左子树的左孩子和右子树的右孩子,左子树的右孩子和右子树的左孩子,这里如果不好理解可以看下面这个图片,如果两个子节......
  • 基于python+flask框架的衣洗净管理系统的设计与实现(开题+程序+论文) 计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着现代生活节奏的加快,人们对便捷、高效的生活服务需求日益增长。在日常生活中,洗衣作为家庭日常活动之一,占据了人们不少的时间和精力。传......
  • 基于python+flask框架的健康管理系统(在线轻问诊)(开题+程序+论文) 计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景在健康意识日益增强的今天,人们对于便捷、高效的医疗服务需求日益增长。然而,传统医疗体系面临资源分配不均、就医流程繁琐等问题,使得部分患......