Cây Nhị Phân Là Gì

Trong bài xích này mình đã giới thiệu chúng ta một trong các kết cấu dữ liệu tiếp theo sau đó chủ yếu là cấu trúc dữ liệu dạng cây. Đây là 1 trong dạng kết cấu được sử dụng rất nhiều trong search kiếm, nó được tối ưu độc nhất trong các cấu trúc dữ liệu mà mình đã giới thiệu.

Bạn đang xem: Cây nhị phân là gì

Chúng ta sẽ cùng nhau tìm hiểu về cấu trúc dữ liệu cây là gì? Có những loại cấu tạo dữ liệu cây làm sao và cách thức buổi giao lưu của nó.

1. Cấu tạo dữ liệu cây là gì?

Cấu trúc tài liệu cây là một cấu tạo biểu diễn các Node dưới dạng cây. Như các bạn đã học tập ở môn xây dựng C/C++ thì khi chúng ta muốn lưu các phần tử, ta có thể lưu chúng dưới dạng mảng một chiều. Hoặc có thể lưu bên dưới dạng một list liên kết. Giống như như vậy các bạn cũng có thể lưu bên dưới dạng cây nhị phân.

Ưu điểm của ghép trúc tài liệu cây so với các kết cấu khác là:

Bài viết này được đăng tại

Phân cấp dữ liệu.Tìm kiếm thuận tiện hơn.Thao tác trên các danh sách dữ liệu đã chuẩn bị xếp.

Trong cấu trúc dữ liệu cây, bao gồm hai cấu tạo chính đó là kết cấu cây nhị phân và kết cấu cây nhị phân tra cứu kiếm. Sau đây bọn họ sẽ tò mò qua về hai cấu tạo dữ liệu này nhé.

2. Cây nhị phân (Binary tree)

Cây nhị phân là một cấu tạo dữ liệu được áp dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân bao gồm các Node cùng mỗi Node bao gồm 3 thành phần:

Data: quý hiếm của một phần tửLeft pointer: nhỏ trỏ trỏ mang lại cây nhị phân bên trái Node.Right pointer: nhỏ trỏ trỏ đến cây nhị phân bên đề nghị Node.

Các nhân tố cơ phiên bản của cây nhị phân bao gồm:

Root: Được gọi là Node nơi bắt đầu của cây (là một Node cha), một cây chỉ gồm một Node cội duy nhất cùng nó không có Node phụ vương nào.Parent Node: Là Node cha của một Node cụ thể nào đó.Child Node: Là Node nhỏ của một Node cụ thể nào đó.

Xem thêm: Cách Làm Mì Ý Xúc Xích - Cách Làm Spaghetti Xúc Xích Sốt Cà Chua Thơm Ngon

Sub-tree: Là cây nhỏ biểu diển những con của một Node.LeafNode: Là Node không tồn tại Node con.Siblings: các Node tất cả cùng một cha.Internal Node: Node có ít nhất một Node con.External Node: Node không có Node bé nào.

3. Cây nhị phân search kiếm (Binary tìm kiếm tree)

Cây nhị phân tìm kiếm là một dạng đặc trưng của cây nhị phân. Về cơ phiên bản nó tất cả đủ tất cả các yếu tắc của cây nhị phân. Nhưng toàn bộ các Node của nó đều phải có chung một đặc điểm sau:

Cây bé bên trái của một Node luôn luôn luôn có giá trị nhỏ tuổi hơn hoặc bởi giá trị của Node cha phía bên trên nó.Cây bé bên nên của một Node luôn luôn có mức giá trị to hơn hoặc bằng giá trị của Node thân phụ phía bên trên nó.

Biểu diễn cây nhị phân kiếm tìm kiếm

Cây nhị phân kiếm tìm kiếm là một trong tập hợp những Node được bố trí và lưu trữ theo một quy tắc nhất định. Nhờ vào quy tắc đó bạn có thể duy trì và triển khai các thao tác trên cây nhị phân tìm kiếm kiếm. Chúng ta hãy xem hình dưới đây để làm rõ hơn về nguyên tắc của nó:

Giả sử ta tất cả các thành phần số nguyên như sau: 27, 14, 35, 10, 19, 31, 32. Quy trình lưu trữ các thành phần này theo cấu tạo cây nhị phân tìm kiếm được thực hiện như sau:

Số 27 sẽ được lưu trữ vào cây trước tiên và nó được lấy làm cho key để so sánh.Số 14 được đối chiếu với số 27 (key), vì 14 Số 35 > 27 bởi vậy sẽ tiến hành lưu trữ vào bên buộc phải số 27.Tiếp tục số 10 Số 19 14 vị vậy nó sẽ nằm bên cạnh phải số 14.Số 31 > 27 và 31 ở đầu cuối số 42 > 27 và 42 > 35 vị vậy nó sẽ nằm bên phải số 35.

Sau khi triển khai lưu trữ các thành phần số nguyên bên trên vào cây ta được một cây như vào hình.

Các thao tác làm việc trên cây nhị phân kiếm tìm kiếm

Trong cây nhị phân kiếm tìm kiếm ta rất có thể thực hiện nay các làm việc sau:

Chèn một trong những phần tử vào trong một cây.Tìm kiếm bộ phận trong cây.Duyệt cây.Đo độ cao của cây.

Trên đây là các thao tác thường được sử dụng nhiều trong cây. Đặc biệt là tìm kiếm bộ phận trong cây, như cái thương hiệu của nó là cây nhị phân search kiếm. Đây là một kết cấu dữ liệu được sử dụng trong các bài toán search kiếm khôn cùng nhiều, vày tính đúng đắn và vận tốc của nó.

4. Kết luận

Như vậy là chúng ta đã search hiểu hoàn thành về cấu trúc dữ liệu cây là gì. Và những hai kết cấu dữ liệu cây nhị phân với nhị phân search kiếm. Chúng ta hãy áp dụng các cấu tạo dữ liệu thật linh động nhé, bởi vì mỗi kết cấu dữ liệu đều phải sở hữu các điểm mạnh nhất định. Ở bài tiếp theo mình sẽ trả lời các kết cấu dữ liệu của cây và bí quyết thêm Node vào cây, hãy để ý theo dõi nhé !!!