多叉树笔记

1 多叉树定义

多叉树是一种树形结构，它有一个特定的节点被称为“根”节点，而每个节点（除了根节点）恰好有一个前驱节点（父节点）。在有根多叉树中，每个节点可以拥有任意数量的后继节点（子节点）。

struct MultiTree{int val;vector<MultiTree*> children;MultiTree(int v):val(v){}
};

2 多叉树的构造

利用vector<int>parents记录每个节点的父节点
利用vector<MultiTree*>记录读入的每个节点（利用值先创建）
然后用关系 (multi[parents[i]-1]->children).push_back(multi[i]) 把每个节点连接起来。

void BuildMultiTree(vector<MultiTree*>& multi,vector<int> parents,int n){for(int i=1;i<n;i++){(multi[parents[i]-1]->children).push_back(multi[i]);}
}

3 逐层历遍打印多叉树

用队列辅助

void print_Multi(MultiTree* root){queue<MultiTree*> q;q.push(root);while(!q.empty()){MultiTree* temp=q.front();q.pop();//cout<<temp->val<<" ";for(int i=0;i<int(temp->children.size());i++){q.push(temp->children[i]);}}
}

4 多叉树到LC-RS二叉树的转变

LC-RS二叉树：左儿子右兄弟。以这种方式重排多叉树为二叉树。
ps.每个节点的左儿子一定使用它的所有儿子中的编号最小的，右兄弟一定使用比它编号大的兄弟中最小的兄弟的编号。

逻辑：
①先搞定根节点：LC-RS的根节点的值永远等于多叉树根节点的值
②左侧递归：左子树为 以多叉树根节点的第一个孩子为根节点的树
③右侧递归：右子树为空，左子树的右子树是 以多叉树根节点的下一个孩子为根节点的树
````````````````````````左子树的右子树的右子树是 以多叉树根节点的再下一个孩子为根节点的树
````直到多叉树的根节点的孩子节点全部安排好。

BiTree* Multi2Bi(MultiTree* root){if(!root) return NULL;BiTree* r=new BiTree(root->val);if(!root->children.empty()){r->lchild=Multi2Bi(root->children[0]);    //左递归BiTree* cur = r->lchild;for(int i=1;i<int(root->children.size());i++){cur->rchild=Multi2Bi(root->children[i]);cur=cur->rchild;                       //右递归}}return r;
}