一.多叉树的定义• 多叉树本质上就是二叉树的延申二叉树是特殊的多叉树二叉树每一个节点都有两个子节点那么 “多叉树” 每一个节点都有任意的子节点用代码表示就是二叉树节点class TreeNode{ public: int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x) , left(nullptr) , right(nullptr){} };多叉树节点任意的子节点-----用数组class TreeNode{ public: int val; vectorTreeNode* children; };二叉树相关知识二叉树---从零开始的数据结构学习-CSDN博客二叉树遍历----从零开始的数据结构-CSDN博客补充森林的定义森林就是多叉树的集合单独一颗多叉树是特殊的森林。代码表示 用list列表listNode forest;每一个node都是一个多叉树的根节点利用bfs和dfs从头节点遍历下去是不是很像哈希表的遍历二.多叉树遍历1.递归遍历DFSclass TreeNode{ public: int val; vectorTreeNode* children; }; void traverse(TreeNode* root){ if (root nullptr) return; //前序 for (TreeNode* child : root-children){ traverse(child); } //后序 }前序在递归函数前面后序在递归函数后没有中序位置是因为可能会大于2因此讨论中序没有意义多叉树每一个节点的子节点在数组中刚好从左往右排列2.层序遍历(BFS):多叉树的层序遍历和二叉树的层序遍历相同。写法一最简单不记录深度#includeiostream #includevector #includequeue using namespace std; class TreeNode{ public: int val; vectorTreeNode* children; }; void levelOrderTraverse(TreeNode* root){ if (root nullptr) return; queueTreeNode* q; q.push(root); while(!q.empty()){ TreeNode* cur q.front(); q.pop(); cout cur-val endl; for (TreeNode* temp : cur-children){ q.push(temp); } } }写法二 常规记录深度#includeiostream #includevector #includequeue using namespace std; class TreeNode{ public: int val; vectorTreeNode* children; }; void levelOrderTraverse(TreeNode* root){ if (root nullptr)return; int depth 1;//深度 queueTreeNode* q; q.push(root); while(!q.empty()){ int size q.size(); for (int i 0; i size; i){ TreeNode* cur q.front(); q.pop(); for (TreeNode* temp : cur-children){ q.push(temp); } } depth; } }每一层在队列中的元素出队之后depth加一写法三 使用于不同路径权重的情况#includeiostream #includevector #includequeue using namespace std; class TreeNode{ public: int val; vectorTreeNode* children; }; class state{ public: TreeNode* Node; int depth;//路径 state(TreeNode* node, int depth) :Node(node) , depth(depth){} }; void levelOrderTraverse(TreeNode* root){ if (root nullptr) return; queuestate q; q.push(state(root,1)); //根节点深度当作1 while(!q.empty()){ state cur q.front(); q.pop(); int depth cur.depth; for (TreeNode* temp : cur.Node-children){ q.push(state(temp,depth1)); } } }每一个层路径节点默认比上一层多一在不同情景中进行更改即可。结语如果喜欢我的文章不妨点一个免费的赞和收藏。你们的支持都是我更新路上最大的动力