Cây nhị phân

Bách khoa toàn thư mở Wikipedia
Một cây nhị phân được gắn nhãn có kích thước là 9 và chiều cao là 3, với nút gốc có giá trị là 2. Cây trên không cân bằng và không được sắp xếp.

Trong khoa học máy tính, cây nhị phân (tiếng Anh: binary tree) là một cấu trúc dữ liệu cây mà mỗi nút có nhiều nhất hai nút con, được gọi là con trái (left child) và con phải (right child). Một định nghĩa đệ quy chỉ sử dụng các khái niệm lý thuyết tập hợp là cây nhị phân không trống là một tuple (L, S, R), với LR là các cây nhị phân hay tập hợp rỗngStập đơn (singleton set).[1] Một số tác giả cho phép cây nhị phân cũng có thể là tập hợp trống.[2]

Từ góc độ lý thuyết đồ thị, cây nhị phân (và K-ary) như định nghĩa ở đây thực sự là arborescence.[3] Vì vậy cây nhị phân có thể gọi là arborescence phân nhánh đôi (bifurcating arborescence)[3]—một thuật ngữ xuất hiện trong các sách lập trình rất cũ,[4] trước khi thuật ngữ khoa học máy tính hiện đại chiếm ưu thế. Cũng có thể hiểu cây nhị phân là một đồ thị vô hướng chứ không phải đồ thị có hướng, trong trường hợp đó cây nhị phân là một cây có gốcthứ tự[5] Một số tác giả dùng thuật ngữ cây nhị phân có gốc thay vì cây nhị phân để nhấn mạnh thực tế rằng cây có gốc, nhưng như được định nghĩa ở trên thì cây nhị phân luôn có gốc.[6] Cây nhị phân là trường hợp đặc biệt của cây K-ary, với k bằng 2.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Trích dẫn[sửa | sửa mã nguồn]

  1. ^ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. tr. 620. ISBN 978-1-4398-1280-8.
  2. ^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. tr. 77. ISBN 978-1-84800-070-4.
  3. ^ a b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. tr. 363. ISBN 0-201-89683-4.
  4. ^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. tr. 39.
  5. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. tr. 749. ISBN 978-0-07-338309-5.
  6. ^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. tr. 246. ISBN 978-0-88385-762-5.

Thư mục[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]