Python 算法基础篇：树和二叉树的实现与应用

小蓝枣

发布于 2023-07-25 17:39:47

8820

文章被收录于专栏：CSDN博客专家-小蓝枣的博客CSDN博客专家-小蓝枣的博客

Python 算法基础篇：树和二叉树的实现与应用

引言

树和二叉树是常用的非线性数据结构，它们在算法和程序设计中有着广泛的应用。本篇博客将重点介绍树和二叉树的原理、实现以及它们在不同场景下的应用。我们将使用 Python 来演示树和二叉树的实现，并通过实例展示每一行代码的运行过程。

😃😄 ❤️ ❤️ ❤️

1. 树的概念与特点

树是一种非线性数据结构，它由节点组成，并通过连接节点的边来表现层次结构。树中包含一个根节点，根节点可以有零个或多个子节点，每个子节点又可以有自己的子节点，形成了一个层次结构。树的节点之间不会存在环路，每个节点有一个父节点，除了根节点。

树的特点：

树中的节点具有层次结构，从根节点到任意节点都存在唯一的路径；
每个节点可以有零个或多个子节点；
每个节点有且只有一个父节点，除了根节点；
树中的节点不会形成环路。

2. 树的实现与应用

2.1 树的实现

下面是树的 Python 实现：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

class Tree:
    def __init__(self):
        self.root = None

    def add_node(self, parent_val, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            parent_node = self.search_node(self.root, parent_val)
            if parent_node:
                parent_node.children.append(TreeNode(val))
            else:
                print(f"Parent node with value {parent_val} not found.")

    def search_node(self, node, val):
        if not node:
            return None
        if node.val == val:
            return node
        for child in node.children:
            result = self.search_node(child, val)
            if result:
                return result
        return None

    def display(self, node=None, level=0):
        if not node:
            node = self.root
        print(" " * level, node.val)
        for child in node.children:
            self.display(child, level + 1)

代码解释：上述代码定义了一个树类 Tree ，以及一个树节点类 TreeNode 。类中的方法包括：添加节点 add_node ，根据给定的父节点值和新节点值，将新节点添加为父节点的子节点；搜索节点 search_node ，在树中搜索给定值的节点；打印树的内容 display ，以树的层次结构打印树的内容。

2.2 树的应用

树在算法和程序设计中有着广泛的应用，以下是一些常见的应用场景：

2.2.1 文件系统的表示

文件系统通常使用树的结构来表示目录和文件之间的层次关系。每个目录是一个树节点，可以包含子目录和文件作为其子节点。

例如，以下是一个简化的文件系统结构：

/
|-- home
|   |-- user
|       |-- documents
|       |-- pictures
|-- etc
|   |-- config

在这个例子中，根目录 / 是树的根节点， home 和 etc 是根目录的子目录， user 是 home 目录的子目录， documents 和 pictures 是 user 目录的子目录，以此类推。

2.2.2 有向无环图( DAG )的表示

有向无环图是一种特殊的图结构，其中图中的边有方向，并且不存在形成环路的路径。有向无环图常常用来表示任务调度、项目管理等问题。

例如，以下是一个简化的有向无环图的表示：

A -> B
A -> C
B -> D
C -> D
D -> E

在这个例子中，节点 A 到节点 B 和节点 C 都有一条有向边，节点 B 和节点 C 再分别到达节点 D ，最后节点 D 到达节点 E 。这样的结构在程序中可以使用树来表示。

3. 二叉树的概念与特点

二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的子树也是二叉树。

二叉树的特点：

每个节点最多有两个子节点，左子节点和右子节点；
左子树和右子树都是二叉树；
二叉树可以为空，称为空二叉树。

4. 二叉树的实现与应用

4.1 二叉树的实现

下面是二叉树的 Python 实现：

class BinaryTreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def add_node(self, val):
        if not self.root:
            self.root = BinaryTreeNode(val)
        else:
            self._add_node(self.root, val)

    def _add_node(self, node, val):
        if val < node.val:
            if node.left:
                self._add_node(node.left, val)
            else:
                node.left = BinaryTreeNode(val)
        else:
            if node.right:
                self._add_node(node.right, val)
            else:
                node.right = BinaryTreeNode(val)

    def search_node(self, val):
        return self._search_node(self.root, val)

    def _search_node(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search_node(node.left, val)
        else:
            return self._search_node(node.right, val)

    def display(self, node=None):
        if not node:
            node = self.root
        if node:
            self.display(node.left)
            print(node.val)
            self.display(node.right)

代码解释：上述代码定义了一个二叉树类 BinaryTree ，以及一个二叉树节点类 BinaryTreeNode 。类中的方法包括：添加节点 add_node ，根据给定的节点值将新节点添加到合适的位置；搜索节点 search_node ，在二叉树中搜索给定值的节点；打印二叉树的内容 display ，按照中序遍历的方式打印二叉树的内容。