数据结构必会|二叉树及其遍历(Python)

简介: Python实现二叉树及其遍历

二叉树

1. 树的概念

​ 在数据结构中,树可以看作是一种通过递归生成的数据结构,每棵树只有一个根结点(下图中的A)而其他的结点可以有很多个,树的结构如下图所示:

在这里插入图片描述

2. 树的术语

​ 在树结构中,有很多专业的术语,常见的术语及解释如下:

  • 根结点:A
  • 祖先结点:B和K
  • 子孙结点:K和B
  • 父结点:E和K
  • 子结点:K和E
  • 兄弟结点:K和L
  • 叶子结点:度等于0的节点,F、G等
  • 结点的度:树中一个结点的子结点个数,A有3个子结点
  • 树的度:结点最大度数

3. 二叉树的定义

​ 对于每个结点来说最多有两棵子树的树叫做二叉树,二叉树有左右之分,次序不能颠倒。

4. 常见的特殊二叉树

  • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
  • 完全二叉树:对于一棵二叉树,假设其深度为d(d>1)。除了第d层外,其他各层的结点数目均已达最大值,且第d层所有结点从左到右的紧密排列。

​ 满二叉树和完全二叉树的结构如下图所示(A为满二叉树,B为完全二叉树,满二叉树也是一种完全二叉树)

在这里插入图片描述

二叉树的遍历

1. 常见的二叉树遍历形式

​ 现有如下的一颗二叉树:

在这里插入图片描述

​ 常见的二叉树遍历形式可以分为下列四种:

  • 前序遍历:先访问根节点,然后前序遍历左子树,再前序遍历右子树。

    • 结果:ABDECFG
  • 中序遍历:中序遍历根节点的左子树,然后是访问根节点,最后遍历右子树。

    • 结果:DBEAFCG
  • 后序遍历:从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。

    • 结果:DEBFGCA
  • 层次遍历:从根节点从上往下逐层遍历,在同一层,按从左到右的顺序对节点逐个访问。

    • 结果:ABCDEFG

2. 二叉树的实现

​ 二叉树的构建及一些功能函数的实现方法如下:

# 二叉树类
class BTree(object):

    # 初始化
    def __init__(self, data=None, left=None, right=None):
        self.data = data  # 数据域
        self.left = left  # 左子树
        self.right = right  # 右子树

    # 前序遍历
    def preorder(self):
                # 根左右
        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()

    # 中序遍历
    def inorder(self):
        # 左根右
        if self.left is not None:
            self.left.inorder()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.inorder()

    # 后序遍历
    def postorder(self):
                # 左右根
        if self.left is not None:
            self.left.postorder()
        if self.right is not None:
            self.right.postorder()
        if self.data is not None:
            print(self.data, end=' ')

    # 层序遍历
    def levelorder(self):

        # 返回某个节点的左孩子
        def LChild_Of_Node(node):
            return node.left if node.left is not None else None

        # 返回某个节点的右孩子
        def RChild_Of_Node(node):
            return node.right if node.right is not None else None

        # 层序遍历列表
        level_order = []
        # 是否添加根节点中的数据
        if self.data is not None:
            level_order.append([self])
    # level_order[[0],[1,2]]
    # 二叉树的高度
        height = self.height()
        if height >= 1:
            # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
            for _ in range(2, height + 1):  # (0,5)  1,2,3,4,5
                level = []  # 该层的节点
                for node in level_order[-1]:
                    # 如果左孩子非空,则添加左孩子
                    if LChild_Of_Node(node):
                        level.append(LChild_Of_Node(node))
                    # 如果右孩子非空,则添加右孩子
                    if RChild_Of_Node(node):
                        level.append(RChild_Of_Node(node))
                # 如果该层非空,则添加该层
                if level:
                    level_order.append(level)

            # 取出每层中的数据
            for i in range(0, height):  # 层数
                for index in range(len(level_order[i])):
                    level_order[i][index] = level_order[i][index].data

        return level_order

    # 二叉树的高度


    def height(self):
        # 空的树高度为0, 只有root节点的树高度为1
        if self.data is None:
            return 0
        elif self.left is None and self.right is None:
            return 1
        elif self.left is None and self.right is not None:
            return 1 + self.right.height()
        elif self.left is not None and self.right is None:
            return 1 + self.left.height()
        else:
            return 1 + max(self.left.height(), self.right.height())

    # 二叉树的叶子节点
    def leaves(self):

        if self.data is None:
            return None
        elif self.left is None and self.right is None:
            print(self.data, end=' ')
        elif self.left is None and self.right is not None:
            self.right.leaves()
        elif self.right is None and self.left is not None:
            self.left.leaves()
        else:
            self.left.leaves()
            self.right.leaves()
AI 代码解读

​ 测试代码如下:

right_tree = BTree(6)
right_tree.left = BTree(2)
right_tree.right = BTree(4)

left_tree = BTree(5)
left_tree.left = BTree(1)
left_tree.right = BTree(3)

tree = BTree(11)
tree.left = left_tree
tree.right = right_tree

left_tree = BTree(7)
left_tree.left = BTree(3)
left_tree.right = BTree(4)

right_tree = tree  # 增加新的变量
tree = BTree(18)
tree.left = left_tree
tree.right = right_tree

print('先序遍历为:')
tree.preorder()
print()

print('中序遍历为:')
tree.inorder()
print()

print('后序遍历为:')
tree.postorder()
print()

print('层序遍历为:')
level_order = tree.levelorder()
print(level_order)
print()

height = tree.height()
print('树的高度为%s.' % height)
print()

print('叶子节点为:')
tree.leaves()

# 输出如下
'''
先序遍历为:
18 7 3 4 11 5 1 3 6 2 4 
中序遍历为:
3 7 4 18 1 5 3 11 2 6 4 
后序遍历为:
3 4 7 1 3 5 2 4 6 11 18 
层序遍历为:
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]
树的高度为4.
叶子节点为:
3 4 1 3 2 4 
'''
AI 代码解读
目录
打赏
0
0
0
0
16
分享
相关文章
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
134 66
Python 中常见的数据结构
这些数据结构各有特点和适用场景,在不同的编程任务中发挥着重要作用。开发者需要根据具体需求选择合适的数据结构,以提高程序的效率和性能
153 59
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
174 59
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
Python 中的数据结构与其他编程语言数据结构的区别
不同编程语言都有其设计理念和应用场景,开发者需要根据具体需求和语言特点来选择合适的数据结构
121 55
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
76 20
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
53 2
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
66 5
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
114 33

热门文章

最新文章