数据结构之二元查找树转有序双向链表详解与示例（C/C++）

文章目录

- 1. 二元查找树（BST）简介
- 2. 有序双向链表（DLL）简介
- 3. 二元查找树的实现
- 4. 转换为有序双向链表的步骤
- 5. C++实现代码
- 6. C实现代码
- 7. 效率与空间复杂度比较
- 8. 结论

在数据结构与算法中，树和链表都是非常重要的数据结构。二元查找树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有很好的查找性能。而双向链表（Doubly Linked List）则是一种线性结构，它允许我们在两个方向上遍历。本文将详细介绍如何将一个二元查找树转换为有序双向链表。

1. 二元查找树（BST）简介

二元查找树是一种数据结构，其中每个节点最多有两个子节点：左子树节点值小于当前节点，右子树节点值大于当前节点。这种性质使得BST能够支持高效的查找操作。

2. 有序双向链表（DLL）简介

有序双向链表是一种链表结构，除了具有链表节点的基本特征外，它还具有指向前一个节点的指针，这使得链表节点可以双向访问。此外，链表节点按照节点值的顺序排列，形成有序链表。

3. 二元查找树的实现

首先定义二元查找树的节点结构体：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class BinarySearchTree {
public:BinarySearchTree() : root(nullptr) {}void insert(int val) {root = insertIntoTree(root, val);}TreeNode* insertIntoTree(TreeNode* node, int val) {if (node == nullptr) return new TreeNode(val);if (val < node->val) {node->left = insertIntoTree(node->left, val);} else {node->right = insertIntoTree(node->right, val);}return node;}// 这里可以添加更多的操作，例如查找、删除等...
};

4. 转换为有序双向链表的步骤

转换过程如下：

从二元查找树的根节点开始，进行中序遍历（左-根-右）。
遍历过程中，将节点转换为链表节点，并维护前一个节点和后一个节点的指针关系。
遍历完成后，头节点的前驱节点指向nullptr，最后一个节点的后继节点也指向nullptr，形成一个闭合的双向链表。

5. C++实现代码

下面是一个C++示例，展示如何实现二元查找树到有序双向链表的转换：

class Node {
public:int val;Node *prev;Node *next;Node(int x) : val(x), prev(nullptr), next(nullptr) {}
};class BinarySearchTreeToDoublyLinkedList {
public:Node* convert(TreeNode* root) {if (root == nullptr) return nullptr;Node* head = nullptr, *prev = nullptr;convertTreeToList(root, &head, &prev);// 闭合双向链表if (prev != nullptr) {prev->next = head;head->prev = prev;}return head;}void convertTreeToList(TreeNode* node, Node** headRef, Node** prevRef) {if (node == nullptr) return;// 左子树转换convertTreeToList(node->left, headRef, prevRef);// 处理当前节点Node* newNode = new Node(node->val);if (*headRef == nullptr) {*headRef = newNode;} else {(*prevRef)->next = newNode;newNode->prev = *prevRef;}*prevRef = newNode;// 右子树转换convertTreeToList(node->right, headRef, prevRef);}
};

示例

假设我们有以下二元查找树：

    4/ \2   5/ \
1   3

通过上述代码转换后，我们得到以下有序双向链表：

1 <-> 2 <-> 3 <-> 4 <-> 5

6. C实现代码

以下是一个完整的C语言示例，展示了如何将二元查找树转换为有序双向链表：

#include <stdio.h>
#include <stdlib.h>// 二元查找树节点定义
typedef struct Node {int data;struct Node* left;struct Node* right;
} Node;// 双向链表节点定义
typedef struct DListNode {int data;struct DListNode* prev;struct DListNode* next;
} DListNode;// 创建双向链表节点
DListNode* createDListNode(int data) {DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));newNode->data = data;newNode->prev = newNode->next = NULL;return newNode;
}// 插入节点
Node* insert(Node* root, int data) {if (root == NULL) {return createNode(data);}if (data < root->data) {root->left = insert(root->left, data);} else if (data > root->data) {root->right = insert(root->right, data);}return root;
}// 查找节点
Node* search(Node* root, int data) {if (root == NULL || root->data == data) {return root;}if (data < root->data) {return search(root->left, data);}return search(root->right, data);
}// 将二元查找树转换为双向链表
DListNode* bstToDList(Node* root) {if (root == NULL) {return NULL;}DListNode* head = NULL;DListNode* tail = NULL;// 递归遍历树if (root->left != NULL) {head = bstToDList(root->left);}if (head != NULL) {head->next = createDListNode(root->data);head->next->prev = head;} else {head = createDListNode(root->data);}if (root->right != NULL) {tail = bstToDList(root->right);}if (tail != NULL) {tail->prev = head;head->next = tail;} else {tail = head;}return head;
}// 打印双向链表
void printDList(DListNode* head) {DListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Node* root = NULL;root = insert(root, 50);insert(root, 30);insert(root, 70);insert(root, 20);insert(root, 40);insert(root, 60);insert(root, 80);printf("BST elements: ");Node* temp = root;while (temp != NULL) {printf("%d ", temp->data);temp = temp->right;}printf("\n");DListNode* dlist = bstToDList(root);printf("Doubly linked list elements: ");printDList(dlist);return 0;
}