StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POConverting a Binary Tree to Double Threaded Binary Tree?
text
Body
copied!<p>I could not find anything on search to satisfy my question, if it exists, I'm sorry!</p> <p>I am working on a college assignment about threaded binary trees. I.e. various kinds of traversals - inorder, postorder and preorder on double TBT.</p> <p>This is the TBTNode struct:</p> <pre><code>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; } }; </code></pre> <p>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.</p> <p>To create the tree, I have this:</p> <pre><code>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; } </code></pre> <p>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?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload