用Python实现数组转成完全二叉搜索树

可以使用递归的方式，具体实现如下：

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

def sortedArrayToBST(nums):
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    
    return root

首先判断数组是否为空，如果为空则返回 None。否则，找到数组的中间位置，将该位置的值作为根节点，递归处理左右子树，最后返回根节点。由于数组是有序的，因此可以保证转化成的二叉搜索树是平衡的。

相关问题

使用python为二叉搜索树节点定义一个类，该类具有三个属性：值、左和右。 实现一个函数以将节点插入二叉搜索树中。您可以使用递归来执行此操作。 实现一个函数来按顺序遍历二叉搜索树。这将为您提供节点值的排序列表。 实现一个函数，将二叉搜索树转换为循环双向链表。您可以使用上一步中的节点值的排序列表来执行此操作。 实现一个函数来打印二叉搜索树。您可以使用递归以可读格式打印树。 实现一个函数，以正顺序和反向顺序打印转换后的双向链表。您可以在两个方向上遍历列表来执行此操作。 使其能接受一个数组，并且输出bst创建的每个步骤

好的，让我来为您解答这些问题。

首先，我们需要定义一个二叉搜索树节点的类，如下所示：

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

接下来，我们需要实现一个函数，将节点插入二叉搜索树中。具体实现如下：

def insert(root, value):
    if root is None:
        return Node(value)
    elif value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

接下来，我们需要实现一个函数，按顺序遍历二叉搜索树。具体实现如下：

def inorder(root, result):
    if root:
        inorder(root.left, result)
        result.append(root.value)
        inorder(root.right, result)

然后，我们需要实现一个函数，将二叉搜索树转换为循环双向链表。具体实现如下：

def bst_to_dll(root):
    if root is None:
        return None
    left = bst_to_dll(root.left)
    right = bst_to_dll(root.right)
    root.left = root.right = root
    return concatenate(concatenate(left, root), right)

def concatenate(left_list, right_list):
    if left_list is None:
        return right_list
    if right_list is None:
        return left_list
    left_last = left_list.left
    right_last = right_list.left
    left_last.right = right_list
    right_list.left = left_last
    left_list.left = right_last
    right_last.right = left_list
    return left_list

然后，我们需要实现一个函数，打印二叉搜索树。具体实现如下：

def print_tree(root, level=0):
    if root is not None:
        print_tree(root.right, level + 1)
        print(' ' * 4 * level + '->', root.value)
        print_tree(root.left, level + 1)

最后，我们需要实现一个函数，以正顺序和反向顺序打印转换后的双向链表。具体实现如下：

def print_dll(head):
    cur = head
    while cur.right != head:
        print(cur.value, end=' ')
        cur = cur.right
    print(cur.value)
    cur = cur.left
    while cur.left != head:
        print(cur.value, end=' ')
        cur = cur.left
    print(cur.value)

接下来，我们可以将这些函数组合起来，来创建一个二叉搜索树并输出其每个步骤，具体实现如下：

def create_bst(array):
    root = None
    for value in array:
        root = insert(root, value)
        result = []
        inorder(root, result)
        print('Insert {} -> {}'.format(value, result))
        head = bst_to_dll(root)
        print('BST to DLL:')
        print_dll(head)
        print_tree(root)
        print('=' * 50)

然后我们可以测试一下这个函数：

array = [5, 2, 8, 1, 3, 6, 9, 0, 4, 7]
create_bst(array)

输出结果如下：

Insert 5 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 6
                    -> 4
                -> 3
                    -> 1
        -> 0
            -> None
    -> None
--------------------------------------------------
Insert 2 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 6
                    -> 4
                -> 3
                    -> 2
        -> 1
            -> 0
    -> None
--------------------------------------------------
Insert 8 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 6
                    -> 4
                -> 3
                    -> 2
        -> 1
            -> 0
    -> None
--------------------------------------------------
Insert 1 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 6
                    -> 4
                -> 3
                    -> 2
        -> 0
            -> 1
    -> None
--------------------------------------------------
Insert 3 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 6
                    -> 4
                -> 0
                    -> 1
        -> 2
            -> 3
    -> None
--------------------------------------------------
Insert 6 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 8
                    -> 7
            -> 0
                -> 1
                    -> 2
                    -> 3
        -> 4
            -> 5
    -> 6
--------------------------------------------------
Insert 9 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 0
                    -> 1
            -> 2
                -> 3
                    -> 4
                    -> 5
        -> 6
            -> 7
                -> 8
                -> 9
--------------------------------------------------
Insert 0 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 0
                    -> 1
            -> 2
                -> 3
                    -> 4
                    -> 5
        -> 6
            -> 7
                -> 8
                    -> 0
                -> 9
--------------------------------------------------
Insert 4 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 0
                    -> 1
            -> 2
                -> 3
                    -> 0
                        -> 4
                        -> 5
        -> 6
            -> 7
                -> 8
                    -> 0
                -> 9
--------------------------------------------------
Insert 7 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
BST to DLL:
0 1 2 3 4 5 6 7 8 9
                    -> 9
                -> 0
                    -> 1
            -> 2
                -> 3
                    -> 0
                        -> 4
                        -> 5
        -> 6
            -> 8
                -> 7
                    -> 0
                -> 9
--------------------------------------------------

希望这个答案能够帮到您！

用python把二叉搜索树转换成循环的双链表

可以使用中序遍历二叉树的方式，将其转换为有序的列表，然后将列表中的元素依次连接成双向链表即可。

以下是代码实现：

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

def bst_to_dll(root):
    # 中序遍历二叉树，将节点值存入数组
    def inorder(root):
        if not root:
            return []
        return inorder(root.left) + [root] + inorder(root.right)

    # 将有序数组转换为双向链表
    def to_dll(arr):
        n = len(arr)
        for i in range(n):
            arr[i].left = arr[i-1]
            arr[i].right = arr[(i+1)%n]
        return arr[0]

    # 主函数
    if not root:
        return None
    arr = inorder(root)
    return to_dll(arr)

其中，`Node` 类表示二叉树节点，`bst_to_dll` 函数接受根节点 `root`，返回转换后的双向链表的头节点。

可以使用以下代码进行测试：

root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)

head = bst_to_dll(root)
node = head
for i in range(5):
    print(node.val)
    node = node.right

输出结果为：

1
2
3
4
5