【树结构从入门到应用】树的基本知识,树的遍历算法,树结构的应用-电话薄管理与文件系统操作,示例+代码

  行业动态     |      2024-01-15 01:03

目录

1 树的定义

2 树的基本术语

3 树的示例

4 常见的树类型

 5 树的遍历算法与代码示例 

5.1  前序遍历(Preorder Traversal)

5.2  中序遍历(Inorder Traversal)

5.3 后序遍历(Postorder Traversal)

 5.4 代码示例       

6 树结构应用示例

6.1 二叉搜索树(Binary Search Tree)管理电话簿

6.2 文件系统应用

(1)Python 文件系统应用示例

(2)遍历文件系统并列出文件   


         树(Tree)是一种重要的数据结构,用于组织数据以形成分层结构,其中每个元素都与一个或多个元素相关联。

1 树的定义

        树是一种抽象数据结构,由节点(或顶点)和边组成。树的每个节点可以有零个或多个子节点,但没有循环路径,意味着树是一个无环图。树有一个特殊的顶点称为根节点,它是整个树的起始点。

2 树的基本术语

  1. 根节点(Root):树的顶部节点,没有父节点,是整个树的起点。
  2. 叶节点(Leaf):没有子节点的节点,通常位于树的末端。
  3. 内部节点:至少有一个子节点的节点。
  4. 父节点和子节点:父节点连接到一个或多个子节点,子节点连接到其父节点。
  5. 兄弟节点:共享相同父节点的节点。
  6. 深度(Depth):从根节点到一个节点的路径长度。
  7. 高度(Height):树的最大深度,即从根节点到叶节点的最长路径的长度。

3 树的示例

以下是一个简单的树的示例,以帮助理解上述概念:

         A
       / | \
      B  C  D
     / \
    E   F
  • A是根节点,它没有父节点,有三个子节点:B、C和D。
  • B、C和D是内部节点,它们有子节点。
  • E和F是叶节点,它们没有子节点。
  • B和C是兄弟节点,它们共享相同的父节点A。
  • 节点B到根节点A的深度为1,节点E到根节点A的深度为2。
  • 树的高度为2,因为从根节点A到叶节点E或F的最长路径的长度为2。

4 常见的树类型

  1. 二叉树(Binary Tree):每个节点最多有两个子节点,左子节点和右子节点。二叉树是最常见的树结构。

          A
         / \
        B   C
       / \   \
      D   E   F
    
  2. 二叉搜索树(Binary Search Tree,BST):一种特殊的二叉树,具有以下性质:

    • 左子树的节点值都小于根节点。
    • 右子树的节点值都大于根节点。

    这使得BST非常适合进行快速搜索和排序操作。

          8
         / \
        3   10
       / \    \
      1   6    14
         / \   /
        4   7  13
    
  3. 平衡二叉树(Balanced Binary Tree):一种特殊的二叉搜索树,确保左子树和右子树的高度差尽可能小,以维护性能。

          8
         / \
        3   10
       / \   / \
      1   6 9   14
    
  4. 多叉树:每个节点可以有多个子节点。

        A
       /|\
      B C D
         |\
         E F
  5. 树的森林(Forest):多个树的集合。

       Tree 1        Tree 2
         A            J
        / \          / \
       B   C        K   L
          /|\
         D E F
    

 5 树的遍历算法与代码示例 

        树的遍历算法是一种用于访问树结构中所有节点的方法。树的遍历算法可以分为以下三种主要类型:前序遍历、中序遍历和后序遍历。这些算法适用于二叉树以及其他树结构,用于遍历树中的节点并执行特定操作。以下是这三种遍历算法的详细解释和示例:

树示例如下:

    1
   / \
  2   3
 / \
4   5

5.1  前序遍历(Preorder Traversal)

        前序遍历从根节点开始,首先访问根节点,然后按照左子树、右子树的顺序递归遍历子树。前序遍历的顺序是根节点->左子树->右子树。

        前序遍历结果:[1, 2, 4, 5, 3]。

5.2  中序遍历(Inorder Traversal)

        中序遍历从根节点开始,首先递归遍历左子树,然后访问根节点,最后递归遍历右子树。中序遍历的顺序是左子树->根节点->右子树。

        中序遍历结果:[4, 2, 5, 1, 3]

5.3 后序遍历(Postorder Traversal)

        后序遍历从根节点开始,首先递归遍历左子树,然后递归遍历右子树,最后访问根节点。后序遍历的顺序是左子树->右子树->根节点。

        后序遍历结果:[4, 5, 2, 3, 1]


 5.4 代码示例       

        这些遍历算法可以通过递归或迭代的方式来实现。下面是前序遍历、中序遍历和后序遍历的递归实现示例(使用Python):

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

# 前序遍历(Preorder Traversal)的递归实现
def preorderTraversal(root):
    if root is None:
        return []  # 如果树为空,返回空列表
    
    result = []
    result.append(root.val)  # 访问根节点
    result += preorderTraversal(root.left)  # 递归遍历左子树
    result += preorderTraversal(root.right)  # 递归遍历右子树
    
    return result

# 中序遍历(Inorder Traversal)的递归实现
def inorderTraversal(root):
    if root is None:
        return []  # 如果树为空,返回空列表
    
    result = []
    result += inorderTraversal(root.left)  # 递归遍历左子树
    result.append(root.val)  # 访问根节点
    result += inorderTraversal(root.right)  # 递归遍历右子树
    
    return result

# 后序遍历(Postorder Traversal)的递归实现
def postorderTraversal(root):
    if root is None:
        return []  # 如果树为空,返回空列表
    
    result = []
    result += postorderTraversal(root.left)  # 递归遍历左子树
    result += postorderTraversal(root.right)  # 递归遍历右子树
    result.append(root.val)  # 访问根节点
    
    return result

# 示例用法
if __name__ == "__main__":
    # 创建一个示例二叉树
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    # 前序遍历示例
    print("前序遍历结果:", preorderTraversal(root))  # [1, 2, 4, 5, 3]
    
    # 中序遍历示例
    print("中序遍历结果:", inorderTraversal(root))  # [4, 2, 5, 1, 3]
    
    # 后序遍历示例
    print("后序遍历结果:", postorderTraversal(root))  # [4, 5, 2, 3, 1]

6 树结构应用示例

        树结构在计算机科学中有许多应用,包括文件系统、数据库管理系统、编译器、网络路由算法等。这里,我将为你提供一个关于二叉搜索树(Binary Search Tree,BST)应用的示例,包括示例代码。BST是一种常见的树结构,用于实现快速搜索、插入和删除操作。

6.1 二叉搜索树(Binary Search Tree)管理电话簿

示例背景:考虑一个应用场景,你需要管理一本电话簿,用于存储联系人的姓名和电话号码。你希望能够快速查找联系人的电话号码、添加新联系人、删除联系人等操作。这个场景适合使用二叉搜索树来实现。

示例代码:以下是一个简单的Python示例代码,用于实现二叉搜索树来管理电话簿。

# 定义树节点类
class TreeNode:
    def __init__(self, name, phone_number):
        self.name = name
        self.phone_number = phone_number
        self.left = None
        self.right = None

# 定义电话簿类
class PhoneBook:
    def __init__(self):
        self.root = None

    # 插入联系人信息
    def insert(self, name, phone_number):
        self.root = self._insert(self.root, name, phone_number)

    # 递归插入方法
    def _insert(self, node, name, phone_number):
        if node is None:
            return TreeNode(name, phone_number)
        if name < node.name:
            node.left = self._insert(node.left, name, phone_number)
        elif name > node.name:
            node.right = self._insert(node.right, name, phone_number)
        return node

    # 查找联系人的电话号码
    def search(self, name):
        return self._search(self.root, name)

    # 递归查找方法
    def _search(self, node, name):
        if node is None:
            return None
        if name == node.name:
            return node.phone_number
        elif name < node.name:
            return self._search(node.left, name)
        else:
            return self._search(node.right, name)

    # 删除联系人
    def delete(self, name):
        self.root = self._delete(self.root, name)

    # 递归删除方法
    def _delete(self, node, name):
        if node is None:
            return node
        if name < node.name:
            node.left = self._delete(node.left, name)
        elif name > node.name:
            node.right = self._delete(node.right, name)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            # 找到右子树中的最小节点
            node.name, node.phone_number = self._min_value(node.right)
            # 删除右子树中的最小节点
            node.right = self._delete(node.right, node.name)
        return node

    # 查找右子树中的最小节点
    def _min_value(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current.name, current.phone_number

# 示例用法
if __name__ == "__main__":
    phonebook = PhoneBook()
    phonebook.insert("Alice", "123-456-7890")
    phonebook.insert("Bob", "987-654-3210")
    phonebook.insert("Charlie", "555-555-5555")

    # 查找联系人的电话号码
    print("Alice's phone number:", phonebook.search("Alice"))
    print("Charlie's phone number:", phonebook.search("Charlie"))

    # 删除联系人
    phonebook.delete("Bob")

    # 查找已删除联系人
    print("Bob's phone number after deletion:", phonebook.search("Bob"))

运行:

Alice's phone number: 123-456-7890
Charlie's phone number: 555-555-5555
Bob's phone number after deletion: None

在这个示例中,我们定义了一个PhoneBook类,它使用二叉搜索树来存储联系人信息。你可以执行以下操作:

  • insert(name, phone_number):插入新联系人。
  • search(name):查找联系人的电话号码。
  • delete(name):删除联系人。

这个示例展示了如何使用二叉搜索树来实现一个简单的电话簿应用。你可以根据具体需求进行扩展和改进。树结构的灵活性使其适用于各种应用,可以更高效地执行搜索、插入和删除操作。

6.2 文件系统应用

        文件系统通常以树形结构表示目录和文件之间的层次关系。文件系统的树结构示例可以用于操作系统中。考虑一个简单的文件系统,根目录包含多个子目录和文件,每个子目录可以包含更多子目录和文件。用户可以执行以下操作:

  1. 列出指定目录下的所有文件和子目录。
  2. 创建新的子目录。
  3. 创建新的文件。
  4. 删除文件或目录。
  5. 导航到不同的目录。
(1)Python 文件系统应用示例
class File:
    def __init__(self, name):
        self.name = name

class Directory:
    def __init__(self, name):
        self.name = name
        self.contents = []

class FileSystem:
    def __init__(self):
        self.root = Directory("root")

    def list_directory(self, directory):
        for item in directory.contents:
            if isinstance(item, File):
                print("File:", item.name)
            elif isinstance(item, Directory):
                print("Directory:", item.name)

    def create_directory(self, parent_directory, name):
        new_directory = Directory(name)
        parent_directory.contents.append(new_directory)

    def create_file(self, parent_directory, name):
        new_file = File(name)
        parent_directory.contents.append(new_file)

    def delete_item(self, parent_directory, name):
        for item in parent_directory.contents:
            if isinstance(item, File) and item.name == name:
                parent_directory.contents.remove(item)
            elif isinstance(item, Directory) and item.name == name:
                parent_directory.contents.remove(item)

    def navigate_directory(self, current_directory, target_directory_name):
        for item in current_directory.contents:
            if isinstance(item, Directory) and item.name == target_directory_name:
                return item
        return None

# 创建文件系统实例
fs = FileSystem()

# 在根目录创建一个子目录
fs.create_directory(fs.root, "documents")

# 在子目录中创建文件
documents_dir = fs.navigate_directory(fs.root, "documents")
fs.create_file(documents_dir, "report.txt")

# 列出根目录下的内容
print("Contents of root directory:")
fs.list_directory(fs.root)

# 列出"documents"子目录下的内容
print("\nContents of 'documents' directory:")
fs.list_directory(documents_dir)

# 删除文件
fs.delete_item(documents_dir, "report.txt")

# 再次列出"documents"子目录下的内容
print("\nContents of 'documents' directory after file deletion:")
fs.list_directory(documents_dir)

上述Python代码示例演示了一个简单的文件系统应用,其中使用树结构表示目录和文件之间的层次关系。以下是代码示例的总结:

  1. 文件和目录类:代码中定义了两个类,FileDirectory,用于表示文件和目录。这些类分别包含了名称属性,用于标识文件或目录。

  2. 文件系统类FileSystem类是文件系统的核心部分,包括以下主要方法:

    • list_directory(directory): 列出指定目录下的所有文件和子目录。
    • create_directory(parent_directory, name): 在指定目录下创建一个新的子目录。
    • create_file(parent_directory, name): 在指定目录下创建一个新的文件。
    • delete_item(parent_directory, name): 删除指定目录下的文件或子目录。
    • navigate_directory(current_directory, target_directory_name): 导航到不同的目录。
  3. 操作示例:代码示例演示了如何创建根目录,创建子目录,创建文件,列出目录内容,删除文件,以及导航到不同的目录。

  4. 文件系统使用:你可以创建文件系统实例(fs),然后使用它来模拟文件和目录的创建、删除和导航操作。这个示例为根目录创建了一个名为"documents"的子目录,然后在该子目录中创建了一个名为"report.txt"的文件。后来,代码演示了如何列出目录内容、删除文件,并再次列出目录内容。

(2)遍历文件系统并列出文件   

        文件系统通常使用树结构表示目录和文件之间的层次关系。以下是一个Python示例,用于遍历文件系统并列出文件:

import os

def list_files(path):
    for root, dirs, files in os.walk(path):
        for file in files:
            print(os.path.join(root, file))

# 列出当前目录下的所有文件和子目录
list_files('.')