树结构简介

树（Tree）是计算机科学中一种非常重要的非线性数据结构，它模拟了自然界中的树结构，由节点（nodes）和边（edges）组成。树结构具有层次化的特性，使得它在许多领域都有广泛的应用。

树结构的应用场景：

• 文件系统：目录和文件的层级结构
• 数据库索引：B树、B+树用于高效数据检索
• 组织结构图：公司或部门的层级关系
• AI决策：决策树用于机器学习分类
• XML/HTML解析：DOM树表示文档结构

树结构核心术语

在Python中实现树结构

在Python中，我们可以使用类来定义树节点。每个节点包含数据和指向其子节点的引用。

基本树节点实现

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    
    def add_child(self, child_node):
        self.children.append(child_node)
    
    def remove_child(self, child_node):
        self.children = [child for child in self.children if child != child_node]

创建树结构

# 创建根节点
root = TreeNode("CEO")

# 添加子节点
cto = TreeNode("CTO")
cfo = TreeNode("CFO")
root.add_child(cto)
root.add_child(cfo)

# 为CTO添加子节点
engineer1 = TreeNode("Engineer 1")
engineer2 = TreeNode("Engineer 2")
cto.add_child(engineer1)
cto.add_child(engineer2)

# 为CFO添加子节点
accountant = TreeNode("Accountant")
cfo.add_child(accountant)

树的遍历方法

遍历树结构意味着访问树中的每个节点。主要有两种遍历策略：深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历（DFS）

深度优先遍历沿着树的深度遍历节点，尽可能深的搜索树的分支。

def dfs(node):
    if node is None:
        return
    print(node.data)  # 访问当前节点
    for child in node.children:
        dfs(child)    # 递归访问每个子节点

广度优先遍历（BFS）

广度优先遍历逐层访问节点，先访问根节点，然后是所有子节点，然后是孙子节点，依此类推。

from collections import deque

def bfs(root):
    if root is None:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.data)  # 访问当前节点
        
        # 将当前节点的所有子节点加入队列
        for child in node.children:
            queue.append(child)

二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，其中每个节点的值大于其左子树的所有节点值，小于其右子树的所有节点值。

BST Python实现

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root is None:
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value):
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def inorder_traversal(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# 创建二叉搜索树
bst = BinarySearchTree()
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for value in values:
    bst.insert(value)

# 中序遍历（返回排序结果）
print("中序遍历:", bst.inorder_traversal())  # 输出: [1, 3, 4, 6, 7, 8, 10, 13, 14]

# 搜索节点
print("搜索 6:", bst.search(6))  # 输出: True
print("搜索 12:", bst.search(12)) # 输出: False