Rate this post

Nếu độ lớn hơn của mọi nút nhỏ hơn hoặc bằng 2, trong cây có hướng hơn cây được gọi là Binary Trees. Một cây bao gồm các nút (cây trống) cũng là một Binary Trees.

Các bài viết liên quan:

Thuật ngữ cơ bản

Root: Binary Trees có một nút duy nhất được gọi là gốc của cây.

Left Child: Nút bên trái của gốc được gọi là nút con bên trái của nó.

Right Child: Nút ở bên phải của gốc được gọi là nút con bên phải của nó.

Parent Node: Một nút có nút con bên trái hoặc nút con bên phải hoặc cả hai được gọi là nút cha của các nút.

Siblings: Hai nút có cùng cha mẹ được gọi là anh chị em.

Leaf: Một nút không có con được gọi là lá. Số lượng lá trong Binary Trees có thể thay đổi từ một (tối thiểu) đến một nửa số đỉnh (tối đa) trong một cây.

Descendant: Một nút được gọi là con của một nút khác nếu nó là con của nút hoặc con của một số con khác của nút đó. Tất cả các nút trong cây là con cháu của gốc.

Left Subtree: Cây con có gốc là con bên trái của một số nút được gọi là cây con bên trái của nút đó.

Ví dụ: Đối với cái cây như trong hình:

  • Nút nào là gốc?
  • Những nút nào là lá?
  • Đặt tên cho nút cha của mỗi nút
  • Binary Trees toán học rời rạc

Giải: (i) Nút A là nút gốc.

(ii) Các nút G, H, I, L, M, N, O là các lá.

(iii) Nodes Parent

        B, C A

        D, E B

        F C

        G, H D

        I, J E

        K F

        L, M J

        N, O K

Cây con phải: Cây con có gốc là con bên phải của một nút nào đó được gọi là cây con bên phải của nút đó.

Mức của một nút: Mức của một nút là khoảng cách của nó từ gốc. Mức gốc được xác định là không. Cấp của tất cả các nút khác hơn nút cha của nó một bậc. Số nút tối đa ở bất kỳ mức N nào là 2N.

Chiều sâu hoặc Chiều cao của cây: Chiều sâu hoặc chiều cao của cây được định nghĩa là số lượng nút tối đa trong một nhánh của cây. Đây là nhiều hơn mức tối đa của cây, tức là độ sâu của rễ là một. Số nút tối đa trong Binary Trees có độ sâu d là 2d-1, trong đó d ≥1.

Các nút bên ngoài: Các nút không có nút con được gọi là nút bên ngoài hoặc nút đầu cuối.

Các nút bên trong: Các nút có một hoặc nhiều hơn một nút con được gọi là nút bên trong hoặc nút không đầu cuối.

Binary Expression Trees

Một biểu thức đại số có thể được biểu diễn một cách thuận tiện bằng cây biểu thức của nó. Một biểu thức có các toán tử nhị phân có thể được phân tách thành

      <toán hạng bên trái hoặc biểu thức> (toán tử) <toán hạng bên phải hoặc biểu thức>

Tùy thuộc vào mức độ ưu tiên đánh giá.

Cây biểu thức là một Binary Trees có gốc chứa toán tử và cây con bên trái chứa biểu thức bên trái và cây con bên phải chứa biểu thức bên phải.

Ví dụ: Xây dựng cây biểu thức nhị phân cho biểu thức (a + b) * (d / c)

Giải pháp: Cây biểu thức nhị phân cho biểu thức (a + b) * (d / c) được hiển thị trong hình:

Binary Trees hoàn chỉnh: Binary Trees hoàn chỉnh là Binary Trees nếu nó là tất cả các cấp, ngoại trừ có thể là cấp cuối cùng, có số lượng nút tối đa cho bên trái càng tốt. Độ sâu của Binary Trees hoàn chỉnh có n nút là log2 n + 1.

Ví dụ: Cây trong hình là một Binary Trees hoàn chỉnh.

Binary Trees đầy đủ: Binary Trees đầy đủ là Binary Trees trong đó tất cả các lá ở cùng một mức và mọi nút không phải lá đều có hai nút con.

Phân biệt giữa General Tree và Binary Tree

General TreeBinary Tree
Không có cây nào như vậy không có nút hoặc một cây tổng quát rỗng. Có thể có một Binary Trees rỗng.
Nếu một số nút có con, thì không có sự phân biệt như vậy.Nếu một số nút có con, thì nó được phân biệt là nút con bên trái hay nút con bên phải.
Những cây trong hình đều giống nhau, khi chúng ta coi chúng là những cây nói chung.Các cây trong hình là khác biệt, khi chúng ta coi chúng là Binary Trees, vì ở (4) là con bên phải của 2 trong khi ở (ii) 4 là con bên trái của 2.

Leave a Reply

Call now
%d bloggers like this: