本文共 1177 字，大约阅读时间需要 3 分钟。

原文地址：

遍历一个二叉树要么用递归，要么用附加的栈。线索二叉树的思想是让中序遍历更快，或者不用栈和递归。一个二叉树通过构建所有右孩子的指针建立索引，这个指针一般为NULL指向中序后继节点（如果存在的话）。

线索二叉树有两种类型：

单线索：使一个NULL右指针指向中序先驱（如果后继存在）

双线索：左右NULL指针分别指向中序的先驱和中序的后继。在翻转中序遍历与后序遍历的时候，前驱线索就很有用啦。

线索在快速访问祖先节点的时候也很有用。

下图是一个单线索二叉树的例子，虚线表示的是线索。

C表示的带线索的节点

下面是C表示的带线索的节点

struct Node {    int data;    Node *left, *right;    bool rightThread;  }

因为右指针有两个用途，所以布尔变量rightThread用于表示右指针指向的是右孩子还是中序后继。类似地，我们可以添加leftThread作为双线索二叉树。

用线索中序遍历

下面是中序遍历线索二叉树的C代码。

// Utility function to find leftmost node in atree rooted with nstruct Node* leftMost(struct Node *n){    if (n == NULL)       return NULL;    while (n->left != NULL)        n = n->left;    return n;}// C code to do inorder traversal in a threadded binary treevoid inOrder(struct Node *root){    struct Node *cur = leftmost(root);    while (cur != NULL)    {        printf("%d ", cur->data);        // If this node is a thread node, then go to        // inorder successor        if (cur->rightThread)            cur = cur->right;        else // Else go to the leftmost child in right subtree            cur = leftmost(cur->right);    }}

下图描述了用线索做中序遍历。

我们将很快讨论线索二叉树的插入删除操作。

来源：