binary search tree python

二叉搜索树（Binary Search Tree）是一种数据结构，它是由节点组成的树形结构，每个节点最多有两个子节点，左子节点的值小于父节点的值，右子节点的值大于父节点的值。在Python中，可以使用类来实现二叉搜索树。

相关问题

1. Convert a binary search tree into a sorted circular doubly linked list 【Problem Description】 Given a binary search tree, you need to convert it into a circular doubly linked list, the elements in the linked list are sorted. For example, a binary search tree in Fig.1 is converted into a sorted circular doubly linked list in Fig.2. 【Basic Requirements】 The input data is a set of data elements to build a binary search tree, you should design algorithms to realize the conversion process and verify the accuracy of your code on multiple test data. The output includes the following: (1) Print the binary search tree (2) Traverse the binary search tree (3) Print the converted doubly linked list (4) Output all elements of the doubly linked list in positive and reverse order

【Solution】
To convert a binary search tree into a sorted circular doubly linked list, we can use the following steps:
1. Inorder traversal of the binary search tree to get the elements in sorted order.
2. Create a doubly linked list and add the elements from the inorder traversal to it.
3. Make the list circular by connecting the head and tail nodes.
4. Return the head node of the circular doubly linked list.

Here's the Python code for the solution:

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None
    
def tree_to_doubly_list(root):
    if not root:
        return None
    
    stack = []
    cur = root
    head = None
    prev = None
    
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        
        cur = stack.pop()
        
        if not head:
            head = cur
        
        if prev:
            prev.right = cur
            cur.left = prev
        prev = cur
        
        cur = cur.right
    
    head.left = prev
    prev.right = head
    
    return head

To verify the accuracy of the code, we can use the following test cases:

# Test case 1
# Input: [4,2,5,1,3]
# Output: 
# Binary search tree: 
#       4
#     /   \
#    2     5
#   / \
#  1   3
# Doubly linked list: 1 <-> 2 <-> 3 <-> 4 <-> 5
# Doubly linked list in reverse order: 5 <-> 4 <-> 3 <-> 2 <-> 1

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

head = tree_to_doubly_list(root)

print("Binary search tree:")
print_tree(root)
print("Doubly linked list:")
print_list(head)
print("Doubly linked list in reverse order:")
print_list_reverse(head)

# Test case 2
# Input: [2,1,3]
# Output: 
# Binary search tree: 
#     2
#   /   \
#  1     3
# Doubly linked list: 1 <-> 2 <-> 3
# Doubly linked list in reverse order: 3 <-> 2 <-> 1

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

head = tree_to_doubly_list(root)

print("Binary search tree:")
print_tree(root)
print("Doubly linked list:")
print_list(head)
print("Doubly linked list in reverse order:")
print_list_reverse(head)

The output of the test cases should match the expected output as commented in the code.

A complete binary search tree is a complete binary tree that satisfies the left-right ordering property of binary search tree as well as the structure of a complete binary tree. Since a complete binary tree can be perfectly stored in an array, we can also store the complete BST in an array. In this lab, you will be given an array of integers as input. The objective is to write a function to_bst(lst) to convert the array to a complete binary tree that stores in an array with the same length. For example, given an array [29, 72, 1, 34, 22], the corresponding complete BST is [34, 22, 72, 1, 29]. Hint: Consider the inorder traversal of the BST.

To convert the input array to a complete binary tree that stores in an array with the same length, we can follow these steps:

1. Sort the input array in ascending order.
2. Create an empty output array with the same length as the input array.
3. Perform an inorder traversal of the complete binary search tree and fill in the output array with the visited nodes in the order of the traversal.

Here is the Python code to implement this algorithm:

def to_bst(lst):
    # Sort the input array in ascending order
    lst.sort()

    # Create an empty output array with the same length as the input array
    output = [None] * len(lst)

    # Perform an inorder traversal of the complete binary search tree
    def inorder(node_index, start_index, end_index):
        if start_index <= end_index:
            # Calculate the index of the middle node
            mid_index = (start_index + end_index) // 2

            # Fill in the current node with the middle element
            output[node_index] = lst[mid_index]

            # Recursively fill in the left and right subtrees
            inorder(2 * node_index + 1, start_index, mid_index - 1)
            inorder(2 * node_index + 2, mid_index + 1, end_index)

    # Start the inorder traversal from the root node
    inorder(0, 0, len(lst) - 1)

    return output

This function uses recursion to perform an inorder traversal of the complete binary search tree and fill in the output array with the visited nodes in the order of the traversal. The time complexity of this algorithm is O(n log n) because of the sorting step.