How Do I Convert a Binary Tree to a Double Threaded Binary Tree?

Question

[jessewhite8077]

So I really can not find anything on search to solve my query; if it exists, I apologise!

I'm working on a college project involving threaded binary trees. In other words, several types of traversals - inorder, postorder, and preorder on double TBT.

The TBTNode struct is as follows:

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

You'll notice that the only difference between a Binary Tree node and a TBT node is that the node's attributes, namely left,right normal, are set to true when needed.

I have the following to make the tree:

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

Following recursively creating the tree with the preceding code, I want to convert it to a double threaded binary tree. I understand that the left child is linked to the kid's inorder predecessor and the right child to the child's inorder successor, but I am unable to design an algorithm. Can somebody assist me?

[Pierre Lindenbaum]

it's unrelated to bionformatics , ask https://stackoverflow.com

[jessewhite8077]

okay thanks for telling me.