前言:
相信大家都知道二叉树如何转化成树,但是让你用代码实现,却发现自己无从下手。下面我将用代码实现。
思想:
树用二叉树来存储的话,那么类型是“左儿子,右兄弟”。即二叉树某节点和它的左儿子在树中的关系也是父子关系,而与右儿子在树中的关系是兄弟关系。所以现在要把用二叉树存储的树来转变成真正的树型。
想象一下构建二叉树怎么来实现?一般都是先序、中序、后序二叉树。树也类似,但一般都是先序构建二叉树。二叉树的根节点对应着树的根节点,二叉树的左儿子,左儿子的右儿子,左儿子的右儿子的右儿子…等等是该根节点的儿子们。所以我们就根据此特点来把二叉树转变成树。代码其实很简短,有了这个思想就不难写出代码。
代码:
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{//二叉树的结构
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int n):val(n),left(NULL),right(NULL){}
};
struct Tree{ //树的结构
int val;
vector<Tree*> children;
Tree(int n):val(n),children(vector<Tree*>()){}
};
TreeNode* create(){ //创建二叉树
int n;
cin>>n;
if(n==0) return NULL;
TreeNode* root=new TreeNode(n);
root->left=create();
root->right=create();
return root;
}
void print(TreeNode* root)//把二叉树先序输出
{
if(root==NULL) return ;
cout<<root->val<<"\t";
print(root->left);
print(root->right);
}
void print1(Tree* root)//把树先序输出
{
if(root==NULL) return ;
cout<<root->val<<"\t";
for(int i=0;i<root->children.size();i++){
print1(root->children[i]);
}
}
Tree* converse(TreeNode* root)//把二叉树转换为树
{
if(root==NULL) return NULL;
Tree* t=new Tree(root->val);
vector<Tree*> ve;
TreeNode* p=root->left;
while(p)
{
ve.push_back(converse(p));
p=p->right;
}
t->children=ve;
return t;
}
void del(TreeNode* root) //删除二叉树
{
if(root==NULL) return;
del(root->left);
del(root->right);
delete root;
}
int main()
{
TreeNode* root=NULL;
root=create();
Tree* t=NULL;
t=converse(root);
print(root);
cout<<endl;
print1(t);
return 0;
}
结果显示: