資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式實現給定二叉樹的非遞迴先序遍歷
樹的遍歷是圖遍歷的一種形式。它涉及到精確地檢查或列印樹中的每個節點一次。二叉搜尋樹的先序遍歷涉及按（根、左、右）的順序訪問樹中的每個節點。
二叉樹的先序遍歷示例如下。
給定一個二叉樹如下所示。
先序遍歷結果：5 3 2 4 8 9
下面給出一個執行非遞迴先序遍歷的程式。
示例
#include<iostream>
#include <stack>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp→data = val;
temp→left = temp→right = NULL;
return temp;
}
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node->right);
if (temp_node→left)
nodeStack.push(temp_node->left);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node→data)
node→left = insertNode(node→left, val);
else if (val > node→data)
node→right = insertNode(node→right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
}輸出
Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9
在上面的程式中，結構體node建立樹的節點。這個結構體是一個自引用結構體，因為它包含struct node型別的指標。該結構體如下所示。
struct node {
int data;
struct node *left;
struct node *right;
};createNode()函式建立一個節點temp並使用malloc為其分配記憶體。資料值val儲存在temp的資料中。NULL儲存在temp的左和右指標中。這可以透過以下程式碼片段演示。
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp→data = val;
temp→left = temp→right = NULL;
return temp;
}preorder()函式使用堆疊以先序列印樹的元素。首先將根節點插入堆疊。啟動一個while迴圈，直到堆疊不為空。首先顯示堆疊頂部元素topnode中的資料，然後彈出該節點。然後將上述節點的右節點和左節點壓入堆疊。
此函式使用以下程式碼片段進行演示。
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node→right);
if (temp_node→left)
nodeStack.push(temp_node→left);
}
}insertNode()函式將所需的值插入到二叉樹的正確位置。如果節點為NULL，則呼叫createNode。否則，在樹中找到節點的正確位置。這可以在下面的程式碼片段中觀察到。
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node→data)
node→left = insertNode(node→left, val);
else if (val > node→data)
node->right = insertNode(node→right, val);
return node;
}在main()函式中，首先將根節點定義為NULL。然後將所有具有所需值的節點插入到二叉搜尋樹中。如下所示。
struct node *root = NULL; root = insertNode(root, 5); insertNode(root, 8); insertNode(root, 3); insertNode(root, 2); insertNode(root, 6); insertNode(root, 9); insertNode(root, 4);
最後，使用樹的根節點呼叫preorder()函式，並以先序顯示所有樹的值。如下所示。
cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);
更新於：2020年6月24日
瀏覽量1K+
廣告