老程序员博客

编程生涯的最后一舞

当前位置：首页 > 技术 > 正文内容

线索二叉树：非递归中序遍历的实现与原理

访客 技术 2026年6月26日 1

在数据结构中，二叉树是一种常见且功能强大的树形结构。然而，对于普通二叉树的遍历（如前序、中序、后序遍历），通常需要借助栈（递归本质上也是利用了系统栈）来存储节点信息，以便在回溯时访问父节点或兄弟节点。当树的深度较大时，这可能导致栈溢出或额外的空间开销。为了优化这一问题，线索二叉树应运而生。

线索二叉树的核心思想是利用二叉树中大量存在的空指针。在一个具有 N 个节点的二叉链表中，总共有 2N 个指针域。如果采用二叉链表作为存储结构，那么 N 个节点将有 N-1 条指向子节点的非空指针，因此会有 2N - (N-1) = N+1 个空指针域。线索二叉树正是通过这些空指针域，建立指向节点前驱和后继的指针，从而避免在遍历时使用栈，实现O(1)额外空间复杂度的线性遍历。

线索二叉树节点结构

为了区分一个指针是指向子节点还是指向前驱/后继节点（即"线索"），我们需要在每个节点中增加两个标志位。典型的线索二叉树节点结构如下：

typedef char data_elem_t; // 节点数据类型

typedef struct thread_node {
    data_elem_t data;          // 节点数据
    struct thread_node *left;   // 左子节点或前驱节点
    struct thread_node *right;  // 右子节点或后继节点
    int l_tag;                  // 左标志：0表示left指向左子树，1表示left指向前驱节点
    int r_tag;                  // 右标志：0表示right指向右子树，1表示right指向后继节点
} ThreadNode;

typedef struct {
    ThreadNode *root;           // 树的根节点
    int node_count;             // 节点数量
} ThreadedBinaryTree;

其中，l_tag 和 r_tag 是关键。当 l_tag 为 0 时，left 指针与普通二叉树一样，指向左子节点；当 l_tag 为 1 时，left 指针指向其中序遍历下的前驱节点。同理，r_tag 控制 right 指针是指向右子节点还是其中序遍历下的后继节点。

线索化过程

线索二叉树的构建分为两个主要阶段：

  1. 构建普通二叉树： 按照常规方式创建二叉树，并初始化节点的 left 和 right 指针以及 l_tag 和 r_tag（通常全部设为0，即默认指向子树）。
  2. 线索化： 对已构建的二叉树进行一次遍历（通常是中序遍历），在遍历过程中，将所有为空的 left 指针连接到其前驱节点，将所有为空的 right 指针连接到其后继节点，并相应地设置 l_tag 和 r_tag 为 1。

以下图为例展示线索化后的结构：

线索二叉树示意图

在进行中序线索化时，我们需要一个辅助指针来跟踪上一个被访问的节点。当当前节点的 left 指针为空时，它应该指向前一个被访问的节点；当前一个节点的 right 指针为空时，它应该指向当前节点。

static ThreadNode *g_last_visited_node = NULL; // 用于线索化时跟踪前一个访问的节点

// 递归地进行中序线索化
static void internalInOrderThreading(ThreadNode *node) {
    if (node == NULL) {
        return;
    }

    // 递归线索化左子树
    internalInOrderThreading(node->left);

    // 处理当前节点：
    // 如果当前节点的左指针为空，则将其线索化指向前驱
    if (node->left == NULL) {
        node->l_tag = 1;
        node->left = g_last_visited_node;
    }

    // 如果前一个节点的右指针为空，则将其线索化指向当前节点
    if (g_last_visited_node != NULL && g_last_visited_node->right == NULL) {
        g_last_visited_node->r_tag = 1;
        g_last_visited_node->right = node;
    }

    // 更新g_last_visited_node为当前节点
    g_last_visited_node = node;

    // 递归线索化右子树
    internalInOrderThreading(node->right);
}

// 对整个线索二叉树进行中序线索化
void threadTreeInOrder(ThreadedBinaryTree *tree) {
    if (tree == NULL || tree->root == NULL) {
        return;
    }
    g_last_visited_node = NULL; // 每次线索化前重置
    internalInOrderThreading(tree->root);
    // 处理线索化结束后，最后一个节点的后继指针。
    // 如果最后一个节点的right指针仍为空，将其设为NULL并标记为线索
    if (g_last_visited_node != NULL && g_last_visited_node->right == NULL) {
        g_last_visited_node->r_tag = 1;
        g_last_visited_node->right = NULL;
    }
}

中序遍历线索二叉树

线索二叉树的最大优势在于，一旦完成线索化，就可以通过非递归方式进行线性遍历，无需栈的支持。中序遍历线索二叉树的步骤如下：

  1. 从根节点开始，找到中序遍历的第一个节点（即沿着左子树一直走到最左端的节点）。
  2. 访问该节点。
  3. 如果该节点的 r_tag 为 1，则其 right 指针指向的就是中序后继，直接移动到该后继节点。
  4. 如果该节点的 r_tag 为 0，则其 right 指针指向的是右子树。此时，我们需要找到右子树中中序遍历的第一个节点（即右子树的最左端节点）。
  5. 重复步骤 2-4，直到所有节点都被访问，或到达根节点右子树的最右端节点的后继为 NULL。
void traverseThreadedTreeInOrder(ThreadedBinaryTree *tree) {
    if (tree == NULL || tree->root == NULL) {
        return;
    }

    ThreadNode *currentNode = tree->root;

    // 1. 找到中序遍历的第一个节点（最左子节点）
    while (currentNode != NULL && currentNode->l_tag == 0) {
        currentNode = currentNode->left;
    }

    // 2. 开始遍历
    while (currentNode != NULL) {
        printNodeData(currentNode); // 访问当前节点

        // 如果当前节点的右指针是线索，直接跳到后继节点
        if (currentNode->r_tag == 1) {
            currentNode = currentNode->right;
        } else {
            // 如果右指针是子树，则找到右子树中中序遍历的第一个节点
            currentNode = currentNode->right;
            while (currentNode != NULL && currentNode->l_tag == 0) {
                currentNode = currentNode->left;
            }
        }
    }
    printf("\n"); // 遍历结束后换行
}

完整的代码示例

thread_tree.h

#ifndef THREAD_TREE_H
#define THREAD_TREE_H

#include <stdbool.h> // For bool type

typedef char data_elem_t;

typedef struct thread_node {
    data_elem_t data;
    struct thread_node *left;
    struct thread_node *right;
    int l_tag; // 0: left child, 1: predecessor
    int r_tag; // 0: right child, 1: successor
} ThreadNode;

typedef struct {
    ThreadNode *root;
    int node_count;
} ThreadedBinaryTree;

// 创建并初始化一个空的线索二叉树
ThreadedBinaryTree *createThreadedTree();

// 释放线索二叉树所有节点内存
void destroyThreadedTree(ThreadedBinaryTree *tree);

// 初始化线索二叉树的根节点
void initializeThreadedTreeRoot(ThreadedBinaryTree *tree, ThreadNode *root_node);

// 创建一个新节点
ThreadNode *createThreadNode(data_elem_t data);

// 为父节点添加左右子节点 (注意：这里假定左右子节点一开始不是线索)
void addChildNodes(ThreadedBinaryTree *tree, ThreadNode *parent, ThreadNode *left_child, ThreadNode *right_child);

// 打印节点数据
void printNodeData(ThreadNode *node);

// 中序线索化二叉树
void threadTreeInOrder(ThreadedBinaryTree *tree);

// 中序遍历线索化后的二叉树
void traverseThreadedTreeInOrder(ThreadedBinaryTree *tree);

#endif // THREAD_TREE_H

thread_tree.c

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

// 创建并初始化一个空的线索二叉树
ThreadedBinaryTree *createThreadedTree() {
    ThreadedBinaryTree *tree = (ThreadedBinaryTree *)malloc(sizeof(ThreadedBinaryTree));
    if (tree == NULL) {
        perror("Failed to allocate memory for ThreadedBinaryTree");
        exit(EXIT_FAILURE);
    }
    tree->node_count = 0;
    tree->root = NULL;
    return tree;
}

// 初始化线索二叉树的根节点
void initializeThreadedTreeRoot(ThreadedBinaryTree *tree, ThreadNode *root_node) {
    if (tree != NULL && tree->root == NULL && root_node != NULL) {
        tree->root = root_node;
        tree->node_count = 1;
    } else if (root_node == NULL) {
        fprintf(stderr, "Error: Cannot initialize tree with a NULL root node.\n");
    } else if (tree->root != NULL) {
        fprintf(stderr, "Warning: Tree already has a root. Not re-initializing.\n");
    }
}

// 创建一个新节点
ThreadNode *createThreadNode(data_elem_t data) {
    ThreadNode *node = (ThreadNode *)malloc(sizeof(ThreadNode));
    if (node == NULL) {
        perror("Failed to allocate memory for ThreadNode");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->left = NULL;
    node->l_tag = 0; // 默认指向子节点
    node->right = NULL;
    node->r_tag = 0; // 默认指向子节点
    return node;
}

// 为父节点添加左右子节点 (注意：这里假定左右子节点一开始不是线索)
void addChildNodes(ThreadedBinaryTree *tree, ThreadNode *parent, ThreadNode *left_child, ThreadNode *right_child) {
    if (tree == NULL || parent == NULL) {
        fprintf(stderr, "Error: Parent or tree is NULL for addChildNodes.\n");
        return;
    }

    if (left_child != NULL) {
        parent->left = left_child;
        tree->node_count++;
    }
    if (right_child != NULL) {
        parent->right = right_child;
        tree->node_count++;
    }
}

// 打印节点数据
void printNodeData(ThreadNode *node) {
    if (node != NULL) {
        printf("%c ", node->data);
    }
}

// 全局静态指针，用于在递归线索化过程中跟踪上一个被访问的节点
static ThreadNode *g_last_visited_node = NULL;

// 递归地进行中序线索化
static void internalInOrderThreading(ThreadNode *node) {
    if (node == NULL) {
        return;
    }

    // 递归线索化左子树
    internalInOrderThreading(node->left);

    // 处理当前节点：
    // 如果当前节点的左指针为空，则将其线索化指向前驱
    if (node->left == NULL) {
        node->l_tag = 1;
        node->left = g_last_visited_node;
    }

    // 如果前一个节点的右指针为空，则将其线索化指向当前节点
    if (g_last_visited_node != NULL && g_last_visited_node->right == NULL) {
        g_last_visited_node->r_tag = 1;
        g_last_visited_node->right = node;
    }

    // 更新g_last_visited_node为当前节点
    g_last_visited_node = node;

    // 递归线索化右子树
    internalInOrderThreading(node->right);
}

// 对整个线索二叉树进行中序线索化
void threadTreeInOrder(ThreadedBinaryTree *tree) {
    if (tree == NULL || tree->root == NULL) {
        return;
    }
    g_last_visited_node = NULL; // 每次线索化前重置
    internalInOrderThreading(tree->root);
    // 处理线索化结束后，最后一个节点的后继指针。
    // 如果最后一个节点的right指针仍为空，将其设为NULL并标记为线索
    if (g_last_visited_node != NULL && g_last_visited_node->right == NULL) {
        g_last_visited_node->r_tag = 1;
        g_last_visited_node->right = NULL;
    }
}

// 中序遍历线索化后的二叉树
void traverseThreadedTreeInOrder(ThreadedBinaryTree *tree) {
    if (tree == NULL || tree->root == NULL) {
        return;
    }

    ThreadNode *currentNode = tree->root;

    // 1. 找到中序遍历的第一个节点（最左子节点）
    while (currentNode != NULL && currentNode->l_tag == 0) {
        currentNode = currentNode->left;
    }

    // 2. 开始遍历
    while (currentNode != NULL) {
        printNodeData(currentNode); // 访问当前节点

        // 如果当前节点的右指针是线索，直接跳到后继节点
        if (currentNode->r_tag == 1) {
            currentNode = currentNode->right;
        } else {
            // 如果右指针是子树，则找到右子树中中序遍历的第一个节点
            currentNode = currentNode->right;
            while (currentNode != NULL && currentNode->l_tag == 0) {
                currentNode = currentNode->left;
            }
        }
    }
    printf("\n"); // 遍历结束后换行
}

// 辅助函数：递归销毁节点
static void recursiveDestroyNode(ThreadNode *node) {
    if (node == NULL) {
        return;
    }

    // 只有当指针指向子树时才递归销毁，避免沿着线索重复销毁或销毁外部节点
    if (node->l_tag == 0) {
        recursiveDestroyNode(node->left);
    }
    if (node->r_tag == 0) {
        recursiveDestroyNode(node->right);
    }
    free(node);
}

// 释放线索二叉树所有节点内存
void destroyThreadedTree(ThreadedBinaryTree *tree) {
    if (tree == NULL) {
        return;
    }
    recursiveDestroyNode(tree->root);
    //printf("\nDestroyed %d nodes.\n", tree->node_count); // Note: node_count might not be accurate after threading
    free(tree);
}

main.c

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

// 构建一个测试用的二叉树
ThreadedBinaryTree *buildTestTree() {
    ThreadedBinaryTree *tree = createThreadedTree();

    ThreadNode *nodeA = createThreadNode('A');
    ThreadNode *nodeB = createThreadNode('B');
    ThreadNode *nodeC = createThreadNode('C');
    ThreadNode *nodeD = createThreadNode('D');
    ThreadNode *nodeE = createThreadNode('E');
    ThreadNode *nodeF = createThreadNode('F');
    ThreadNode *nodeG = createThreadNode('G');
    ThreadNode *nodeH = createThreadNode('H');
    ThreadNode *nodeK = createThreadNode('K');

    initializeThreadedTreeRoot(tree, nodeA);

    // 建立树的结构
    addChildNodes(tree, nodeA, nodeB, nodeE);
    addChildNodes(tree, nodeB, NULL, nodeC);
    addChildNodes(tree, nodeC, nodeD, NULL);
    addChildNodes(tree, nodeE, NULL, nodeF);
    addChildNodes(tree, nodeF, nodeG, NULL);
    addChildNodes(tree, nodeG, nodeH, nodeK);

    return tree;
}

int main() {
    ThreadedBinaryTree *myTree = buildTestTree();
    printf("初始树节点数量: %d\n", myTree->node_count);

    printf("开始中序线索化...\n");
    threadTreeInOrder(myTree);
    printf("线索化完成。\n");

    printf("中序遍历线索二叉树: ");
    traverseThreadedTreeInOrder(myTree);

    destroyThreadedTree(myTree);
    printf("树已销毁。\n");

    return 0;
}

运行结果

初始树节点数量: 9
开始中序线索化...
线索化完成。
中序遍历线索二叉树: B D C A H G K F E
树已销毁。
标签: C语言
返回列表

上一篇：冒泡排序算法实现

下一篇：Codeforces 比赛复盘与题解分析

相关文章

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class        （可选）id           （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

Mac 安装 Node.js 指南

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成 无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件） 和 Listeners（监听器） 是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

发表评论

访客

◎欢迎参与讨论，请在这里发表您的看法和观点。

Copyright © agingcoder.cn

Powered By Z-BlogPHP. Theme by TOYEAN.