C语言经典算法之二叉树的中序线索化

目录

前言

A.建议

B.简介

一 代码实现

二 时空复杂度

A.时间复杂度：

B.空间复杂度：

三 优缺点

A.优点：

B.缺点：

四 现实中应用

---

前言

A.建议

1.学习算法最重要的是理解算法的每一步，而不是记住算法。

2.建议读者学习算法的时候，自己手动一步一步地运行算法。

tips：文中的对数均以2为底数

B.简介

中序线索化是一种在二叉树中提供额外信息以加速中序遍历的方法。通过中序线索化，我们为每个节点添加指向其在中序遍历中前驱和后继的线索。这使得在遍历时可以更快地找到前后相邻的节点，而无需通过递归或栈的方式。

一 代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    int isThreaded;  // 标记是否是线索
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->isThreaded = 0;  // 默认不是线索
    }
    return newNode;
}

// 中序线索化函数
void inOrderThread(TreeNode* root, TreeNode** prev) {
    if (root != NULL) {
        // 递归处理左子树
        inOrderThread(root->left, prev);

        // 处理当前节点
        if (root->left == NULL) {
            // 如果左子树为空，建立前驱线索
            root->left = *prev;
            root->isThreaded = 1;
        }

        if (*prev != NULL && (*prev)->right == NULL) {
            // 如果前一个节点的右子树为空，建立后继线索
            (*prev)->right = root;
            (*prev)->isThreaded = 1;
        }

        // 更新前一个节点为当前节点
        *prev = root;

        // 递归处理右子树
        inOrderThread(root->right, prev);
    }
}

// 中序线索化二叉树的入口函数
void inOrderThreadedBinaryTree(TreeNode* root) {
    TreeNode* prev = NULL;  // 用于保存前一个节点的指针
    inOrderThread(root, &prev);
}

// 中序线索化后的中序遍历
void inOrderThreadedTraversal(TreeNode* root) {
    TreeNode* current = root;
    while (current != NULL) {
        // 找到中序遍历的第一个节点（最左边的节点）
        while (current->left != NULL && !current->isThreaded) {
            current = current->left;
        }

        // 处理当前节点
        printf("%d ", current->data);

        // 如果存在后继线索，直接跳转到后继节点
        if (current->isThreaded) {
            current = current->right;
        } else {
            // 否则，沿着右子树继续中序遍历
            current = current->right;
            while (current != NULL && !current->isThreaded) {
                current = current->left;
            }
        }
    }
}

// 释放二叉树的内存
void freeBinaryTree(TreeNode* root) {
    if (root != NULL) {
        freeBinaryTree(root->left);
        freeBinaryTree(root->right);
        free(root);
    }
}

int main() {
    // 创建一棵示例二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // 中序线索化
    inOrderThreadedBinaryTree(root);

    // 中序线索化后的中序遍历
    printf("Inorder Threaded Traversal: ");
    inOrderThreadedTraversal(root);
    printf("\n");

    // 释放内存
    freeBinaryTree(root);

    return 0;
}

这个示例中，首先创建了一棵二叉树，然后使用inOrderThreadedBinaryTree函数进行中序线索化，最后通过inOrderThreadedTraversal函数进行中序线索化后的中序遍历。请注意，线索化的过程通过添加线索标记（isThreaded）和调整左右指针来完成。

二 时空复杂度

A.时间复杂度：

时间开销分为以下两部分

线索化过程： 对于一棵有 n 个节点的二叉树，进行中序线索化的过程需要访问每个节点一次。每次对节点的操作是常数时间的，因此线索化的时间复杂度是 。

中序遍历过程： 中序遍历的过程也需要访问每个节点一次。在每个节点，通过检查 isThreaded 标记，可以在常数时间内找到节点的前驱或后继。因此，中序遍历的时间复杂度同样是。

因此，整个中序线索化和遍历过程的时间复杂度为。

B.空间复杂度：

空间开销分为以下两部分

递归调用栈： 线索化和遍历的过程中使用了递归，递归调用栈的深度最大为树的高度。在最坏情况下，如果树是链式的，递归深度为 n，因此递归调用栈的空间复杂度为 。在平衡树的情况下，递归深度为，空间复杂度为。

额外空间： 除了递归调用栈，算法本身只使用了常数级别的额外空间用于节点的标记。因此，额外空间的复杂度是 。

因此，整个算法的空间复杂度主要由递归调用栈决定，在最坏情况下为 O(n)，在平衡树的情况下为 。

三 优缺点

A.优点：

空间效率： 中序线索化节省了存储线索二叉树所需的额外指针空间，减小了内存占用。

中序遍历的加速： 由于线索化添加了前驱和后继的信息，中序遍历时能够更快速地找到下一个节点，提高了遍历效率。

不破坏原树结构： 线索化的过程并没有破坏原二叉树的结构，因此可以在需要的时候进行线索化，而不会影响其他操作。

B.缺点：

实现复杂度： 中序线索化的实现相对较为复杂，需要考虑节点的前驱和后继关系，以及线索的添加和维护。这可能使代码相对难以理解和维护。

不适用于频繁修改的场景： 如果二叉树的结构经常发生变化，即频繁地插入、删除节点，那么维护线索关系可能会带来额外的复杂性和开销。

不适用于非线性结构： 中序线索化主要适用于二叉搜索树等中序遍历有序性质的结构，对于非线性结构的二叉树，线索化可能并不具备明显的优势。

四 现实中应用

tips:二叉树的中序线索化在现在已经不常用了，以下是其在计算机发展早期的应用场景

数据库索引结构：

在数据库系统中，B+树是一种常见的索引结构，而中序线索化可以用于优化B+树的中序遍历。这种优化可以提高数据库查询性能，因为它能更有效地找到下一个索引值。

表达式树的中序遍历：

在编译器和计算器中，表达式通常以树的形式表示，被称为表达式树。中序线索化可以用于优化表达式树的中序遍历，这在编译器优化和表达式求值中都有应用。

图形用户界面：

在图形用户界面（GUI）的实现中，有时使用二叉树来表示控件的层次结构。中序线索化可以用于优化在层次结构上的遍历，特别是在寻找焦点、焦点移动和遍历可见控件时。

网络路由表：

在网络路由中，路由表通常使用二叉树表示，中序线索化可以用于优化对路由表的中序遍历，从而提高查找最优路径的效率。

文件系统：

在文件系统的目录结构中，中序线索化可以用于提高对目录树的中序遍历效率，这对于文件的查找和排序等操作是有帮助的。