Is there a way to convert from a general tree to binary SEARCH tree?

Question

I know how to convert from a general tree to a binary tree just fine,

      a             a
    / | \          /
   b  c  d   ->   b
                   \
                    c
                     \
                      d

I was just asked how to convert from a general tree to a binary search tree though. My thoughts are that the person who asked me either didn't mean binary search tree (I asked him, he said he did), or he's misunderstanding something from his class notes. In any case, has anyone heard of doing this? General tree to binary search tree? The answer I gave him was first convert to a binary tree then sort it to get a binary search tree. Is this correct?

Answer 1

You can follow the given step for conversion:

For every node N make it's left child as left child and its right sibling as right child

By this the root child of the tree will not have right sub-tree as it does not have any right sibling. For example: The general tree for conversion

By following the steps you will get: Resultant Binary tree

Answer 2

**

This is an algorithm I created that can convert a tree data structure into a 2 degree tree true (Binary tree). Following is the node structure for the tree nodes.

**

template<class T>
class Node
{
public:
  T _data;    // The Node Data

  std::vector<Node<T>*> _link;   // Possible OutLinks from the Node.

  Node(){}

  void setValue(T D){ _data = D; }

  T getValue()const{ return _data; }

  ~Node(){}
};

Following is the tree adapter.

template <class T> 

class tree{

  Node<T>*_root;  // The Pointer holding the root node.

  int _degree;

  std::string _type; // shows the tree type,Binary Or Any other outdegree 

//degrees.

public:

  tree(){ _degree = 0; _root = NULL; }

  tree(Node<T>*R, int D) :_root(R),_degree(D){}


 Node<T>* getRoot()const{ return _root; }

 ~tree(){ _root = NULL; }
};

//.........
//This is the Algorithm for converting a x-order tree to a binary tree.

///*This Template function is used to convert a general tree into a binary tree  

without loosing any nodes,with the same root node.*/

template<class T> 

tree<T> makeBinaryTree(tree<T> _tree){

  Node<T>* node = _tree.getRoot();

  Node<T>* root = new Node<T>;

  root = node;


  int i = 0;

  int k = 0;

  std::queue<Node<T>*> que;  // que used to save the links other than the 

leftmost one.

  std::stack<Node<T>*> s1;   // stack for saving the tree nodes,while going deep 
into left

  std::stack<char>s2;

  Node<T>* s3;

  char flag = ' ';

  while (true){

    while (root&&flag!='A'){

      s1.push(root);

      if (root->_link[0] == NULL && root->_link.size())

        s2.push('C');

      else if (root->_link.size() > 1){

        s2.push('B');

      }

      else

        s2.push('A');

      root = root->_link[0];

    }

    if (s1.empty())break;

    root = s1.pop();

    flag = s2.pop();


    if (flag == 'C'){  // handles the deep left node with any number of nodes 

other than in socket 0.

      while (true){

        i = 1;

        if (root->_link[0] == NULL&&root->_link.size() == 0){ flag = 'A'; break; 

}
        if (root->_link.size() >= 1){

          while (true)

          {

            if (root->_link[i]){

              root->_link[0] = root->_link[i];

              root->_link.erase(i);

              if (root->_link.size() > 1){

                s1.push(root);

                s2.push('B');

              }

              break;

            }

            ++i;

          }

          root = root->_link[0];

        }

      }

    }


    if (flag == 'B'){ // any node except the deep left node that has more links 

from it.

      i = root->_link.size()-1;

      k = i-1;

      while (K!=0){

        root->_link.at(k)->_link.push(root->_link.at(k + 1));

        --k;

      }

      s3->_link[1] = root->_link[1];

      root->_link.erase[1];

    s1.push(root);

    s2.push('A');
      // Now You have to manage link 1 of s3.

      s3 = s3->_link[1];



      if (s3->_link.size()){

        //TODO...

        //Testing...

        root = s3;

      }

      //AT the end 

      s3 = NULL;



    }





    if (flag == 'A'){   // the safe nodes,i.e having only one node from it 

,other than the deep left node

      s3 = root;

    }



  }//end of main while loop.

return (new tree<T>(node,2));

}

Answer 3

I think you just have to traverse the initial tree and insert each node into a binary search tree. After that, you will have converted your initial tree into a BST.

For traversing the tree click here

For binary search tree info and insertion method click here