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 次瀏覽

開啟您的 職業

完成課程獲得認證

開始了
廣告