数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装研究
法学C++ 中不使用递归实现 N 叉树的前序遍历
在本问题中，我们给出一棵 N 叉树。我们的任务是打印该树的前序遍历。
首先，让我们学习一些基本术语，
N 叉树是一棵树，其中所有节点最多可以拥有 N 个子节点。例如，2 叉（二叉）树最多有 2 个子节点。
前序遍历是一种遍历树节点的方式。在这种方式中，我们将首先遍历根节点，然后是左子节点，然后是右子节点。
我们举一个例子来理解我们的问题
Preorder traversal : 12151499411719
要解决此问题，我们必须使用堆栈数据结构。我们将首先将根节点压入堆栈中。然后将其弹出并打印。对于每个弹出的节点，我们将从右子节点压入堆栈中的子节点到左子节点。然后在所有子节点被推出后将其弹出。重复此过程，直到堆栈为空。
程序演示了我们解决方案的实现
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
vector<Node*> child;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
return temp;
}
void preOrderTraversal(struct Node* root){
stack<Node*> tree;
tree.push(root);
while (!tree.empty()) {
Node* curr = tree.top();
tree.pop();
cout<<curr->key<<"\t";
vector<Node*>::iterator it = curr->child.end();
while (it != curr->child.begin()) {
it--;
tree.push(*it);
}
}
}
int main(){
Node* root = insertNode(12);
(root->child).push_back(insertNode(15));
(root->child).push_back(insertNode(99));
(root->child).push_back(insertNode(4));
(root->child).push_back(insertNode(7));
(root->child[0]->child).push_back(insertNode(1));
(root->child[0]->child).push_back(insertNode(4));
(root->child[0]->child).push_back(insertNode(25));
(root->child[2]->child).push_back(insertNode(11));
(root->child[3]->child).push_back(insertNode(19));
cout<<"PreOrder Traversal of the tree is :\n";
preOrderTraversal(root);
return 0;
}输出
PreOrder Traversal of the tree is : 12 15 14 25 99 4 11 7 19
更新于： 03-2 月 2020 年
172 次浏览
广告