### 关于树的数据结构代码实现 以下是基于二叉树这一经典树形数据结构的代码实现，涵盖了基本操作如创建节点、构建二叉树以及遍历方法。 #### 节点定义 在任何树型数据结构中，节点是最基础的部分。对于一棵二叉树来说，每个节点最多有两个子节点——左孩子和右孩子[^1]。 ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value # 当前节点存储的值 self.left = left # 左子节点指针 self.right = right # 右子节点指针 ``` #### 构建二叉树 通过递归的方式可以方便地构建一颗完整的二叉树。这里提供了一个简单的例子来展示如何手动建立一棵小型的二叉树。 ```python def build_tree(): node7 = TreeNode(7) node6 = TreeNode(6) node5 = TreeNode(5) node4 = TreeNode(4) node3 = TreeNode(3, node6, node7) node2 = TreeNode(2, node4, node5) root = TreeNode(1, node2, node3) return root ``` #### 遍历方式 常见的三种遍历方式分别为先序遍历（Pre-order）、中序遍历（In-order）和后序遍历（Post-order），下面分别给出其实现。 ##### 先序遍历 (根 -> 左 -> 右) ```python def preorder_traversal(root): result = [] if not root: return result stack = [root] while stack: node = stack.pop() result.append(node.value) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result ``` ##### 中序遍历 (左 -> 根 -> 右) ```python def inorder_traversal(root): result = [] stack = [] current = root while True: if current is not None: stack.append(current) current = current.left elif(stack): current = stack.pop() result.append(current.value) current = current.right else: break return result ``` ##### 后序遍历 (左 -> 右 -> 根) ```python def postorder_traversal(root): result = [] if not root: return result stack = [(root, False)] while stack: node, visited = stack.pop() if node: if visited: result.append(node.value) else: stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return result ``` 以上展示了关于二叉树的一些基本概念及其具体实现方法。如果需要更复杂的树结构或者特定功能比如哈夫曼树，则可以根据需求进一步扩展上述模型[^2]。