数据结构
网络
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+ 浏览量
广告