Cây nhị phân

Một cây nhị phân (binary tree) là một cấu trúc dữ liệu phi tuyến tính mô hình hóa mối quan hệ phân cấp giữa "tổ tiên" (ancestors) và "hậu duệ" (descendants), đồng thời thể hiện mô hình chia để trị (divide-and-conquer) mà trong đó mỗi lần chia tách sẽ rẽ thành hai nhánh. Tương tự như danh sách liên kết, đơn vị cơ bản của cây nhị phân là một nút (node), và mỗi nút chứa một giá trị, một tham chiếu đến nút con bên trái (left child node) và một tham chiếu đến nút con bên phải (right child node) của nó.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

class TreeNode:
    """Nút cây nhị phân"""
    def __init__(self, val: int):
        self.val: int = val                # Giá trị của nút
        self.left: TreeNode | None = None  # Tham chiếu đến nút con bên trái
        self.right: TreeNode | None = None # Tham chiếu đến nút con bên phải

/* Nút cây nhị phân */
struct TreeNode {
    int val;          // Giá trị của nút
    TreeNode *left;   // Con trỏ đến nút con bên trái
    TreeNode *right;  // Con trỏ đến nút con bên phải
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/* Nút cây nhị phân */
class TreeNode {
    int val;         // Giá trị của nút
    TreeNode left;   // Tham chiếu đến nút con bên trái
    TreeNode right;  // Tham chiếu đến nút con bên phải
    TreeNode(int x) { val = x; }
}

/* Nút cây nhị phân */
class TreeNode(int? x) {
    public int? val = x;    // Giá trị của nút
    public TreeNode? left;  // Tham chiếu đến nút con bên trái
    public TreeNode? right; // Tham chiếu đến nút con bên phải
}

/* Nút cây nhị phân */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
/* Hàm khởi tạo */
func NewTreeNode(v int) *TreeNode {
    return &TreeNode{
        Left:  nil, // Con trỏ đến nút con bên trái
        Right: nil, // Con trỏ đến nút con bên phải
        Val:   v,   // Giá trị của nút
    }
}

/* Nút cây nhị phân */
class TreeNode {
    var val: Int // Giá trị của nút
    var left: TreeNode? // Tham chiếu đến nút con bên trái
    var right: TreeNode? // Tham chiếu đến nút con bên phải

    init(x: Int) {
        val = x
    }
}

/* Nút cây nhị phân */
class TreeNode {
    val; // Giá trị của nút
    left; // Con trỏ đến nút con bên trái
    right; // Con trỏ đến nút con bên phải
    constructor(val, left, right) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/* Nút cây nhị phân */
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val; // Giá trị của nút
        this.left = left === undefined ? null : left; // Tham chiếu đến nút con bên trái
        this.right = right === undefined ? null : right; // Tham chiếu đến nút con bên phải
    }
}

/* Nút cây nhị phân */
class TreeNode {
  int val;         // Giá trị của nút
  TreeNode? left;  // Tham chiếu đến nút con bên trái
  TreeNode? right; // Tham chiếu đến nút con bên phải
  TreeNode(this.val, [this.left, this.right]);
}

use std::rc::Rc;
use std::cell::RefCell;

/* Nút cây nhị phân */
struct TreeNode {
    val: i32,                               // Giá trị của nút
    left: Option<Rc<RefCell<TreeNode>>>,    // Tham chiếu đến nút con bên trái
    right: Option<Rc<RefCell<TreeNode>>>,   // Tham chiếu đến nút con bên phải
}

impl TreeNode {
    /* Hàm khởi tạo */
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            val,
            left: None,
            right: None
        }))
    }
}

/* Nút cây nhị phân */
typedef struct TreeNode {
    int val;                // Giá trị của nút
    int height;             // Chiều cao của nút
    struct TreeNode *left;  // Con trỏ đến nút con bên trái
    struct TreeNode *right; // Con trỏ đến nút con bên phải
} TreeNode;

/* Hàm khởi tạo */
TreeNode *newTreeNode(int val) {
    TreeNode *node;

    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* Nút cây nhị phân */
class TreeNode(val _val: Int) {  // Giá trị của nút
    val left: TreeNode? = null   // Tham chiếu đến nút con bên trái
    val right: TreeNode? = null  // Tham chiếu đến nút con bên phải
}

### Lớp nút cây nhị phân ###
class TreeNode
  attr_accessor :val    # Giá trị của nút
  attr_accessor :left   # Tham chiếu đến nút con bên trái
  attr_accessor :right  # Tham chiếu đến nút con bên phải

  def initialize(val)
    @val = val
  end
end

Mỗi nút có hai tham chiếu (con trỏ), trỏ tương ứng đến nút con bên trái (left-child node) và nút con bên phải (right-child node). Nút này được gọi là nút cha (parent node) của hai nút con này. Khi có một nút của cây nhị phân, chúng ta gọi cây được tạo bởi nút con bên trái của nút này và tất cả các nút bên dưới nó là cây con bên trái (left subtree) của nút đó. Tương tự, cây con bên phải (right subtree) cũng có thể được định nghĩa như vậy.

Trong một cây nhị phân, mọi nút không phải nút lá đều có các nút con và do đó có các cây con không rỗng. Như được hiển thị trong hình bên dưới, nếu "Nút 2" được coi là một nút cha, các nút con bên trái và bên phải của nó lần lượt là "Nút 4" và "Nút 5". Cây con bên trái được tạo bởi "Nút 4" và tất cả các nút bên dưới nó, trong khi cây con bên phải được tạo bởi "Nút 5" và tất cả các nút bên dưới nó.

Thuật ngữ thường gặp của Cây nhị phân

Các thuật ngữ thường dùng của cây nhị phân được thể hiện trong hình dưới đây.

• Nút gốc (Root node): Nút ở mức cao nhất của cây nhị phân, không có nút cha.
• Nút lá (Leaf node): Nút không có bất kỳ nút con nào, cả hai con trỏ của nó đều trỏ đến None.
• Cạnh (Edge): Đoạn thẳng nối giữa hai nút, đại diện cho một tham chiếu (con trỏ) giữa các nút đó.
• Mức (Level) của một nút: Tăng dần từ trên xuống dưới, với nút gốc ở mức 1.
• Bậc (Degree) của một nút: Số lượng nút con của nút đó. Trong cây nhị phân, bậc có thể là 0, 1 hoặc 2.
• Chiều cao (Height) của cây nhị phân: Số lượng cạnh đi từ nút gốc đến nút lá xa nhất.
• Độ sâu (Depth) của một nút: Số lượng cạnh đi từ nút gốc đến nút đó.
• Chiều cao (Height) của một nút: Số lượng cạnh đi từ nút lá xa nhất đến nút đó.

Tip

Chúng ta thường định nghĩa "chiều cao" và "độ sâu" là số lượng cạnh đi qua, nhưng một số sách giáo khoa và đề bài định nghĩa chúng là số lượng nút trên đường đi. Trong trường hợp đó, cả hai giá trị đều lớn hơn 1 đơn vị.

Các thao tác cơ bản trên Cây nhị phân

Khởi tạo Cây nhị phân

Tương tự như danh sách liên kết, việc khởi tạo cây nhị phân bao gồm việc tạo các nút trước, sau đó thiết lập các tham chiếu (con trỏ) giữa chúng.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_tree.py

# Khởi tạo cây nhị phân
# Khởi tạo các nút
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
# Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.cpp

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

binary_tree.java

// Khởi tạo các nút
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.cs

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
TreeNode n1 = new(1);
TreeNode n2 = new(2);
TreeNode n3 = new(3);
TreeNode n4 = new(4);
TreeNode n5 = new(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.go

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
n1 := NewTreeNode(1)
n2 := NewTreeNode(2)
n3 := NewTreeNode(3)
n4 := NewTreeNode(4)
n5 := NewTreeNode(5)
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.Left = n2
n1.Right = n3
n2.Left = n4
n2.Right = n5

binary_tree.swift

// Khởi tạo các nút
let n1 = TreeNode(x: 1)
let n2 = TreeNode(x: 2)
let n3 = TreeNode(x: 3)
let n4 = TreeNode(x: 4)
let n5 = TreeNode(x: 5)
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.js

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
let n1 = new TreeNode(1),
    n2 = new TreeNode(2),
    n3 = new TreeNode(3),
    n4 = new TreeNode(4),
    n5 = new TreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.ts

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
let n1 = new TreeNode(1),
    n2 = new TreeNode(2),
    n3 = new TreeNode(3),
    n4 = new TreeNode(4),
    n5 = new TreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.dart

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.rs

// Khởi tạo các nút
let n1 = TreeNode::new(1);
let n2 = TreeNode::new(2);
let n3 = TreeNode::new(3);
let n4 = TreeNode::new(4);
let n5 = TreeNode::new(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.borrow_mut().left = Some(n2.clone());
n1.borrow_mut().right = Some(n3);
n2.borrow_mut().left = Some(n4);
n2.borrow_mut().right = Some(n5);

binary_tree.c

/* Khởi tạo một cây nhị phân */
// Khởi tạo các nút
TreeNode *n1 = newTreeNode(1);
TreeNode *n2 = newTreeNode(2);
TreeNode *n3 = newTreeNode(3);
TreeNode *n4 = newTreeNode(4);
TreeNode *n5 = newTreeNode(5);
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

binary_tree.kt

// Khởi tạo các nút
val n1 = TreeNode(1)
val n2 = TreeNode(2)
val n3 = TreeNode(3)
val n4 = TreeNode(4)
val n5 = TreeNode(5)
// Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.rb

# Khởi tạo cây nhị phân
# Khởi tạo các nút
n1 = TreeNode.new(1)
n2 = TreeNode.new(2)
n3 = TreeNode.new(3)
n4 = TreeNode.new(4)
n5 = TreeNode.new(5)
# Thiết lập liên kết tham chiếu (con trỏ) giữa các nút
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=class%20TreeNode%3A%0A%20%20%20%20%22%22%22%E4%BA%8C%E5%8F%89%E6%A0%91%E8%8A%82%E7%82%B9%E7%B1%BB%22%22%22%0A%20%20%20%20def%20__init__%28self,%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E8%8A%82%E7%82%B9%E5%80%BC%0A%20%20%20%20%20%20%20%20self.left%3A%20TreeNode%20%7C%20None%20%3D%20None%20%20%23%20%E5%B7%A6%E5%AD%90%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%20%20%20%20%20%20%20%20self.right%3A%20TreeNode%20%7C%20None%20%3D%20None%20%23%20%E5%8F%B3%E5%AD%90%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E8%8A%82%E7%82%B9%0A%20%20%20%20n1%20%3D%20TreeNode%28val%3D1%29%0A%20%20%20%20n2%20%3D%20TreeNode%28val%3D2%29%0A%20%20%20%20n3%20%3D%20TreeNode%28val%3D3%29%0A%20%20%20%20n4%20%3D%20TreeNode%28val%3D4%29%0A%20%20%20%20n5%20%3D%20TreeNode%28val%3D5%29%0A%20%20%20%20%23%20%E6%9E%84%E5%BB%BA%E8%8A%82%E7%82%B9%E4%B9%8B%E9%97%B4%E7%9A%84%E5%BC%95%E7%94%A8%EF%BC%88%E6%8C%87%E9%92%88%EF%BC%89%0A%20%20%20%20n1.left%20%3D%20n2%0A%20%20%20%20n1.right%20%3D%20n3%0A%20%20%20%20n2.left%20%3D%20n4%0A%20%20%20%20n2.right%20%3D%20n5&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Chèn và xóa nút

Tương tự như danh sách liên kết, việc chèn và xóa các nút trong cây nhị phân có thể thực hiện được bằng cách sửa đổi con trỏ. Hình dưới đây minh họa một ví dụ.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_tree.py

# Chèn và xóa nút
p = TreeNode(0)
# Chèn nút P vào giữa n1 -> n2
n1.left = p
p.left = n2
# Xóa nút P
n1.left = n2

binary_tree.cpp

/* Chèn và xóa nút */
TreeNode* P = new TreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1->left = P;
P->left = n2;
// Xóa nút P
n1->left = n2;

binary_tree.java

TreeNode P = new TreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1.left = P;
P.left = n2;
// Xóa nút P
n1.left = n2;

binary_tree.cs

/* Chèn và xóa nút */
TreeNode P = new(0);
// Chèn nút P vào giữa n1 và n2
n1.left = P;
P.left = n2;
// Xóa nút P
n1.left = n2;

binary_tree.go

/* Chèn và xóa nút */
// Chèn nút P vào giữa n1 và n2
p := NewTreeNode(0)
n1.Left = p
p.Left = n2
// Xóa nút P
n1.Left = n2

binary_tree.swift

let P = TreeNode(x: 0)
// Chèn nút P vào giữa n1 và n2
n1.left = P
P.left = n2
// Xóa nút P
n1.left = n2

binary_tree.js

/* Chèn và xóa nút */
let P = new TreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1.left = P;
P.left = n2;
// Xóa nút P
n1.left = n2;

binary_tree.ts

/* Chèn và xóa nút */
const P = new TreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1.left = P;
P.left = n2;
// Xóa nút P
n1.left = n2;

binary_tree.dart

/* Chèn và xóa nút */
TreeNode P = new TreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1.left = P;
P.left = n2;
// Xóa nút P
n1.left = n2;

binary_tree.rs

let p = TreeNode::new(0);
// Chèn nút P vào giữa n1 và n2
n1.borrow_mut().left = Some(p.clone());
p.borrow_mut().left = Some(n2.clone());
// Xóa nút P
n1.borrow_mut().left = Some(n2);

binary_tree.c

/* Chèn và xóa nút */
TreeNode *P = newTreeNode(0);
// Chèn nút P vào giữa n1 và n2
n1->left = P;
P->left = n2;
// Xóa nút P
n1->left = n2;

binary_tree.kt

val P = TreeNode(0)
// Chèn nút P vào giữa n1 và n2
n1.left = P
P.left = n2
// Xóa nút P
n1.left = n2

binary_tree.rb

# Chèn và xóa nút
_p = TreeNode.new(0)
# Chèn nút _p vào giữa n1 và n2
n1.left = _p
_p.left = n2
# Xóa nút _p
n1.left = n2

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=class%20TreeNode%3A%0A%20%20%20%20%22%22%22%E4%BA%8C%E5%8F%89%E6%A0%91%E8%8A%82%E7%82%B9%E7%B1%BB%22%22%22%0A%20%20%20%20def%20__init__%28self,%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%E8%8A%82%E7%82%B9%E5%80%BC%0A%20%20%20%20%20%20%20%20self.left%3A%20TreeNode%20%7C%20None%20%3D%20None%20%20%23%20%E5%B7%A6%E5%AD%90%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%20%20%20%20%20%20%20%20self.right%3A%20TreeNode%20%7C%20None%20%3D%20None%20%23%20%E5%8F%B3%E5%AD%90%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E8%8A%82%E7%82%B9%0A%20%20%20%20n1%20%3D%20TreeNode%28val%3D1%29%0A%20%20%20%20n2%20%3D%20TreeNode%28val%3D2%29%0A%20%20%20%20n3%20%3D%20TreeNode%28val%3D3%29%0A%20%20%20%20n4%20%3D%20TreeNode%28val%3D4%29%0A%20%20%20%20n5%20%3D%20TreeNode%28val%3D5%29%0A%20%20%20%20%23%20%E6%9E%84%E5%BB%BA%E8%8A%82%E7%82%B9%E4%B9%8B%E9%97%B4%E7%9A%84%E5%BC%95%E7%94%A8%EF%BC%88%E6%8C%87%E9%92%88%EF%BC%89%0A%20%20%20%20n1.left%20%3D%20n2%0A%20%20%20%20n1.right%20%3D%20n3%0A%20%20%20%20n2.left%20%3D%20n4%0A%20%20%20%20n2.right%20%3D%20n5%0A%0A%20%20%20%20%23%20%E6%8F%92%E5%85%A5%E4%B8%8E%E5%88%A0%E9%99%A4%E8%8A%82%E7%82%B9%0A%20%20%20%20p%20%3D%20TreeNode%280%29%0A%20%20%20%20%23%20%E5%9C%A8%20n1%20-%3E%20n2%20%E4%B8%AD%E9%97%B4%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9%20P%0A%20%20%20%20n1.left%20%3D%20p%0A%20%20%20%20p.left%20%3D%20n2%0A%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E8%8A%82%E7%82%B9%20P%0A%20%20%20%20n1.left%20%3D%20n2&cumulative=false&curInstr=37&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Tip

Hãy lưu ý rằng việc chèn một nút có thể thay đổi cấu trúc logic ban đầu của cây nhị phân, trong khi việc xóa một nút thường kéo theo việc loại bỏ nút đó cùng với toàn bộ cây con của nó. Do đó, trong thực tế, các thao tác chèn và xóa trong cây nhị phân thường được triển khai dưới dạng chuỗi các hoạt động phối hợp để đạt được kết quả mong muốn.

Các loại cây nhị phân phổ biến

Cây nhị phân hoàn hảo

Như được hiển thị trong hình bên dưới, một cây nhị phân hoàn hảo (perfect binary tree) có tất cả các mức được lấp đầy hoàn toàn. Trong cây nhị phân hoàn hảo, các nút lá có bậc bằng \(0\), trong khi tất cả các nút khác có bậc bằng \(2\). Nếu chiều cao của cây là \(h\), tổng số nút sẽ là \(2^{h+1} - 1\), tuân theo mô hình hàm mũ tiêu chuẩn phản ánh hiện tượng phân bào phổ biến trong tự nhiên.

Tip

Xin lưu ý rằng trong cộng đồng tiếng Trung, cây nhị phân hoàn hảo (perfect binary tree) thường được gọi là cây nhị phân đầy đủ (full binary tree).

Cây nhị phân hoàn chỉnh

Như được hiển thị trong hình bên dưới, một cây nhị phân hoàn chỉnh (complete binary tree) chỉ cho phép mức dưới cùng là không được lấp đầy hoàn toàn, và các nút ở mức dưới cùng đó phải được lấp đầy liên tục từ trái qua phải. Lưu ý rằng một cây nhị phân hoàn hảo cũng là một cây nhị phân hoàn chỉnh.

Cây nhị phân đầy đủ

Như được hiển thị trong hình bên dưới, trong một cây nhị phân đầy đủ (full binary tree), tất cả các nút ngoại trừ nút lá đều có hai nút con.

Cây nhị phân cân bằng

Như được hiển thị trong hình bên dưới, trong một cây nhị phân cân bằng (balanced binary tree), chênh lệch tuyệt đối về chiều cao giữa cây con trái và cây con phải của bất kỳ nút nào đều không vượt quá 1.

Sự thoái hóa của Cây nhị phân

Hình dưới đây so sánh cấu trúc lý tưởng và cấu trúc thoái hóa của cây nhị phân. Khi mọi mức đều được lấp đầy, cây trở thành một "cây nhị phân hoàn hảo"; khi tất cả các nút bị lệch về một phía, cây nhị phân sẽ thoái hóa thành một "danh sách liên kết".

• Cây nhị phân hoàn hảo là trường hợp lý tưởng, tận dụng tối đa ưu thế chia để trị của cây nhị phân.
• Danh sách liên kết đại diện cho một thái cực khác, nơi tất cả các thao tác trở thành các thao tác tuyến tính với độ phức tạp thời gian thoái hóa về \(O(n)\).

Như bảng dưới đây hiển thị, trong cấu trúc tốt nhất và tệ nhất, cây nhị phân đạt được các giá trị cực đại hoặc cực tiểu đối với số lượng nút lá, tổng số nút và chiều cao.

Bảng   Cấu trúc tốt nhất và tệ nhất của cây nhị phân

	Cây nhị phân hoàn hảo	Danh sách liên kết
Số lượng nút ở mức \(i\)	\(2^{i-1}\)	\(1\)
Số lượng nút lá của cây có chiều cao \(h\)	\(2^h\)	\(1\)
Tổng số nút của cây có chiều cao \(h\)	\(2^{h+1} - 1\)	\(h + 1\)
Chiều cao của cây có tổng cộng \(n\) nút	\(\log_2 (n+1) - 1\)	\(n - 1\)