我知道如何从一般树转换为二叉树就好了，
a a
/ | \ /
b c d -> b
\
c
\
d
我只是被问到如何从一般树转换为二叉搜索树。我的想法是，问我的人不是指二叉搜索树（我问他，他说他是），或者他从课堂笔记中误解了一些东西。无论如何，有人听说过这样做吗？一般树到二叉搜索树？我给他的答案是先转换成二叉树，然后排序得到二叉搜索树。这个对吗？
**
这是我创建的一种算法，可以将树数据结构转换为 2 度树真（二叉树）。以下是树节点的节点结构。
**
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));
}
