資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中的二叉搜尋樹 - 搜尋和插入操作
二叉搜尋樹 (BST) 是一種特殊的樹，遵循以下規則：
- 左子節點的值始終小於父節點
- 右子節點的值始終大於父節點。
- 所有節點單獨構成一個二叉搜尋樹。
二叉搜尋樹 (BST) 示例：
建立二叉搜尋樹是為了降低搜尋、查詢最小值和最大值等操作的複雜度。
BST 中的搜尋操作
在二叉搜尋樹中執行搜尋：
我們需要在樹中搜索一個鍵。為此，我們將鍵與樹的根節點進行比較。
如果鍵等於根節點，則找到鍵。
如果鍵的值大於根節點，則取右子樹並搜尋鍵。
如果鍵的值小於根節點，則取左子樹並搜尋鍵。
示例
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* search(struct node* root, int key){
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
insert(root, 45);
printf("The tree is :\n");
traversetree(root);
printf("\nSearching for 12 in this tree ");
if(search(root , 12))
printf("\nelement found");
else
printf("\nelement not found");
return 0;
}輸出
The tree is : 12 15 17 23 29 32 45 Searching for 12 in this tree element found
BST 中的插入操作
BST 中的插入操作發生在樹的葉節點處。對於插入，我們將開始將節點與根節點進行比較，並找到節點的正確位置，然後將其放置。下面的示例將使您更加清楚。
將 12 插入此 BST。
我們將 12 與根節點進行比較：12 > 5，它屬於右子樹。
將 12 與右子節點進行比較：12 > 8，它屬於右子樹的右側。
將 12 與右子樹的右子節點進行比較：12 > 10，它的位置在這個節點的右側。
形成的新樹將是：
示例
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
printf("The tree is :\n");
traversetree(root);
printf("\nInseting 45 to the tree\n");
insert(root, 45);
printf("Tree after insertion is :\n");
traversetree(root);
return 0;
}輸出
The tree is : 12 15 17 23 29 32 Inserting 45 to the tree Tree after insertion is : 12 15 17 23 29 32 45
更新於：2020年1月3日
2K+ 次瀏覽
廣告