用Python构建二叉搜索树并遍历,再将二叉搜索树（BST）转换为有序循环双向链表

首先，让我们来构建一个二叉搜索树，并遍历它。以下是一个简单的 Python 代码示例：

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

def insertNode(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insertNode(node.left, val)
    else:
        node.right = insertNode(node.right, val)
    return node

def inorderTraversal(node):
    if node is not None:
        inorderTraversal(node.left)
        print(node.val)
        inorderTraversal(node.right)

# 测试样例
root = None
root = insertNode(root, 5)
root = insertNode(root, 3)
root = insertNode(root, 7)
root = insertNode(root, 2)
root = insertNode(root, 4)
root = insertNode(root, 6)
root = insertNode(root, 8)

inorderTraversal(root)

这个代码使用递归的方式构建了一个二叉搜索树，并使用中序遍历来遍历它。在测试样例中，它将打印以下输出：

2
3
4
5
6
7
8

接下来，我们将把这个二叉搜索树转换为一个有序循环双向链表。这个过程需要使用中序遍历来访问二叉树的节点，并将它们连接起来。以下是一个 Python 代码示例：

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

class DoublyListNode:
    def __init__(self, val=None):
        self.val = val
        self.prev = None
        self.next = None

def treeToDoublyList(node):
    if node is None:
        return None

    head, tail = helper(node)
    head.prev = tail
    tail.next = head

    return head

def helper(node):
    if node is None:
        return None, None

    leftHead, leftTail = helper(node.left)
    rightHead, rightTail = helper(node.right)

    newHead = DoublyListNode(node.val)
    newTail = newHead

    if leftTail is not None:
        leftTail.next = newHead
        newHead.prev = leftTail
        newHead = leftHead

    if rightHead is not None:
        newTail.next = rightHead
        rightHead.prev = newTail
        newTail = rightTail

    return newHead, newTail

# 测试样例
root = None
root = insertNode(root, 5)
root = insertNode(root, 3)
root = insertNode(root, 7)
root = insertNode(root, 2)
root = insertNode(root, 4)
root = insertNode(root, 6)
root = insertNode(root, 8)

head = treeToDoublyList(root)

while head is not None:
    print(head.val)
    head = head.next

这个代码定义了一个新的节点类型 DoublyListNode，它包含一个 prev 指针和一个 next 指针，用于构建双向链表。函数 treeToDoublyList 递归地遍历二叉搜索树，并返回链表的头和尾节点。函数 helper 递归地构建链表，并返回左子树和右子树的头和尾节点。在测试样例中，它将打印以下输出：

2
3
4
5
6
7
8

这个输出是一个双向链表，它的头节点是 2，尾节点是 8，它是环形的，即头节点的 prev 指针指向尾节点，尾节点的 next 指针指向头节点。