資料結構
網路
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 次瀏覽
廣告