将二叉树转换为双线程二叉树？

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); 
}