將二叉樹轉換爲雙線程二叉樹？

Question

我找不到任何關於搜索的內容來滿足我的問題，如果它存在，我很抱歉！

我正在進行關於線程二叉樹的高校作業。即各種各樣的遍歷 - 雙重技術性貿易壁壘中的訂單，後序和預訂。

這是TBTNode結構：

struct TBTNode { 
    TBTNode *left, *right, *parent;  
    char data; 
    bool left_normal, right_normal; 
    TBTNode(char d) { 
    data = d; 
    left = NULL; 
    right = NULL; 
    parent = NULL; 
    left_normal = true; 
    right_normal = true; 
    } 
}; 

正如你所看到的，沒有一個二叉樹節點和節點TBT太大區別，不同之處在於節點的屬性，即{left，right} _normal在需要時設置爲true。

要創建樹，我有這樣的：樹被使用上面的代碼創建遞歸

class TBT { 
    TBTNode *root; 
public: 
    TBT() { 
    root = new TBTNode(0); 
    root->right = root; 
    root->right_normal = true;   
    cout << "Root:" ;   
    root->left = create(); 
    if(root->left) 
     root->left_normal = true; 
    } 
    TBTNode* create(); 
}; 

TBTNode* TBT::create() { 
    char data; 
    TBTNode *node = NULL; 
    cout << endl << "Enter data (0 to quit): "; 
    cin >> data; 
    if(data == '0') 
    return NULL; 
    node = new TBTNode(data); 
    cout << endl << "Enter left child of " << data; 
    node->left = create(); 
    if(node->left) 
    node->left->parent = node; 
    else { 
    node->left = root; 
    node->right = node->parent; 
    node->left_normal = node->right_normal = false; 
    } 
    cout << endl << "Enter right child of " << data; 
    node->right = create(); 
    if(node->right) 
    node->right->parent = node; 
    else { 
    node->left = node; 
    node->right = node->parent->parent; 
    node->left_normal = node->right_normal = false; 
    } 
    return node; 
} 

後，我想將其轉換爲雙螺紋二叉樹。我知道離開孩子的概念與孩子的前任和後繼者的權利有關，但我無法創建算法。有人能幫我嗎？

Answer 1

我自己找到了解決方案。首先在inorder中遍歷樹，並在繼續時將節點添加到數組中。然後處理數組以鏈接線程，因爲對於數組中的給定元素x，x之前的那個將是inorder的前者，而x之後的將是inorder的後繼者。對於第一個和最後一個元素，會進行特殊檢查，將它們鏈接到頭節點（而不是根節點）。

父鏈接不需要，它被刪除。

代碼如下：

class TBT { 
    TBTNode *root; 
    void createInorderArray(TBTNode *T); 
    TBTNode **array; 
    unsigned array_size; 
public: 
    TBT(); 
    TBTNode* create(); 
    void inorder(); 
    void preorder(); 
}; 

TBT::TBT() { 
    root = new TBTNode(0); 
    root->right = root; 
    root->right_normal = true; 
    cout << "Root:" ; 
    root->left = create();  
    if(!root->left) { 
    root->left_normal = false; 
    root->left = root; 
    } 
    array = NULL; 
    array_size = 0; 
    createInorderArray(root->left); 
    for(unsigned i = 0; i < array_size; i++) { 
    if(!array[i]->left) { 
     array[i]->left = i == 0 ? root : array[i-1]; 
     array[i]->left_normal = false; 
    } 
    if(!array[i]->right) { 
     array[i]->right_normal = false; 
     array[i]->right = i == (array_size - 1) ? root : array[i+1]; 
    } 
    } 
    free(array); 
    array_size = 0; 
} 

void TBT::createInorderArray(TBTNode *T) { 
    if(!T) 
    return; 
    createInorderArray(T->left); 
    array = (TBTNode**) realloc(array, sizeof(TBTNode**) * ++array_size); 
    array[array_size-1] = T; 
    createInorderArray(T->right); 
}