一、多叉树的介绍

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

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

其他的名词解释

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

二、多叉树 的先序遍历

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

递归的写法

struct Node {char data;vector 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 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 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> levelOrder(Node* root) {//特判if(root == nullptr) return {};vector> res;queue qu;qu.push(root);while(!qu.empty()){vector 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 children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector _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博客_多叉树的遍历算法

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