我知道如何從一個普通的樹轉換爲二進制樹就好了，有沒有辦法將普通樹轉換爲二元搜索樹？
a a
/| \ /
b c d -> b
\
c
\
d
我只是問如何從一個普通的樹，雖然轉換爲二進制搜索樹。我的想法是，問我的人或者不是指二叉搜索樹（我問他，他說他是），或者他誤解他的課堂筆記中的某些東西。無論如何，有沒有人聽說過這樣做？一般樹到二叉搜索樹？我給他的答案是首先轉換爲二叉樹，然後對其進行排序以獲得二叉搜索樹。它是否正確？
我想你只需要traverse這個初始樹並將每個節點插入一個binary search tree。之後，您將會將您的初始樹轉換爲BST。
對於遍歷樹click here
對於二進制搜索樹信息和插入方法click here
**
這是一個算法我創建能夠在樹數據結構 轉換成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));
}
您可以按照轉換的給定步驟：
對於每一個節點N使得它留給孩子的左孩子和其右兄弟爲右孩子
由此樹的根子將不會有正確的子樹，因爲它沒有任何右siblin G。例如： The general tree for conversion
通過以下步驟，您將獲得： Resultant Binary tree
哎呀，我甚至沒有想到這一點。謝謝。我的思想被困在某種移動的東西上而不是迭代。 –