資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式實現給定二叉樹的中序遞迴遍歷
樹遍歷是圖遍歷的一種形式。它涉及到精確檢查或列印樹中的每個節點一次。二叉搜尋樹的中序遍歷涉及按照 (左、根、右) 的順序訪問樹中的每個節點。
二叉樹的中序遍歷示例如下。
給定一個二叉樹如下。
中序遍歷結果為：1 4 5 6 8
執行中序遞迴遍歷的程式如下所示。
示例
#include<iostream>
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 inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
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, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
}輸出
In-Order traversal of the Binary Search Tree is: 1 2 3 4 5 9
在上述程式中，結構體 node 建立樹的節點。該結構體是一個自引用結構體，因為它包含 struct node 型別的指標。該結構體顯示如下。
struct node {
int data;
struct node *left;
struct node *right;
};函式 createNode() 建立一個節點 temp 並使用 malloc 為其分配記憶體。資料值 val 儲存在 temp 的 data 中。NULL 儲存在 temp 的 left 和 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;
}函式 inorder() 以二叉樹的根節點作為引數，並按中序列印樹的元素。它是一個遞迴函式。使用以下程式碼進行演示。
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}函式 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, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
最後，使用樹的根節點呼叫函式 inorder()，並按中序顯示所有樹值。如下所示。
cout<<"In-Order traversal of the Binary Search Tree is: "; inorder(root);
更新於: 2020-06-24
14K+ 瀏覽量
廣告