本文共 2195 字，大约阅读时间需要 7 分钟。

树是一个由边连接的节点组成的非线性数据结构，具有明确的根节点和父节点关系。每个节点可以具有零个或多个子节点。树的插入过程遵循特定规则，即将新值与当前节点的值进行比较，决定其位置，并按照递归方式处理子树。

创建树

创建根节点并初始化树结构：

class Node:    def __init__(self, data):        self.left = None        self.right = None        self.data = dataroot = Node(10)

插入节点

插入功能基于节点的比较，决定左或右添加：

class Node:    def __init__(self, data):        self.left = None        self.right = None        self.data = data    def insert(self, data):        if self.data:            if data < self.data:                if not self.left:                    self.left = Node(data)                else:                    self.left.insert(data)            elif data > self.data:                if not self.right:                    self.right = Node(data)                else:                    self.right.insert(data)        else:            self.data = data

遍历树

通过不同的顺序访问节点数据。

顺序遍历 (Preorder)

从根访问左，然后右。

class Node:    def __init__(self, data):        self.left = None        self.right = None        self.data = data    def preorderTraversal(self, root):        res = []        if root:            res.append(root.data)            res += self.preorderTraversal(root.left)            res += self.preorderTraversal(root.right)        return res

中序遍历 (Inorder)

访问左，根，右。

class Node:    def __init__(self, data):        self.left = None        self.right = None        self.data = data    def inorderTraversal(self, root):        res = []        if root:            res = self.inorderTraversal(root.left)            res.append(root.data)            res += self.inorderTraversal(root.right)        return res

后序遍历 (Postorder)

访问左，右，根。

class Node:    def __init__(self, data):        self.left = None        self.right = None        self.data = data    def postorderTraversal(self, root):        res = []        if root:            res = self.postorderTraversal(root.left)            res += self.postorderTraversal(root.right)            res.append(root.data)        return res

示例应用

创建并插入节点：

root = Node(27)root.insert(14)  # 左root.insert(35)  # 右root.insert(10)  # 左，再次插入root.insert(19)  # 左的左root.insert(31)  # 右的右root.insert(42)  # 右的右

不同遍历结果：

• 顺序遍历：[27, 14, 10, 19, 35, 31, 42]
• 中序遍历：[10,14,19,27,31,35,42]
• 后序遍历：[10,19,14,31,42,35,27]