引線二元樹（Threaded Binary Tree）是一種特殊的二元樹變體，通過添加特殊的指針（線索）來優化對二元樹的遍歷操作，特別是中序遍歷。其主要目的是實現中序遍歷的高效執行，並將其時間複雜度降至O(n)，無需使用遞歸或其他輔助數據結構（如堆疊）。
在傳統的二元樹中，每個節點都包含左子節點和右子節點指針。然而，在引線二元樹中，這些指針被重新利用，以指向中序遍歷中的直接前驅或直接後繼節點。具體來說：
引線二元樹的優勢在於它最大限度地利用了二元樹節點中的空閒指針，提供了更方便的節點訪問方式，並降低了中序遍歷的時間複雜度。這種資料結構的應用包括樹的搜索、排序算法以及需要中序遍歷的任何場景。
中序遍歷效率高： 引線二元樹最大的優點是在中序遍歷時能夠實現高效的遍歷操作，時間複雜度為O(n)。這是因為它使用了線索（引線）來直接訪問節點的前驅和後繼，無需使用遞歸或額外的數據結構（如堆疊），從而減少了遍歷過程的複雜性。
節點訪問方便： 引線二元樹的線索使得在特定情況下訪問節點變得非常方便，特別是在需要查找節點的前驅或後繼時。
節點操作高效： 插入和刪除節點操作相對高效。特別是在刪除操作中，如果節點具有前驅或後繼，則可以輕鬆替換它們，而不需要重建整個樹。
佔用空間多： 引線二元樹需要額外的線索指針來存儲前驅和後繼信息，這將增加樹的內存消耗。如果樹很大，這可能會占用大量內存。
初始構建複雜： 創建引線二元樹需要特別的插入操作，以確保線索的正確設置。這可能使樹的初始構建過程變得複雜，並且容易出現錯誤。
不適用於所有情況： 引線二元樹主要用於中序遍歷的優化，對於其他類型的遍歷（如前序或後序）可能不如普通二元樹適用。因此，如果應用需要不同類型的遍歷，則引線二元樹可能不是最佳選擇。
總的來說，引線二元樹是一個特殊的數據結構，對於某些特定的應用場景非常有用，特別是需要高效中序遍歷的情況。然而，在其他情況下，它可能不是最佳選擇，因為插入和刪除操作相對複雜。選擇是否使用引線二元樹應該根據具體應用的需求和性能要求來決定。
引線二元樹（Threaded Binary Tree）的基本操作包括插入節點、中序遍歷、查找節點和刪除節點等。
struct Node{
int data;
Node *left,*right;
bool leftThread,rightThread;
}
插入節點的基本思想是在二元樹中找到適當的位置插入新節點，然後，需要調整前驅和後繼線索，以確保引線二元樹的性質。
void insert(int data){
if(root == NULL){
root = new Node(data);
root->left = root->right = root;
root->leftThread = root->rightThread = true;
return;
}
Node *temp = root;
while(true){
if(temp->data > data){
if(temp->leftThread == false)
temp = temp->left;
else
break;
}
else{
if(temp->rightThread == false)
temp = temp->right;
else
break;
}
}
Node *newNode = new Node(data);
if(temp->data > data){
newNode->left = temp->left;
newNode->right = temp;
temp->leftThread = false;
temp->left = newNode;
}
else{
newNode->left = temp;
newNode->right = temp->right;
temp->rightThread = false;
temp->right = newNode;
}
}
中序遍歷一個引線二元樹，你可以從根節點開始，按照指針遍歷節點。
void inOrderTraversal(Node *root) {
if (root == NULL)
return;
Node *current = leftMost(root);
while (current != NULL) {
cout << current->data << " ";
if (current->rightThread)
current = current->right;
else
current = leftMost(current->right);
}
}
Node* leftMost(Node* node) {
while (node != NULL && !node->leftThread)
node = node->left;
return node;
}
刪除操作在引線二元樹中需要處理三種主要情況：
刪除葉節點：如果要刪除的節點是葉子節點，只需調整其父節點的左線程或右線程。如果葉子節點是父節點的左子節點，則將父節點的左線程指向該節點的左線程孩子，同時將父節點的 leftThread 設定為 false，表示父節點指向某個有序前驅。類似地，如果要刪除右側的子節點，則將父節點的右線程指向子節點的右線程，並將 rightThread 設定為 false。
只有一個子節點的情況：如果要刪除的節點只有一個子節點，需要調整相應的線索，使前驅或後繼節點指向正確的位置。具體來說，如果要刪除的節點有左子節點，則刪除後，其前驅節點的右線程應該指向其後繼節點。如果要刪除的節點有右子節點，則刪除後，其後繼節點的左線程應該指向其前驅節點。
有兩個子節點的情況：如果要刪除的節點有兩個子節點，需要找到其中序遍歷下的前驅或後繼節點，將其用來替換要刪除的節點，然後刪除前驅或後繼節點。這樣可以保持二元樹的性質。
Node *predecessor(Node *node){ // 前驅
if(node->leftThread)
return node->left;
Node *temp = node->left;
while(temp->rightThread == false)
temp = temp->right;
return temp;
}
Node *successor(Node *node){ // 後繼
if(node->rightThread)
return node->right;
Node *temp = node->right;
while(temp->leftThread == false)
temp = temp->left;
return temp;
}
Node* deleteNode(Node* root, int key) {
if(root == NULL)
return NULL;
// 查找要刪除的節點
Node *cur = root;
Node *parent = NULL;
while(cur != NULL && cur->data != key){
parent = cur;
if(cur->data > key)
cur = cur->left;
else
cur = cur->right;
}
if(cur == NULL)
return root;
// 刪除節點
Node* p = predecessor(cur); // 前驅
Node* s = successor(cur); // 後繼
Node * child = NULL;
// 1. 節點為葉子節點
if(cur->leftThread && cur->rightThread){
cout << "delete leaf node" << endl;
// 刪除根節點
if(parent == NULL){
delete cur;
return NULL;
}
// 刪除左子樹的葉子節點
if(parent->left == cur){
// parent thread to cur->right
parent->left = cur->left;
parent->leftThread = true;
}
// 刪除右子樹的葉子節點
else{
parent->right = cur->right;
parent->rightThread = true;
}
delete cur;
}
// 2.有一個子節點
else if (cur->leftThread || cur->rightThread ||(!cur->leftThread && cur->rightThread)){
// 刪除根節點
if(parent == NULL){
if(cur->leftThread){
root = cur->right;
cur->right->left = cur->left;
}
else{
root = cur->left;
cur->left->right = cur->right;
}
delete cur;
return root;
}
child = cur->leftThread ? cur->right : cur->left;
// 刪除左子樹的節點
if(parent->left == cur)
parent->left = child;
else
parent->right = child;
// 更新前驅或後繼
if(cur->leftThread)// 有右子樹
s->left = cur->left;
else // 有左子樹
p->right = cur->right;
delete cur;
}
// 3.有兩個子節點 (找前驅或後繼)
else{
// 找前驅取代
Node *temp = predecessor(cur);
int val = temp->data;
deleteNode(root, temp->data);
cur->data = val;
}
return root;
}
引線二元樹是一個強大的數據結構，通過適當的操作可以實現高效的中序遍歷和其他二元樹相關的操作。它的主要優勢在於減少了中序遍歷的時間複雜度，並簡化了遍歷過程，使之更加高效。
生活中的每一刻都是獨一無二的，每分每秒都值得我們用心感受、用於有意義的事情。
iThome鐵人賽
看影片追技術