数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中二叉树转换为二叉搜索树
二叉树是一种特殊的树，其中树的每个节点最多可以有两个子节点。这些子节点称为右子节点和左子节点。
一个简单的二叉树是 -
二叉搜索树 (BST) 是一种特殊的树，它遵循以下规则 -
左子节点的值总是小于父节点 注意
右子节点的值大于父节点。
所有节点分别形成一个二叉搜索树。
二叉搜索树 (BST) 的示例 -
创建二叉搜索树是为了降低搜索、查找最小值和最大值等操作的复杂度。
在这里，我们给定一个二叉树，我们必须将此二叉树(BT) 转换为二叉搜索树(BST)。在此转换中，二叉树的原始结构不应更改。
让我们举个例子来理解如何将BT 转换为 BST -
输入 -
输出 -
将二叉树转换为二叉搜索树分三个步骤进行。它们是 -
步骤 1 - 将二叉树的中序遍历数据存储到数组arr[] 中。
步骤 2 - 使用任何排序技术对数组 arr[] 进行排序。
步骤 3 - 现在，对树进行中序遍历，并将数组中的元素逐个复制到树的节点中。
示例
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left;
struct node *right;
};
void Inordertraversal(struct node* node, int inorder[], int *index_ptr){
if (node == NULL)
return;
Inordertraversal(node->left, inorder, index_ptr);
inorder[*index_ptr] = node->data;
(*index_ptr)++;
Inordertraversal(node->right, inorder, index_ptr);
}
int countNodes(struct node* root){
if (root == NULL)
return 0;
return countNodes (root->left) +
countNodes (root->right) + 1;
}
int compare (const void * a, const void * b){
return( *(int*)a - *(int*)b );
}
void arrayToBST (int *arr, struct node* root, int *index_ptr){
if (root == NULL)
return;
arrayToBST (arr, root->left, index_ptr);
root->data = arr[*index_ptr];
(*index_ptr)++;
arrayToBST (arr, root->right, index_ptr);
}
struct node* newNode (int data){
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void printInorder (struct node* node){
if (node == NULL)
return;
printInorder (node->left);
printf("%d ", node->data);
printInorder (node->right);
}
int main(){
struct node *root = NULL;
root = newNode(17);
root->left = newNode(14);
root->right = newNode(2);
root->left->left = newNode(11);
root->right->right = newNode(7);
printf("Inorder Traversal of the binary Tree: \n");
printInorder (root);
int n = countNodes(root);
int *arr = new int[n];
int i = 0;
Inordertraversal(root, arr, &i);
qsort(arr, n, sizeof(arr[0]), compare);
i = 0;
arrayToBST (arr, root, &i);
delete [] arr;
printf("\nInorder Traversal of the converted BST: \n");
printInorder (root);
return 0;
}输出
Inorder Traversal of the binary Tree: 11 14 17 2 7 Inorder Traversal of the converted BST: 2 7 11 14 17
更新于: 2020-07-13
908 次查看
广告