Преобразование двоичного дерева в двоичное дерево с двумя нитями?

Question

Я не смог найти ничего в поиске, чтобы удовлетворить мой вопрос, если он существует, извините!

Я работаю над заданием в колледже о двоичных деревьях с резьбой. То есть различные виды обхода - порядок, порядок и порядок двойного TBT.

Это структура 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;
}

После того, как дерево было рекурсивно создано с использованием приведенного выше кода, я хочу преобразовать его в двухпоточное двоичное дерево. Я знаю, что понятие «оставленный ребенок» связано с предшественником inorder ребенка и правом наследника inorder, но я не могу создать алгоритм. Может ли кто-нибудь мне помочь?

Answer 1

Я нашел решение сам. Сначала пройдитесь по дереву в порядке и добавьте узлы в массив по мере продвижения. Затем обработайте массив, чтобы связать потоки, потому что для данного элемента x в массиве, предшествующий x будет предшественником по порядку, а один после x будет наследником по порядку. Для первого и последнего элемента выполняются специальные проверки, чтобы связать их с головным узлом (не корневым).

Родительская ссылка не нужна, и она удалена.

Код выглядит следующим образом:

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