Converting a Binary Tree to Double Threaded Binary Tree?

Question

I could not find anything on search to satisfy my question, if it exists, I'm sorry!

I am working on a college assignment about threaded binary trees. I.e. various kinds of traversals - inorder, postorder and preorder on double TBT.

This is the TBTNode struct:

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

As you can see, there is not much distinction between a Binary Tree node and a TBT node, except that the node's properties, viz. {left,right}_normal are set to true when required.

To create the tree, I have this:

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

After the tree gets recursively created using the above code, I want to convert it into a double threaded binary tree. I know the concept that left child is linked to the child's inorder predecessor and right to inorder successor, but I am unable to create an algorithm. Can someone help me?

Nilesh Nilesh · Accepted Answer · 2012-02-09T09:04:01

I found the solution myself. First traverse the tree in inorder and add nodes to an array as you go on. Then process the array to link threads, because for a given element x in the array, the one previous to x will be inorder predecessor and one after x will be inorder successor. For the first and last element, special checks are made to link them to the head node (not root).

Parent link isn't needed, and it's removed.

Code is as follows:

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

Converting a Binary Tree to Double Threaded Binary Tree?

1 Answers