线索化二叉树

以下是实现该结构并进行中序遍历的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
using namespace std;

// 定义线索二叉树节点的结构
struct ThreadedNode {
    int value;                      // 节点的值
    ThreadedNode* left;             // 指向左子节点
    ThreadedNode* right;            // 指向右子节点
    bool lThread;                   // 左指针是否为线索
    bool rThread;                   // 右指针是否为线索

    // 构造函数初始化节点值，并将左右指针初始化为空，线索标志初始化为 false
    ThreadedNode(int val) : value(val), left(nullptr), right(nullptr), lThread(false), rThread(false) {}
};

// 插入节点并构建线索二叉树的函数
ThreadedNode* insert(ThreadedNode* root, int key) {
    // 创建一个新节点
    ThreadedNode* newNode = new ThreadedNode(key);

    // 如果树为空，直接返回新节点作为根节点
    if (root == nullptr) return newNode;

    // `current` 用于跟踪当前节点，`parent` 用于跟踪当前节点的父节点
    ThreadedNode* current = root;
    ThreadedNode* parent = nullptr;

    // 找到要插入的位置
    while (current != nullptr) {
        parent = current;

        // 插入左子树
        if (key < current->value) {
            // 如果左指针不是线索，继续向左子树移动
            if (!current->lThread)
                current = current->left;
            else
                break; // 遇到线索停止
        } 
        // 插入右子树
        else {
            // 如果右指针不是线索，继续向右子树移动
            if (!current->rThread)
                current = current->right;
            else
                break; // 遇到线索停止
        }
    }

    // 根据值的大小决定插入到左子树还是右子树
    if (key < parent->value) {
        // 左子树插入
        newNode->left = parent->left;  // 新节点的左指针指向父节点的左指针
        newNode->right = parent;       // 新节点的右指针指向父节点
        parent->lThread = false;       // 插入后，父节点的左指针不再是线索
        parent->left = newNode;        // 父节点的左子树变为新节点
    } else {
        // 右子树插入
        newNode->right = parent->right; // 新节点的右指针指向父节点的右指针
        newNode->left = parent;         // 新节点的左指针指向父节点
        parent->rThread = false;        // 插入后，父节点的右指针不再是线索
        parent->right = newNode;        // 父节点的右子树变为新节点
    }

    // 返回根节点
    return root;
}

// 找到中序遍历的起点（即最左边的节点）
ThreadedNode* leftmost(ThreadedNode* node) {
    if (node == nullptr) return nullptr;
    // 一直移动到没有左子节点的节点
    while (!node->lThread) 
        node = node->left;
    return node;
}

// 线索化二叉树的中序遍历
void inOrderTraversal(ThreadedNode* root) {
    // 从最左边的节点开始
    ThreadedNode* current = leftmost(root);

    // 遍历整个树
    while (current != nullptr) {
        // 输出当前节点的值
        cout << current->value << " ";

        // 如果当前节点的右指针是线索，直接跳到下一个中序节点
        if (current->rThread)
            current = current->right;
        else
            // 否则找到当前节点右子树中的最左节点
            current = leftmost(current->right);
    }
}

int main() {
    ThreadedNode* root = nullptr;  // 创建一个空的线索二叉树

    // 插入节点，构建线索二叉树
    root = insert(root, 5);  // 插入根节点
    root = insert(root, 3);  // 插入左子节点
    root = insert(root, 8);  // 插入右子节点
    root = insert(root, 2);  // 插入左子树中的左子节点
    root = insert(root, 4);  // 插入左子树中的右子节点

    // 线索化后的中序遍历
    cout << "中序遍历: ";
    inOrderTraversal(root);
    cout << endl;

    return 0;
}

代码说明：

  1. 树的结构：

    • 我们插入节点顺序为 5, 3, 8, 2, 4，构造如下的树：
      1
      2
      3
      4
      5
          5
         / \
        3   8
       / \
      2   4

  2. 中序遍历顺序：

    • 中序遍历的顺序是：先访问左子树，再访问根节点，最后访问右子树.
    • 对于这棵树的中序遍历顺序是：2 3 4 5 8.

  3. 关键函数：

    • insert：在二叉树中插入节点，同时维护线索化指针.
    • leftmost：寻找中序遍历中最左边的节点，作为遍历起点.
    • inOrderTraversal：通过线索化指针进行中序遍历.

输出结果：

运行此代码，输出将会是：

1
中序遍历: 2 3 4 5 8

线索化二叉树解释：

1. 初始状态：

我们创建了一个空的线索二叉树 root，即 root = nullptr.

2. 插入节点 5：

  • 调用 insert(root, 5).
  • 因为 root 是 nullptr，直接返回新节点 5 作为根节点.此时树结构如下：
    1
    5
  • 5 没有子节点，也没有线索.

3. 插入节点 3：

  • 调用 insert(root, 3)，即在节点 5 的基础上插入.
  • 3 < 5，因此我们将其插入到 5 的左子树中.
  • 节点 3 的右指针作为线索指向节点 5，此时树结构如下：
    1
    2
    3
    4
    5
      5
     /
    3
     \
      5 (线索)
  • 5 的左指针不再是线索，它现在有一个真正的左子树（节点 3）.

4. 插入节点 8：

  • 调用 insert(root, 8)，即在当前树结构上插入.
  • 8 > 5，因此我们将其插入到节点 5 的右子树中.
  • 节点 8 的左指针作为线索指向节点 5，此时树结构如下：
    1
    2
    3
    4
    5
    6
      5
     / \
    3   8
     \
      5 (线索)
      8 (线索)
  • 节点 5 的右指针现在指向真正的右子树（节点 8）.

5. 插入节点 2：

  • 调用 insert(root, 2)，即在当前树结构上插入.
  • 2 < 5，继续向左走，2 < 3，因此我们将其插入到节点 3 的左子树中.
  • 节点 2 的右指针作为线索指向节点 3，此时树结构如下：
    1
    2
    3
    4
    5
    6
    7
        5
       / \
      3   8
     / \
    2   5 (线索)
     \
      3 (线索)
  • 节点 3 的左指针不再是线索，它现在有一个真正的左子树（节点 2）.

6. 插入节点 4：

  • 调用 insert(root, 4)，即在当前树结构上插入.
  • 4 < 5，继续向左走，4 > 3，因此我们将其插入到节点 3 的右子树中.
  • 节点 4 的右指针作为线索指向节点 5，此时树结构如下：
    1
    2
    3
    4
    5
    6
    7
    8
        5
       / \
      3   8
     / \
    2   4
    \	 \
    3(线) 5 (线索)

7. 树的最终结构：

经过上述插入操作，最终树的结构如下：

1
2
3
4
5
    5
   / \
  3   8
 / \
2   4
  • 左子树是：3 -> 2, 3 -> 4，并且线索指向相应的节点.

8. 中序遍历过程：

步骤 1：找到最左边的节点

  • 调用 leftmost(root)，找到树中最左边的节点，即 2.

步骤 2：遍历中序节点

  • 当前节点是 2，输出 2，然后查看 2 的右指针，发现它是线索指向节点 3，因此移动到节点 3.
  • 当前节点是 3，输出 3，然后查看 3 的右指针，发现它指向节点 4，移动到节点 4.
  • 当前节点是 4，输出 4，然后查看 4 的右指针，发现它是线索，指向节点 5，移动到节点 5.
  • 当前节点是 5，输出 5，然后查看 5 的右指针，指向真正的右子树，找到最左边的节点 8.
  • 当前节点是 8，输出 8，然后它没有右子树或线索，遍历结束.

9. 中序遍历输出：

最终中序遍历输出是：

1
2 3 4 5 8

这就是整个代码的运行过程和中序遍历结果.