Giả sử chúng ta có một cây tìm kiếm nhị phân. Chúng ta phải tìm phần tử tối thiểu trong cây tìm kiếm nhị phân. Vì vậy, nếu BST như dưới đây -
Phần tử tối thiểu sẽ là 1.
Như chúng ta biết rằng cây con bên trái luôn chứa các phần tử nhỏ hơn. Vì vậy, nếu chúng ta đi qua cây con bên trái nhiều lần cho đến khi bên trái là null, chúng ta có thể tìm thấy phần tử nhỏ nhất.
Ví dụ
#include<iostream>
using namespace std;
class node{
public:
node *left;
int val;
node *right;
};
node *bst = NULL;
node *getNode(){
node *newNode;
newNode = new node;
return newNode;
}
void insert(node **root, int key){
node *newNode;
newNode = getNode();
newNode->val = key; newNode->left = NULL; newNode->right = NULL;
if(*root == NULL){
*root = newNode;
return;
} else {
if(key < (*root)->val)
insert(&((*root)->left), key);
else
insert(&((*root)->right), key);
}
}
int minElement(){
node* current = bst;
while (current->left != NULL) {
current = current->left;
}
return(current->val);
}
main(){
int item[] = {3, 2, 1, 6, 5, 8};
int n = sizeof(item)/sizeof(item[0]);
int i;
for(i = 0; i<8; i++){
insert(&bst, item[i]);
}
cout << "Minimum element is: " << minElement();
} Đầu ra
Minimum element is: 1