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
廣告