python使用递归的方式建立二叉树

下面我将详细讲解如何使用递归的方式建立二叉树。

1. 建立二叉树的基本概念

在二叉树中，每个节点最多有2个子节点，分别称为左子节点和右子节点，因此我们可以通过递归的方式不断的构建左、右子树，来得到一个完整的二叉树。

2. 二叉树的节点定义

为了建立一个二叉树，我们首先需要定义二叉树中的节点。我们可以定义一个类来表示每个节点，其中包含三个属性：value 表示该节点的值，left 和 right 分别表示该节点的左子节点和右子节点。

下面是该节点类的基本代码：

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

3. 构建二叉树的递归函数

我们可以定义一个递归函数 build_tree() 来构建二叉树。该函数接受一个列表 data 和两个索引 left 和 right，其中 data 表示需要插入到二叉树中的数据，left 和 right 分别表示 data 的左右边界（即需要在 data[left:right] 中插入元素）。

该函数的基本思路为：

• 如果左右边界相等，则说明已经不能再往下插入节点，直接返回 None。
• 否则，我们应该找到 data[left:right] 中的最大值和最大值的索引 max_index，以及同样方式找到最小值和最小值的索引 min_index。
• 将最大值插入到当前节点中，并以 max_index 为边界，递归的调用 build_tree() 函数，以构建当前节点的右子树。
• 同样的，将最小值插入到当前节点中，并以 min_index 为边界，递归的调用 build_tree() 函数，以构建当前节点的左子树。
• 最终返回当前节点。

下面是 build_tree() 函数完整代码：

def build_tree(data, left, right):
    if left == right:
        return None

    max_val = max(data[left:right])
    max_index = data.index(max_val, left, right)

    min_val = min(data[left:right])
    min_index = data.index(min_val, left, right)

    node = TreeNode(max_val)
    node.right = build_tree(data, max_index+1, right)
    node.left = build_tree(data, left, min_index)

    return node

4. 构建二叉树的示例

下面是一个简单的示例，以构建二叉树 [5,90,15,20,35,25] 为例：

data = [5, 90, 15, 20, 35, 25]
root = build_tree(data, 0, len(data))

该代码会自动构建一个二叉树，其中根节点为 90，左子树的根节点为 5，右子树的根节点为 35。

我们可以通过遍历二叉树来查看结果：

def inorder_traversal(node):
    if not node:
        return
    inorder_traversal(node.left)
    print(node.value, end=' ')
    inorder_traversal(node.right)

inorder_traversal(root)

运行结果：

5 15 20 25 35 90 

可以看到，运行结果与预期的结果一致。

5. 另一个构建二叉树的示例

下面是另一个稍微复杂一点的示例，以构建二叉树 [1,2,3,4,5,6,7,8,9,10] 为例：

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
root = build_tree(data, 0, len(data))

该代码会自动构建一个二叉树，其中根节点为 10，左子树的根节点为 5，右子树的根节点为 9。

我们同样可以使用遍历二叉树来查看结果：

inorder_traversal(root)

运行结果：

1 2 3 4 5 6 7 8 9 10 

可以看到，运行结果与预期的结果一致。

这便是使用递归的方式建立二叉树的完整攻略，希望对你有所帮助。