Trong phần này, chúng ta sẽ thấy một số thuộc tính quan trọng của một cấu trúc dữ liệu cây nhị phân. Giả sử chúng ta có một cây nhị phân như thế này.
Một số thuộc tính -
- Số nút tối đa ở cấp ‘l’ sẽ là $ 2 ^ {l-1} $. Ở đây cấp là số lượng nút trên đường dẫn từ gốc đến nút, bao gồm cả bản thân gốc. Chúng tôi đang xem xét cấp độ gốc là 1.
- Số lượng nút tối đa có trong cây nhị phân có chiều cao h là $ 2 ^ {h} -1 $. Ở đây chiều cao là số nút tối đa trên đường dẫn từ gốc đến lá. Ở đây chúng ta đang xem xét chiều cao của một cây có một nút là 1.
- Trong cây nhị phân có n nút, chiều cao tối thiểu có thể có hoặc số cấp tối thiểu là $ \ log_ {2} \ lgroup {n + 1} \ rgroup $. Nếu chúng ta coi rằng chiều cao của nút lá được coi là 0, thì công thức sẽ là $ \ log_ {2} \ lgroup {n + 1} \ rgroup-1 $
- Một cây nhị phân với các lá "L" có ít nhất $ \ log_ {2} {L + 1} $ số cấp độ
- Nếu một cây nhị phân có 0 hoặc 2 nút con, thì số nút lá luôn nhiều hơn một nút có hai nút con.
N.B. Như cây nhị phân là một loại cây; nó có tất cả các thuộc tính của cây trong lý thuyết đồ thị.