二叉树转循环双向链表

17 Mar 2025 | 4 分钟阅读

二叉树是计算机科学中的基本数据结构，它提供了一种有组织的方式来存储和管理数据。另一方面，循环双向链表（CDLL）具有一个循环结构，其中每个节点都指向其前一个节点和后一个节点。将二叉树转换为 CDLL 涉及在保持自然顺序的同时，将树的节点重新排列成循环双向链表。本页将探讨此转换的方法、算法和实现细节。

理解二叉树和 CDLL

二叉树是一种层次数据结构，由节点组成，每个节点最多有两个子节点，称为左子节点和右子节点。另一方面，CDLL 是一种链表，其中最后一个节点指向第一个节点，反之亦然，从而形成一个循环结构。CDLL 节点包含数据以及两个指针：一个指向下一个节点，一个指向前一个节点。

伪代码

treeToCDLLUtil(root, head, tail):
    if root is NULL:
        return
    treeToCDLLUtil(root->left, head, tail)
    if head is NULL:
        head = root
        tail = root
    else:
        tail->right = root
        root->left = tail
        tail = root
    treeToCDLLUtil(root->right, head, tail)
    tail->right = head
    head->left = tail
treeToCDLL(root):
    head = NULL
    tail = NULL
    treeToCDLLUtil(root, head, tail)

二叉树转换为 CDLL 的算法

输入：二叉树的根节点

1. 初始化头尾指针

将生成的 CDLL 的头指针和尾指针初始化为 NULL。

2. 定义辅助函数

创建一个名为 treeToCDLLUtil 的辅助函数，该函数接受以下参数：
二叉树的根节点
指向生成的 CDLL 头指针的引用
指向生成的 CDLL 尾指针的引用

3. 辅助函数 (treeToCDLLUtil)

如果根节点为 NULL，则返回。
递归调用 treeToCDLLUtil 处理左子树。

4. 处理当前节点

如果 head 为 NULL

将头指针和尾指针设置为当前节点。

否则

将 tail->right 连接到当前节点。
将当前节点的 left 连接到 tail。
将 tail 更新为当前节点。

5. 处理右子树

递归调用 treeToCDLLUtil 处理右子树。

6. 连接头尾

处理完两个子树后，使 CDLL 循环化。
将 tail->right 连接到 head。
将 head->left 连接到 tail。

7. 返回

从辅助函数返回。

主函数

调用辅助函数 treeToCDLLUtil，传入二叉树的根节点、头指针和尾指针。

通过遍历将二叉树转换为 CDLL

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
struct Node* concatenateCDLL(struct Node* leftList, struct Node* rightList) {
    if (leftList == NULL) return rightList;
    if (rightList == NULL) return leftList;
    struct Node* leftLast = leftList->left;
    struct Node* rightLast = rightList->left;
    leftLast->right = rightList;
    rightList->left = leftLast;
    leftList->left = rightLast;
    rightLast->right = leftList;

    return leftList;
}
struct Node* treeToCDLL(struct Node* root) {
    if (root == NULL) return NULL;
    struct Node* leftList = treeToCDLL(root->left);
    struct Node* rightList = treeToCDLL(root->right);
    root->left = root;
    root->right = root;
    leftList = concatenateCDLL(leftList, root);
    leftList = concatenateCDLL(leftList, rightList);
    return leftList;
}
void printCDLL(struct Node* head) {
    if (head == NULL) return;
    struct Node* current = head;
    do {
        printf("%d ", current->data);
        current = current->right;
    } while (current != head);
}
int main() {
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->right = createNode(30);

    struct Node* head = treeToCDLL(root);
    printf("Circular Doubly Linked List: ");
    printCDLL(head);
    return 0;
}

输出

通过递归将二叉树转换为 CDLL

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
void treeToCDLLUtil(struct Node* root, struct Node** head, struct Node** tail) {
    if (root == NULL)
        return;
    treeToCDLLUtil(root->left, head, tail);
    if (*head == NULL) {
        *head = root;
        *tail = root;
    } else {
        (*tail)->right = root;
        root->left = *tail;
        *tail = root;
    }
    struct Node* rightChild = root->right;
    (*tail)->right = *head;
    (*head)->left = *tail;
    treeToCDLLUtil(rightChild, head, tail);
}
void treeToCDLL(struct Node* root, struct Node** head) {
    struct Node* tail = NULL;
    treeToCDLLUtil(root, head, &tail);
}
void printCDLL(struct Node* head) {
    if (head == NULL)
        return;
    struct Node* current = head;
    do {
        printf("%d ", current->data);
        current = current->right;
    } while (current != head);
}
int main() {
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->right = createNode(30);
    struct Node* head = NULL;
    treeToCDLL(root, &head);
    printf("Circular Doubly Linked List: ");
    printCDLL(head);
    return 0;
}

输出

下一个主题检查一个二叉树是否是另一个二叉树的子树

← 上一个下一个 →

二叉树转循环双向链表

理解二叉树和 CDLL

伪代码

二叉树转换为 CDLL 的算法

通过遍历将二叉树转换为 CDLL

通过递归将二叉树转换为 CDLL

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树转循环双向链表

理解二叉树和 CDLL

伪代码

二叉树转换为 CDLL 的算法

通过遍历将二叉树转换为 CDLL

通过递归将二叉树转换为 CDLL

相关帖子

二叉树的顶视图

通过沿主对角线或反对角线翻转子矩阵来检查矩阵转换

从二叉搜索树中删除所有叶子节点

合并重叠区间

将二叉树展平成排序链表

整数流的（运行）中位数

根据给定查询查找满二叉树中着色节点的数量

使用双向链表实现优先队列

二叉树的性质

Map 使用什么数据结构

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器