多叉树的使用

ゝ一世哀愁。 2024-04-01 11:08 38阅读 0赞

#### 一、多叉树的介绍 ####

**多叉树**：多叉树，顾名思义，就是一个节点可能有若干个子节点，构造的一个较为复杂的树结构。

class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };

![a0f99b2697334cae8294f11200681562.png][]

其他的名词解释

边：从父节点到子节点的连线（边有方向）  
兄弟节点：父节点相同的节点，互为兄弟节点  
树叶、分支节点：没有子节点的节点称为树叶，树中的其余节点称为分支节点（分支节点可只有一个分支）  
祖先和子孙：基于父节点/子节点关系和传递性，可以确定相应的传递关系，称为祖先关系或子孙关系  
度数：一个节点的子节点个数，称为该节点的度数  
路径、路径长度：从一个祖先节点到其子孙节点的一系列边称为树中一条路径（从一棵树的根到树中任一个节点都有唯一路径）  
路径中边的条数称为路径的长度，认为每个节点到自身有长0的路径  
节点的层数：树根到节点的路径长度是该节点的层数  
节点都有层数，根所在的层为0  
高度（或深度）：树的高度或深度是树中节点的最大层数（最长路径的长度）加1，空树高度为0，只有根节点的树高度为1

#### 二、多叉树 的先序遍历 ####

先序遍历即是指父节点先于子节点访问

递归的写法

struct Node {
        char data;
        vector<Node*> children;
        Node(char data) :data(data) {}
    };
    
    void Preorder(Node* root) {
        // 先序遍历
        if (nullptr == root) {
            return;
        }
        // 访问当前节点
        cout << root->data << endl;
        // 访问子节点
        for (auto node : root->children) {
            Preorder(node);
        }
    }

非递归

void preorder_stack(Node* root) {
        if (nullptr == root) {
            return;
        }
        stack<Node*> sck;
        sck.push(root);
        while (!sck.empty()) {
            Node* node = sck.top();
            sck.pop();
            cout << node->data << " ";
            for (int i = node->children.size() - 1; i >= 0; i--) {
                sck.push(node->children[i]);
            }
        }
    }

#### 三、后续遍历 ####

访问过程中优先处理子节点

递归的写法

void Postorder(Node* root){
        // 先序遍历
        if(nullptr == root) return;
    
        // 访问子节点
        for(auto node:root->children){
            Postorder(node);
        }
        // 访问当前节点
        cout << root->data << endl;
    }

非递归的写法

void Postorder_stack(Node* root) {
        if (nullptr == root)
        {
            return;
        }
        stack<Node*> sck;
        sck.push(root);
        Node* pre = root;
        while (!sck.empty()) {
            Node* node = sck.top();
            if (node->children.empty() // 叶子结点
                || pre == node->children.back() // 分支节点的叶子节点完>成访问
                ) {
                sck.pop();
                cout << node->data << " ";
            }
            else {
                for (int i = node->children.size() - 1; i >= 0; i--) {
                    sck.push(node->children[i]);
                }
            }
            pre = node;
        }
    }

#### 四、层序遍历 ####

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

class Solution {
    public:
        vector<vector<int>> levelOrder(Node* root) {
            //特判
            if(root == nullptr) return {};
            vector<vector<int>> res;
            queue<Node*> qu;
            qu.push(root);
            while(!qu.empty()){
                vector<int> temp;
                //每一层的个数
                int size = qu.size();
                for(int i = 0; i < size; i++){
                    Node* node = qu.front();
                    temp.push_back(qu.front()->val);
                    //遍历队头的孩子节点，如果不为空，加入队列
                    for (auto node : qu.front()->children) {
                        if (node){
                            qu.push(node);
                        }
                    }
                    qu.pop();
                }
                res.push_back(temp);
            }
            return res;
        }
    };
    /*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };
    */

#### 五、合并多叉树 ####

void MergeTree(Node* target, Node* current) {
    
        if (target->children.empty()) { // 目标树是空树
            for (auto& child : current->children) {
                target->children.push_back(child);
            }
            return;
        }
        for (auto& curChild : current->children)
        {
            bool same = false;
            for (auto& tarChild : target->children)
            {
                if (tarChild->data == curChild->data) {
                    same = true;
                    MergeTree(tarChild, curChild);
                }
            }
            if (!same) {
                target->children.push_back(curChild);
            }
        }
    }

参考：

[多叉树的遍历\_Rqff的博客-CSDN博客\_多叉树的遍历算法][Rqff_-CSDN]

[【数据结构】多叉树的深度优先遍历DFS和广度优先遍历BFS（含C++递归和非递归方式实现）\_大家好，我是好同学的博客-CSDN博客\_多叉树的广度优先遍历][DFS_BFS_C_-CSDN]

[a0f99b2697334cae8294f11200681562.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7f0c2a305c564a3482b3f725447c99f3.png
[Rqff_-CSDN]: https://blog.csdn.net/qq_41342326/article/details/106910292
[DFS_BFS_C_-CSDN]: https://blog.csdn.net/weixin_50941083/article/details/124710978