N叉树的广度优先遍历和深度优先遍历

class Node {

public:

int val;

vector<Node*> children;

};

// N 叉树的非递归层序遍历（广度优先遍历）

void levelOrderTraverse(Node* root) {

if (root == nullptr) {

return;

}

std::queue<Node*> q;

q.push(root);

while (!q.empty()) {

Node* cur = q.front();

q.pop();

// 访问 cur 节点

std::cout << cur->val << std::endl;

// 把 cur 的所有子节点加入队列

for (Node* child : cur->children) {

q.push(child);

}

}

}

// N 叉树的递归先序遍历（深度优先遍历）

void Preorder(Node* root){

// 先序遍历

if(nullptr == root) return;

// 访问当前节点

cout << root->data << endl;

// 访问子节点

for(auto node:root->children){

Preorder(node);

}

}

// N 叉树的非递归先序遍历（深度优先遍历）

void preorder_stack(node* root){

if(nullptr == root) return;

stack<node*> s;

s.push(root);

while(!s.empty()){

node* node = s.top();

s.pop();

cout << node->data << " ";

for(int i=node->children.size()-1; i>=0; i--){

s.push(node->children[i]);

}

}

}

// N 叉树的递归后序遍历（深度优先遍历）

void Postorder(Node* root){

// 先序遍历

if(nullptr == root) return;

// 访问子节点

for(auto node:root->children){

Postorder(node);

}

// 访问当前节点

cout << root->data << endl;

}

// N 叉树的非递归后序遍历（深度优先遍历）

void Postorder_stack(Node* root){

if(nullptr == root) return;

stack<Node*> s;

s.push(root);

Node* pre = root;

while(!s.empty()){

Node* node = s.top();

if(node->children.empty() // 叶子结点

|| pre == node->children.back() // 分支节点的叶子节点完>成访问

){

s.pop();

cout << node->data << " ";

}else{

for(int i=node->children.size()-1; i>=0; i--){

s.push(node->children[i]);

}

}

pre = node;

}

}

// N 叉树的非递归层序遍历（广度优先遍历）

int depth(Node* root) {

if(nullptr == root) return 0;

int maxdepth = 0;

for(auto child : root->children){

maxdepth = max(maxdepth, depth(child));

}

return maxdepth+1;

}

void traverLayer(Node* root, int level){

if(nullptr == root) return;

if(level == 0){

cout << root->data << " ";

}else{

for(auto child:root->children){

traverLayer(child,level-1);

}

}

}

void BFS2(Node* root){

if(nullptr == root) return;

int n=depth(root);

for(int i=0; i<n; i++){

traverLayer(root, i);

}

}