Cây nhị phân trong C
Trong C, một Cây nhị phân là một thể hiện của cấu trúc dữ liệu cây với một nút cha có thể có số lượng tối đa hai nút con; 0, 1 hoặc 2 nút con. Mỗi nút đơn lẻ trong một Cây nhị phân có một giá trị của riêng nó và hai con trỏ tới con của nó, một con trỏ cho con trái và con trỏ kia cho con phải.
Khai báo cây nhị phân
MỘT Cây nhị phân có thể được khai báo trong C bằng cách sử dụng một đối tượng được gọi là cấu trúc mô tả một trong các nút trong cây.
cấu trúc nút {
kiểu dữ liệu var_name ;
cấu trúc nút * bên trái ;
cấu trúc nút * Phải ;
} ;
Trên đây là tuyên bố của một Cây nhị phân tên nút như một nút. Nó giữ ba giá trị; một là biến lưu trữ dữ liệu và hai biến còn lại là con trỏ tới biến con. (con trái và phải của nút cha).
Sự kiện của cây nhị phân
Ngay cả đối với các tập hợp dữ liệu lớn, sử dụng một Cây nhị phân giúp việc tìm kiếm trở nên dễ dàng và nhanh chóng hơn. Số lượng cành cây không hạn chế. Trái ngược với một mảng, bất kỳ loại cây nào cũng có thể được tạo ra và tăng lên dựa trên những gì được yêu cầu của một cá nhân.
Thực hiện cây nhị phân trong C
Sau đây là hướng dẫn từng bước để thực hiện một Cây nhị phân trong C
Bước 1: Khai báo cây tìm kiếm nhị phân
Tạo một nút cấu trúc có ba loại dữ liệu, chẳng hạn như dữ liệu, *left_child và *right_child, trong đó dữ liệu có thể thuộc loại số nguyên và cả hai nút *left_child và *right_child đều có thể được khai báo là NULL hoặc không.
cấu trúc nút{
int dữ liệu ;
cấu trúc nút * ngay_con ;
cấu trúc nút * trái_con ;
} ;
Bước 2: Tạo các nút mới trong cây tìm kiếm nhị phân
Tạo một nút mới bằng cách tạo một hàm chấp nhận một số nguyên làm đối số và cung cấp con trỏ tới nút mới được tạo với giá trị đó. Sử dụng hàm malloc() trong C để cấp phát bộ nhớ động cho nút đã tạo. Khởi tạo con trái và con phải thành NULL và trả về tên nút.
cấu trúc nút * tạo nên ( dữ liệu kiểu dữ liệu )
{
cấu trúc nút * Tên nút = malloc ( kích thước của ( cấu trúc nút ) ) ;
Tên nút -> dữ liệu = giá trị ;
Tên nút -> trái_con = Tên nút -> ngay_con = VÔ GIÁ TRỊ ;
trở lại Tên nút ;
}
Bước 3: Chèn các phần tử con bên phải và bên trái vào cây nhị phân
Tạo các hàm insert_left và insert_right sẽ chấp nhận hai đầu vào, là giá trị được chèn và con trỏ tới nút mà cả hai nút con sẽ được kết nối. Gọi hàm tạo để tạo một nút mới và gán con trỏ trả về cho con trỏ bên trái của con trái hoặc con trỏ bên phải của con phải của cha mẹ gốc.
cấu trúc nút * chèn_trái ( cấu trúc nút * nguồn gốc , dữ liệu kiểu dữ liệu ) {nguồn gốc -> bên trái = tạo nên ( dữ liệu ) ;
trở lại nguồn gốc -> bên trái ;
}
cấu trúc nút * chèn_right ( cấu trúc nút * nguồn gốc , dữ liệu kiểu dữ liệu ) {
nguồn gốc -> Phải = tạo nên ( dữ liệu ) ;
trở lại nguồn gốc -> Phải ;
}
Bước 4: Hiển thị các nút của cây nhị phân bằng phương pháp truyền tải
Chúng ta có thể hiển thị cây bằng cách sử dụng ba phương pháp duyệt trong C. Các phương pháp duyệt này là:
1: Tra cứu đơn đặt hàng trước
Trong phương pháp truyền tải này, chúng ta sẽ đi qua các nút theo hướng từ parent_node->left_child->right_child .
khoảng trống đặt hàng trước ( nút * nguồn gốc ) {nếu như ( nguồn gốc ) {
bản inf ( '%d \N ' , nguồn gốc -> dữ liệu ) ;
display_pre_order ( nguồn gốc -> bên trái ) ;
display_pre_order ( nguồn gốc -> Phải ) ;
}
}
2: Tra cứu sau khi đặt hàng
Trong phương pháp truyền tải này, chúng ta sẽ đi qua các nút theo hướng từ left_child->right_child->parent_node-> .
khoảng trống display_post_order ( nút * nguồn gốc ) {nếu như ( Cây nhị phân ) {
display_post_order ( nguồn gốc -> bên trái ) ;
display_post_order ( nguồn gốc -> Phải ) ;
bản inf ( '%d \N ' , nguồn gốc -> dữ liệu ) ;
}
}
3: Travers theo thứ tự
Trong phương pháp truyền tải này, chúng ta sẽ đi qua các nút theo hướng từ left_node->root_child->right_child .
khoảng trống display_in_order ( nút * nguồn gốc ) {nếu như ( Cây nhị phân ) {
display_in_order ( nguồn gốc -> bên trái ) ;
bản inf ( '%d \N ' , nguồn gốc -> dữ liệu ) ;
display_in_order ( nguồn gốc -> Phải ) ;
}
}
Bước 5: Thực hiện xóa trong cây nhị phân
Chúng ta có thể xóa những gì đã tạo Cây nhị phân bằng cách xóa cả các nút con có chức năng nút cha trong C như sau.
khoảng trống xóa_t ( nút * nguồn gốc ) {nếu như ( nguồn gốc ) {
xóa_t ( nguồn gốc -> bên trái ) ;
xóa_t ( nguồn gốc -> Phải ) ;
miễn phí ( nguồn gốc ) ;
}
}
Chương trình C của cây tìm kiếm nhị phân
Sau đây là cách triển khai đầy đủ cây tìm kiếm nhị phân trong lập trình C:
#include#include
cấu trúc nút {
int giá trị ;
cấu trúc nút * bên trái , * Phải ;
} ;
cấu trúc nút * nút1 ( int dữ liệu ) {
cấu trúc nút * tmp = ( cấu trúc nút * ) malloc ( kích thước của ( cấu trúc nút ) ) ;
tmp -> giá trị = dữ liệu ;
tmp -> bên trái = tmp -> Phải = VÔ GIÁ TRỊ ;
trở lại tmp ;
}
khoảng trống in ( cấu trúc nút * Nút gốc ) // hiển thị các nút!
{
nếu như ( Nút gốc != VÔ GIÁ TRỊ ) {
in ( Nút gốc -> bên trái ) ;
bản inf ( '%d \N ' , Nút gốc -> giá trị ) ;
in ( Nút gốc -> Phải ) ;
}
}
cấu trúc nút * chèn_node ( cấu trúc nút * nút , int dữ liệu ) // chèn các nút!
{
nếu như ( nút == VÔ GIÁ TRỊ ) trở lại nút1 ( dữ liệu ) ;
nếu như ( dữ liệu < nút -> giá trị ) {
nút -> bên trái = chèn_node ( nút -> bên trái , dữ liệu ) ;
} khác nếu như ( dữ liệu > nút -> giá trị ) {
nút -> Phải = chèn_node ( nút -> Phải , dữ liệu ) ;
}
trở lại nút ;
}
int chủ yếu ( ) {
bản inf ( 'C triển khai Cây tìm kiếm nhị phân! \N \N ' ) ;
cấu trúc nút * cha mẹ = VÔ GIÁ TRỊ ;
cha mẹ = chèn_node ( cha mẹ , 10 ) ;
chèn_node ( cha mẹ , 4 ) ;
chèn_node ( cha mẹ , 66 ) ;
chèn_node ( cha mẹ , Bốn năm ) ;
chèn_node ( cha mẹ , 9 ) ;
chèn_node ( cha mẹ , 7 ) ;
in ( cha mẹ ) ;
trở lại 0 ;
}
Trong đoạn mã trên, đầu tiên chúng ta khai báo một nút sử dụng cấu trúc . Sau đó, chúng tôi khởi tạo một nút mới là “ nút1 ” và cấp phát bộ nhớ động bằng cách sử dụng malloc() trong C với dữ liệu và hai con trỏ kiểu con sử dụng nút được khai báo. Sau này, chúng tôi hiển thị nút bằng printf() chức năng và gọi nó trong chủ yếu() chức năng. Sau đó insertion_node() chức năng được tạo, trong đó nếu dữ liệu nút là NULL thì nút1 đã ngừng hoạt động, dữ liệu khác được đặt trong nút (cha mẹ) của con bên trái và bên phải. Chương trình bắt đầu thực hiện từ chủ yếu() chức năng tạo một nút bằng cách sử dụng một vài nút mẫu khi còn nhỏ và sau đó sử dụng các phương thức duyệt theo thứ tự để in nội dung nút.
đầu ra
Phần kết luận
Cây thường được sử dụng để giữ dữ liệu ở dạng phi tuyến tính. cây nhị phân là những loại cây mà mỗi nút (cha) có hai con là con trái và con phải. MỘT Cây nhị phân là một phương pháp linh hoạt để truyền và lưu trữ dữ liệu. Nó hiệu quả hơn so với Linked-List trong C. Trong bài viết trên, chúng ta đã thấy khái niệm về một Cây nhị phân từng bước thực hiện một Cây tìm kiếm nhị phân trong C