m叉树转2叉树代码实现(红棉小冰一面)

101 阅读 0 评论 67 点赞

我是靠谱客的博主震动大树，最近开发中收集的这篇文章主要介绍m叉树转2叉树代码实现(红棉小冰一面)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个数据结构有讲到,如果一点都不懂可以看看数据结构的树那一章

代码如下,思路见代码

#include<bits/stdc++.h>
using namespace std;
struct mTreeNode{
mTreeNode():val(0){}
int val;
//保存m叉树的m个儿子
vector<mTreeNode * > son;
};
// 每个二叉树结点的意义
struct treeNode{
treeNode():val(0),bro(nullptr),son(nullptr){}
int val;
treeNode * son;//该结点的儿子（长子）结点
treeNode * bro;//该结点兄弟结点
};
// m叉树转2叉树
/*
如何将m叉树转换为 2叉树
如果把考虑的重点放在边遍历m叉树边构造二叉树，这样很难处理二叉树当前结点点对子结点，或者兄弟结点的指向问题
所以这边要把问题的中心放在2叉树的构建上，考虑递归构建二叉树，递归的把左右子树构建好后返回左右子树的根结点给父节点
具体转换思路可以自己画一个2层的3叉树，用上面方法试着转换成2叉树
*/
/* 参数 当前的m叉树结点、
指向当前的m叉树节点的父节点(用来帮助构建二叉树结点的兄弟结点)、
要构建的兄弟结点在vector<mTreeNode>中的下标
*/
treeNode * func(mTreeNode * mRoot,mTreeNode * pRoot,int index){
if(!mRoot)
return nullptr;
treeNode * temp = new treeNode();
temp->val = mRoot->val;
auto sonArr = mRoot->son;
//cout << mRoot->val << 't';
int sz = sonArr.size();
if(sz)
{
//cout << mRoot->val << "lt" ;
temp->son = func(sonArr[0],mRoot,1);
}
if(pRoot)
{
// cout << "index " << index << endl;
//cout << mRoot->val <<"rt" ;
temp->bro = (index + 1 > pRoot->son.size() ? nullptr : func(pRoot->son[index],pRoot,index + 1));
}
return temp;
}
// 层序输出二叉树（由m叉树转换产生的）
void checkTreeNode(treeNode * root){
queue<treeNode * > q,p,p1;
q.push(root);
while(q.size()){
treeNode * temp = q.front(); q.pop();
cout << temp->val << 't';
if(temp->son)
p.push(temp->son);
if(temp->bro)
p.push(temp->bro);
if(!q.size())
{
q = p;
p = p1;
cout << 'n';
}
}
}
// 层序输出m叉树
void checkmTree(mTreeNode * root){
queue<mTreeNode * > q,p,p1;
q.push(root);
while(q.size()){
mTreeNode * temp = q.front(); q.pop();
cout << temp->val << 't';
for(auto it : temp->son)
{
p.push(it);
}
if(!q.size())
{
q = p;
p = p1;
cout << 'n';
}
}
}
// 构建高度为n的满m叉树
mTreeNode * createmNode(int n,int m){
if(!n)
return nullptr;
mTreeNode * root = new mTreeNode();
root->val = rand() % 50;
if(n > 1)
for(int i = 1; i <= m; ++i){
mTreeNode * temp = createmNode(n - 1,m);
root->son.push_back(temp);
}
return root;
}
int main(){
/* 输入层数和儿子个数 */
int n,m;
cin >> n >> m;
/* 构建高度为n的满m叉树 */
mTreeNode * mRoot = createmNode(n,m);
/* 打印构建出的m叉树 */
checkmTree(mRoot);
/* 根据m叉树转换出二叉树 */
treeNode * root = func(mRoot,nullptr,0);
/* 打印转换出来的二叉树 */
checkTreeNode(root);
return 0;
}