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

🕗 发布于 2024-07-24 20:03 数据结构 链表 c语言 c++

文章目录

在数据结构与算法中，树和链表都是非常重要的数据结构。二元查找树（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);
    }
};

示例

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

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

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;
}

7. 效率与空间复杂度比较

二元查找树：

插入、删除和查找的时间复杂度平均为O(log n)，在最坏的情况下（树退化为链表）为O(n)。
空间复杂度为O(n)，用于存储树中的节点。

有序双向链表：

插入和删除操作在O(1)时间复杂度内完成，因为每个节点都包含前驱和后继指针。
查找操作的时间复杂度为O(n)，因为可能需要遍历整个链表。
空间复杂度同样为O(n)，用于存储链表中的节点。

在实际应用中，二元查找树在搜索效率方面具有优势，特别是在数据量较大且分布均匀时。然而，当树高度不平衡时，其性能会显著下降。另一方面，有序双向链表在插入和删除操作上具有更好的性能保证，但查找操作效率较低。

8. 结论

二元查找树和有序双向链表各有优缺点，适用于不同的场景。二元查找树更适合需要频繁搜索的场景，而有序双向链表则在插入和删除操作更频繁的场景中表现更好。选择哪种数据结构取决于具体应用的需求和性能考量。

在实现时，二元查找树的结构简单，逻辑清晰，而有序双向链表需要额外的指针来维护前后关系，这可能会增加代码的复杂性。然而，有序双向链表的一个优点是它不会像二元查找树那样出现平衡问题，这使得它在某些应用中更加稳定。

原文地址：https://blog.csdn.net/qq_35320456/article/details/140588720

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：AI谈AI：开源项目的机遇与挑战 - 从创新到可持续发展
下一篇：数据结构第一讲：复杂度

免费申请 Let‘s Encrypt SSL 证书
在网络安全日益重要的今天，为网站启用 SSL 证书是保障数据安全和用户信任的关键。Let's Encrypt 提供的免费 SSL 证书是一个很好的选择。下面我们详细介绍如何为网站域名申请该证书。
阅读更多2024-11-16
Spring Boot 中使用 @Transactional 注解配置事务管理
Spring Boot 中使用 @Transactional 注解配置事务管理
阅读更多2024-11-16
自定义实体类中DateTime属性的序列化格式
本文介绍了Newtonsoft.Json与System.Text.Json下如何在实体上自定义DateTime类型的序列化格式。
阅读更多2024-11-16
阅读2020-2023年《国外军用无人机装备技术发展综述》笔记_作战无人机和察打无人机图鉴
本篇对2020-2023年《国外军用无人机装备技术发展综述》这几篇文章中所提到的作战无人机和察打无人机逐个更详细的介绍。
阅读更多2024-11-16
Flutter：InheritedWidget数据共享
未使用数据共享时，要传递数据，只能组件间一级一级向下传递。InheritedWidget数据共享，优化下上边代码。下边代码中，创建了一个按钮，当点击时。
阅读更多2024-11-16
Ubuntu22.04.2 k8s部署
Helm 是 Kubernetes 的一个包管理工具，类似于 Linux 下的 apt 或 yum。它可以帮助用户通过定义配置文件的方式来部署和管理 Kubernetes 应用，极大地简化了应用在 K
阅读更多2024-11-16
推荐一款全能网络视频下载工具：闪豆视频下载器
是一款网络视频，主要支持下载同时，软件还具备4K、1080p60、720p60、1080+、720p、480p、360p画质的视频下载，无论你想要哪种画质，在这里都能满足你。
阅读更多2024-11-16
3D电子商务是什么？如何利用3D技术提升销售转化？
3D电子商务，简而言之，就是利用3D产品模型来优化和提升在线购物体验的一种新型电商模式。它打破了传统二维图片的局限，使消费者能够以前所未有的方式“触摸”和感受商品。无论是家具、服装、电子产品还是艺术品
阅读更多2024-11-16
麒麟系统下docker搭建jenkins
执行这个命令后，我们将启动一个Jenkins容器，并且可以通过宿主机的7083端口访问Jenkins的Web界面，通过7084端口访问Jenkins的调试端口。同时，Jenkins的数据会被存储在宿主
阅读更多2024-11-16
前后端交互之动态列
在做项目时，有时候后会遇到后端使用了**聚合函数**，导致生成的**对象的属性数量或数量不固定**，因此无法建立一个与之对应的对象来向前端传递数据，这时可以采用NameDataListVO向前端传递
阅读更多2024-11-16