用c語言實現——一個交互式的中序線索二叉樹系統，支持用戶動態構建、線索化、遍歷和查詢功能

知識補充：什么是中序線索化

? ? ? ? ? ? ? ? ? ? ? ? ? 中序遍歷是什么

一、代碼解釋

1.結構體定義

Node 結構體：
成員說明：
int data：存儲節點的數據值。
struct Node* lchild：該節點的左孩子

struct Node* rchild：該節點的右孩子。
int ltag 和 int rtag：用于標記左孩子和右孩子指針的性質，0 表示指向真正的子節點，1 表示指向該節點在中序遍歷中的前驅或后繼節點。?

作用：表示二叉樹中的一個節點。

QueueNode 結構體：
成員說明：
Node* treeNode：存儲一個二叉樹節點的指針。
struct QueueNode* next：指向隊列中下一個元素。

作用：用于構建隊列，輔助層次構建二叉樹。

Queue 結構體：
成員說明：
QueueNode* front：指向隊列的頭部。
QueueNode* rear：指向隊列的尾部。

作用：表示一個隊列。

2.隊列操作函數createQueue

createQueue 函數：
使用 malloc 分配內存以存儲 Queue 結構體。
檢查分配內存是否成功，若失敗則調用 exit(1) 終止程序。
初始化隊列的頭front 和尾rear 指針為 NULL，表示隊列為空。
返回指向新創建隊列的指針。?

作用：創建一個新的空隊列。

3.隊列的入隊操作enqueue

enqueue 函數
參數：
Queue* q：指向隊列的指針。
Node* treeNode：指向要插入隊列的二叉樹節點的指針。

動態分配內存以存儲一個新的隊列節點。

?檢查內存分配是否成功，若失敗則直接返回，不進行后續操作。

將傳入的二叉樹節點的地址賦值給新隊列節點的 treeNode 成員，建立關聯。

初始化新隊列節點的 next 指針為 NULL，表示其后沒有其他節點。

判斷隊列是否為空（即尾指針 rear 是否為 NULL），若是空隊列，則將新節點同時作為隊頭和隊尾。

若隊列不為空，則將原隊尾節點的 next 指針指向新節點，并更新隊尾指針為新節點。?

作用：將一個二叉樹節點插入到隊列中。

4.隊列的出隊操作dequeue

dequeue 函數
參數：Queue* q，指向隊列的指針。

作用：從隊列中移除并返回隊頭的二叉樹節點。

檢查隊列是否為空，若為空則返回 NULL，表示沒有節點可以出隊。

將隊頭節點保存到臨時指針 temp 中，以便后續釋放內存。

獲取隊頭節點所關聯的二叉樹節點，并保存到 treeNode 中，這是要返回的結果。

將隊頭指針移動到下一個節點，實現隊頭的前進。

檢查隊列是否變為空，若變為空則將隊尾指針也設置為 NULL。

釋放之前保存的隊頭節點所占用的內存，避免內存泄漏。

返回出隊的二叉樹節點。

5.判斷隊列是否為空函數isEmpty

isEmpty 函數
參數：Queue* q，指向隊列的指針。
返回值：如果隊列為空，返回非零值（真）；否則返回 0（假）。
實現：通過檢查隊列的 front 指針是否為 NULL 來判斷隊列是否為空。在隊列的鏈式存儲結構中，當 front 指針為 NULL 時，表示隊列中沒有任何節點，即隊列為空。

作用：判斷隊列是否為空。

6.釋放隊列函數freeQueue

freeQueue 函數
參數：Queue* q，指向要釋放的隊列的指針。

作用：釋放隊列及其包含的所有節點所占用的內存。

while (!isEmpty(q))：使用一個循環，只要隊列不為空就持續執行。
在循環體內調用出隊dequeue(q) 函數，不斷移除隊列中的節點并釋放每個節點的內存。
這個過程會一直持續到隊列被完全清空為止。
free(q)：在隊列為空后，釋放隊列本身的內存空間。

?7.創建中序線索二叉樹createInThreadedTree

createInThreadedTree 函數
作用：對整個二叉樹進行中序線索化。
參數：Node* root，指向二叉樹的根節點。

①創建一個指針變量 pre，初始化為 NULL。這個變量將用于記錄中序遍歷過程中的前一個節點。

②調用中序線索化函數 inThreading，從根節點開始對整個二叉樹進行中序線索化，并傳入 pre 的地址，以便在遞歸過程中能夠記錄和更新前驅節點

8.二叉樹節點創建createNode

createNode 函數
作用：創建一個新的二叉樹節點。
參數：int data，表示要存儲在新節點中的數據值。
返回值：返回指向新創建的二叉樹節點的指針。如果內存分配失敗，則返回 NULL。

①使用 malloc 函數動態分配內存，為新的二叉樹節點分配足夠的空間。sizeof(Node) 計算出 Node 結構體的大小。

②檢查內存分配是否成功。如果 newNode 為 NULL，表示內存分配失敗，程序調用 exit(1) 終止執行。

③將傳入的 data 值賦給新節點的 data 成員。

④初始化新節點的左右孩子指針為 NULL，表示該節點目前沒有子節點。

⑤初始化新節點的左右標簽為 0，表示左右指針目前指向的是實際的子節點（盡管此時子節點還未創建）。

⑥返回指向新創建節點的指針。

9.中序線索化操作inThreading

inThreading 函數
作用：對二叉樹進行中序線索化。
參數：
Node* root：指向當前要線索化的節點。
Node** pre：指向一個指針變量，該變量保存了中序遍歷過程中上一個訪問的節點。

①如果當前節點為空，直接返回。因為空節點無需線索化。

②遞歸對當前節點的左子樹進行中序線索化。這一步符合中序遍歷的順序，先處理左子樹。

③如果當前節點沒有左孩子，則將當前節點的左指針指向中序遍歷中的前驅節點（即 pre 指向的節點），并將左標簽 ltag 設置為 1，表示這個左指針是線索而不是指向實際的左孩子。

④如果前驅節點存在且前驅節點沒有右孩子，則將前驅節點的右指針指向當前節點，并將前驅節點的右標簽 rtag 設置為 1，表示這個右指針是線索而不是指向實際的右孩子。

⑤更新 pre 指針，使其指向當前節點，表示當前節點已經成為下一個節點的前驅。

⑥遞歸對當前節點的右子樹進行中序線索化。這一步符合中序遍歷的順序，在處理完左子樹和當前節點后，最后處理右子樹。

10.查找前驅和后繼節點操作findPredecessor&findSuccessor

findPredecessor 函數
作用：找到指定節點在中序遍歷下的前驅節點。
參數：Node* node，指向要查找前驅的節點。

返回值：返回指向中序前驅節點的指針。如果沒有前驅，則返回 NULL。

findSuccessor 函數
作用：找到指定節點在中序遍歷下的后繼節點。
參數：Node* node，指向要查找后繼的節點。
返回值：返回指向中序后繼節點的指針。如果沒有后繼，則返回 NULL。

findPre：

①如果節點的左標簽為1，說明其左指針是指向前驅的線索，直接返回該左指針。

②如果左標簽不是1，則從該節點的左孩子開始查找。

③沿著左孩子的右子樹一直向下尋找，直到找到一個右標簽為1的節點或者無法繼續。

④返回找到的前驅節點。

findSuc：

①如果節點的右標簽為1，說明其右指針指向后繼的線索，直接返回該右指針。

②如果右標簽不是1，則從該節點的右孩子開始查找。

③沿著右孩子的左子樹一直向下尋找，直到找到一個左標簽為1的節點或者無法繼續。

④返回找到的后繼節點。

11. 中序遍歷printInOrderSequece

printInOrderSequence 函數
作用：中序遍歷線索二叉樹并打印節點數據。
參數：Node* root，指向二叉樹的根節點。

①如果根節點為空，直接返回，結束函數執行。

②創建一個指針變量 current，初始化為根節點，用于遍歷樹。

③將 current 移動到最左節點。因為線索二叉樹的最左節點是中序遍歷的第一個節點。

④開始主循環，循環條件是 current 不為 NULL。

⑤打印當前節點的數據。

⑥如果當前節點的右標簽為1，說明右指針是指向后繼的線索。

⑦移動 current 到后繼節點。

⑧如果右標簽不是1，說明右指針指向實際的右孩子。

⑨移動 current 到右孩子。

⑩將 current 移動到其右子樹的最左節點，這是為了找到下一個中序遍歷的節點。

12.查詢前驅和后繼節點findNodeByValue

findNodeByValue 函數
作用：在中序線索二叉樹中查找具有指定值的節點。
參數：
Node* root：指向二叉樹的根節點。
int value：要查找的值。
返回值：如果找到具有指定值的節點，返回指向該節點的指針；否則返回 NULL。

①如果根節點為空，直接返回 NULL，因為空樹中不存在任何節點。

②創建一個指針變量 current，初始化為根節點，用于遍歷樹。

③用while循環將 current 移動到樹的最左節點。這一步確保從樹的中序遍歷的起始位置開始查找。

④開始主循環，循環條件是 current 不為 NULL。

⑤檢查當前節點的數據是否等于要查找的值。如果是，直接返回當前節點指針。

⑥如果當前節點的右標簽為1，說明右指針是指向中序后繼的線索。

? ? ?移動 current 到后繼節點。

⑦?如果右標簽不是1，說明右指針指向實際的右孩子。

? ? ?移動 current 到右孩子。

? ? ?將 current 移動到其右子樹的最左節點，以便繼續中序遍歷。

⑧如果循環結束后仍未找到匹配的節點，返回 NULL。

13.安全釋放二叉樹freeTree

freeTree 函數
作用：遞歸釋放二叉樹中所有節點所占用的內存，防止內存泄漏。
參數：Node* root，指向二叉樹的根節點。

①如果根節點為空，直接返回。因為空樹無需釋放內存。

②如果當前節點的左標簽為0，說明左指針指向實際的左孩子節點，遞歸釋放左子樹的內存。

③如果當前節點的右標簽為0，說明右指針指向實際的右孩子節點，遞歸釋放右子樹的內存。?

④釋放當前節點的內存。

14.用戶輸入二叉樹操作bulidTreeFromInput

buildTreeFromInput 函數
作用：根據用戶輸入構建二叉樹。
返回值：返回指向構建好的二叉樹根節點的指針。如果用戶輸入-1，則返回 NULL，表示不構建樹。

①聲明一個整型變量 value，用于存儲用戶輸入的節點值。

? ??提示用戶輸入根節點的值。

②讀取用戶輸入。如果輸入失敗或者用戶輸入-1，則返回 NULL，表示不構建樹。

③創建根節點。

? ?創建一個隊列，用于輔助構建樹。

? ?將根節點入隊。

④當隊列不為空時，循環執行以下操作：

? ??取出隊列中的節點。

? ??提示用戶輸入當前節點左子節點的值。

? ??讀取用戶輸入。

? ??如果輸入的值不是-1，則創建左子節點，并將其入隊。

? ??提示用戶輸入當前節點右子節點的值。

? ??讀取用戶輸入。

? ??如果輸入的值不是-1，則創建右子節點，并將其入隊。

⑤釋放隊列資源。

⑥返回根節點指針。

15.主函數邏輯

1.循環構建和處理二叉樹：使用 while (1) 創建一個無限循環，允許用戶反復構建和處理二叉樹，直到用戶選擇結束程序。

2.打印菜單：通過 printf 輸出菜單信息，提示用戶當前操作是中序線索二叉樹操作。

3.構建二叉樹：

調用 buildTreeFromInput 函數根據用戶輸入構建二叉樹。
如果用戶輸入-1，表示不構建樹，則打印“程序結束。”并退出循環。

4.線索化二叉樹：

調用 createInThreadedTree 函數對構建好的二叉樹進行中序線索化。

5.中序遍歷并打印：

打印提示信息“中序遍歷結果：”。
調用 printInOrderSequence 函數進行中序遍歷并打印結果。

6.查詢節點：

使用嵌套的 while (1) 循環，反復提示用戶輸入要查詢的節點值。
如果用戶輸入-1，退出查詢循環。
調用 findNodeByValue 函數查找指定值的節點。
如果找不到節點，打印提示信息并跳過本次循環。
調用 findPredecessor 和 findSuccessor 函數查找節點的前驅和后繼。
打印前驅和后繼的信息，使用三元運算符處理空節點的情況，使其顯示為“無”。

7.釋放內存：

調用 freeTree 函數釋放二叉樹占用的內存。
打印提示信息，告知用戶內存已釋放，準備新一輪輸入。

8.結束程序

二、完整代碼

#include <stdio.h>
#include <stdlib.h>typedef struct Node 
{int data;struct Node* lchild;struct Node* rchild;int ltag;int rtag;
} Node;// 隊列結構用于層次構建二叉樹
typedef struct QueueNode 
{Node* treeNode;struct QueueNode* next;
} QueueNode;typedef struct Queue
{QueueNode* front;QueueNode* rear;
} Queue;// 隊列操作函數
Queue* createQueue()
{Queue* q = (Queue*)malloc(sizeof(Queue));if (q == NULL){exit(1);}q->front = q->rear = NULL;return q;
}void enqueue(Queue* q, Node* treeNode) 
{QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){return;}newNode->treeNode = treeNode;newNode->next = NULL;if (q->rear == NULL){q->front = q->rear = newNode;}else{q->rear->next = newNode;q->rear = newNode;}
}Node* dequeue(Queue* q)
{if (q->front == NULL) return NULL;QueueNode* temp = q->front;Node* treeNode = temp->treeNode;q->front = q->front->next;if (q->front == NULL)q->rear = NULL;free(temp);return treeNode;
}int isEmpty(Queue* q) 
{return q->front == NULL;
}void freeQueue(Queue* q)
{while (!isEmpty(q)) {dequeue(q);}free(q);
}// 二叉樹節點創建
Node* createNode(int data) 
{Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL){exit(1);}newNode->data = data;newNode->lchild = newNode->rchild = NULL;newNode->ltag = newNode->rtag = 0;return newNode;
}// 中序線索化
void inThreading(Node* root, Node** pre)
{if (!root)return;inThreading(root->lchild, pre);if (!root->lchild) {root->lchild = *pre;root->ltag = 1;}if (*pre && !(*pre)->rchild) {(*pre)->rchild = root;(*pre)->rtag = 1;}*pre = root;inThreading(root->rchild, pre);
}void createInThreadedTree(Node* root) 
{Node* pre = NULL;inThreading(root, &pre);
}// 查找前驅和后繼
Node* findPredecessor(Node* node) 
{if (node->ltag == 1) return node->lchild;Node* p = node->lchild;while (p && p->rtag == 0) p = p->rchild;return p;
}Node* findSuccessor(Node* node) 
{if (node->rtag == 1)return node->rchild;Node* p = node->rchild;while (p && p->ltag == 0) p = p->lchild;return p;
}// 中序遍歷線索二叉樹
void printInOrderSequence(Node* root)
{if (!root) return;Node* current = root;while (current->ltag == 0) current = current->lchild;while (current){printf("%d ", current->data);if (current->rtag == 1) {current = current->rchild;}else {current = current->rchild;while (current && current->ltag == 0) {current = current->lchild;}}}
}// 通過值查找節點
Node* findNodeByValue(Node* root, int value) 
{if (!root)return NULL;Node* current = root;while (current->ltag == 0)current = current->lchild;while (current) {if (current->data == value) return current;if (current->rtag == 1){current = current->rchild;}else {current = current->rchild;while (current && current->ltag == 0) {current = current->lchild;}}}return NULL;
}// 安全釋放二叉樹
void freeTree(Node* root)
{if (!root) return;if (root->ltag == 0)freeTree(root->lchild);if (root->rtag == 0)freeTree(root->rchild);free(root);
}// 用戶輸入構建二叉樹
Node* buildTreeFromInput()
{int value;printf("輸入根節點值（-1結束）: ");if (scanf_s("%d", &value) != 1 || value == -1)return NULL;Node* root = createNode(value);Queue* q = createQueue();enqueue(q, root);while (!isEmpty(q)) {Node* current = dequeue(q);printf("輸入節點%d的左子節點（-1為空）: ", current->data);scanf_s("%d", &value);if (value != -1) {current->lchild = createNode(value);enqueue(q, current->lchild);}printf("輸入節點%d的右子節點（-1為空）: ", current->data);scanf_s("%d", &value);if (value != -1){current->rchild = createNode(value);enqueue(q, current->rchild);}}freeQueue(q);return root;
}int main()
{while (1){printf("\n===== 中序線索二叉樹操作 =====\n");Node* root = buildTreeFromInput();if (!root) {printf("程序結束。\n");break;}createInThreadedTree(root);printf("中序遍歷結果: ");printInOrderSequence(root);printf("\n");int query;while (1){printf("\n輸入要查詢的節點值（-1返回）: ");scanf_s("%d", &query);if (query == -1)break;Node* target = findNodeByValue(root, query);if (!target) {printf("節點%d不存在！\n", query);continue;}Node* pred = findPredecessor(target);Node* succ = findSuccessor(target);printf("前驅: %s\t后繼: %s\n",pred ? itoa(pred->data, (char[]) { 0 }, 10) : "無",succ ? itoa(succ->data, (char[]) { 0 }, 10) : "無");}freeTree(root);printf("內存已釋放，準備新一輪輸入...\n");}return 0;
}

該代碼用c語言實現的——一個完整的中序線索二叉樹工具，支持用戶動態構建、線索化、遍歷和查詢功能，適合教學演示或需要快速查找前驅/后繼節點的場景。數據結構！！！