当前位置：首页 > article >正文

多叉树笔记

article 2024/11/15 2:11:37

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;
}