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

多叉树定义与遍历-----从零开始的数据结构

news 2026/4/27 12:49:21

一.多叉树的定义：

• 多叉树本质上就是二叉树的延申，二叉树是特殊的多叉树

二叉树每一个节点都有两个子节点，那么 “多叉树” 每一个节点都有任意的子节点

用代码表示就是：

二叉树节点：

class TreeNode{ public: int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x) , left(nullptr) , right(nullptr){} };

多叉树节点：任意的子节点-----用数组！

class TreeNode{ public: int val; vector<TreeNode*> children; };

二叉树相关知识：

二叉树---从零开始的数据结构学习-CSDN博客

二叉树遍历----从零开始的数据结构-CSDN博客

补充：森林的定义

森林就是多叉树的集合，单独一颗多叉树是特殊的森林。

代码表示：用list列表

list<Node> forest;

每一个node都是一个多叉树的根节点

利用bfs和dfs从头节点遍历下去，是不是很像哈希表的遍历？

二.多叉树遍历

1.递归遍历（DFS）：

class TreeNode{ public: int val; vector<TreeNode*> children; }; void traverse(TreeNode* root){ if (root == nullptr) return; //前序 for (TreeNode* child : root->children){ traverse(child); } //后序 }

前序在递归函数前面，后序在递归函数后

没有中序位置是因为可能会大于2，因此讨论中序没有意义

多叉树每一个节点的子节点在数组中刚好从左往右排列

2.层序遍历(BFS):

多叉树的层序遍历和二叉树的层序遍历相同。

写法一：最简单，不记录深度

#include<iostream> #include<vector> #include<queue> using namespace std; class TreeNode{ public: int val; vector<TreeNode*> children; }; void levelOrderTraverse(TreeNode* root){ if (root == nullptr) return; queue<TreeNode*> 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); } } }

写法二：常规，记录深度

#include<iostream> #include<vector> #include<queue> using namespace std; class TreeNode{ public: int val; vector<TreeNode*> children; }; void levelOrderTraverse(TreeNode* root){ if (root == nullptr)return; int depth = 1;//深度 queue<TreeNode* > 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加一

写法三：使用于不同路径权重的情况

#include<iostream> #include<vector> #include<queue> using namespace std; class TreeNode{ public: int val; vector<TreeNode*> 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; queue<state> 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,depth+1)); } } }

每一个层路径节点默认比上一层多一，在不同情景中进行更改即可。