Chương trình tìm giá trị nhỏ nhất của một cây tìm kiếm nhị phân (BST).
Thuật toán
Bắt đầu
Khai báo nd là một cấu trúc.
Khai báo d kiểu nguyên.
Khai báo con trỏ lt kiểu cấu trúc nd.
Khai báo con trỏ rt kiểu cấu trúc nd.
Khai báo hàm new_nd() trả về kiểu cấu trúc nd.
Khai báo d kiểu nguyên.
Truyền chúng làm tham số.
Khai báo con trỏ nd kiểu cấu trúc nd.
Khởi tạo nd = (struct nd*) malloc(sizeof(struct nd)).
nd->d = d.
nd->lt = NULL.
nd->rt = NULL.
trả về(nd).
Kết thúc
Bắt đầu
Khai báo hàm add_node() trả về kiểu cấu trúc nd.
Khai báo con trỏ nd kiểu cấu trúc nd.
Khai báo d kiểu nguyên.
Truyền chúng làm tham số.
nếu (nd == NULL) thì
trả về(new_nd(d)).
ngược lại
nếu (d <= nd->d) thì
nd->lt = add_node(nd->lt, d).
ngược lại
nd->rt = add_node(nd->rt, d).
trả về nd.
Kết thúc
Bắt đầu
Khai báo hàm minimum_val() trả về kiểu nguyên.
Khai báo con trỏ nd kiểu cấu trúc nd.
Truyền nó làm tham số.
Khai báo con trỏ cur kiểu cấu trúc nd.
Khởi tạo cur = nd.
while (cur->lt != NULL) thực hiện
cur = cur->lt.
trả về(cur->d).
Khai báo con trỏ root kiểu cấu trúc nd.
Khởi tạo root = NULL.
root = add_node(root, 54).
add_node(root, 32).
add_node(root, 25).
add_node(root, 45).
add_node(root, 65).
add_node(root, 75).
In "The Minimum value of the given binary search tree is: ".
In giá trị nhỏ nhất của cây nhị phân.
getchar().
Kết thúc.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
struct nd {
int d;
struct nd* lt;
struct nd* rt;
};
struct nd* new_nd(int d) {
struct nd* nd = (struct nd*)
malloc(sizeof(struct nd));
nd->d = d;
nd->lt = NULL;
nd->rt = NULL;
return(nd);
}
struct nd* add_node(struct nd* nd, int d) {
if (nd == NULL)
return(new_nd(d));
else {
if (d <= nd->d)
nd->lt = add_node(nd->lt, d);
else
nd->rt = add_node(nd->rt, d);
return nd;
}
}
int minimum_val(struct nd* nd) {
struct nd* cur = nd;
while (cur->lt != NULL) {
cur = cur->lt;
}
return(cur->d);
}
int main() {
struct nd* root = NULL;
root = add_node(root, 54);
add_node(root, 32);
add_node(root, 25);
add_node(root, 45);
add_node(root, 65);
add_node(root, 75);
cout << "The Minimum value of the given binary search tree is: " << minimum_val(root);
getchar();
return 0;
}
Kết quả
The Minimum value of the given binary search tree is: 25