Cây nhị phân

Khái niệm cơ bản về cây nhị phân

Cây nhị phân là một cấu trúc cây có nhiều nhất hai cây con trên mỗi nút. Thông thường các cây con được gọi là "cây con bên trái" và "cây con bên phải"

Thuộc tính (đặc điểm) của cây nhị phân

Thuộc tính 1: Có nhiều nhất 2 ^ (i-1) nút (i> 0) ở mức thứ i của cây nhị phân. Tính chất 2: Cây nhị phân có độ sâu k có nhiều nhất 2 ^ k-1 nút (k> 0) Tính chất 3: Đối với bất kỳ cây nhị phân nào, nếu số nút lá là N0 và tổng số nút có bậc 2 là N2 thì N0 = N2 + 1; Tính chất 4: Độ sâu của một cây nhị phân hoàn chỉnh có n nút phải là log2 (n + 1) Thuộc tính 5: Đối với một cây nhị phân hoàn chỉnh, nếu được đánh số từ trên xuống dưới và từ trái sang phải, nút được đánh số i, số con bên trái của nó phải là 2i và số con bên phải của nó phải là 2i + 1; Số của cấp độ gốc phải là i / 2 (i = 1 là số gốc, ngoại trừ)

(1) Cây nhị phân hoàn chỉnh-nếu chiều cao của cây nhị phân là h, ngoại trừ lớp thứ h, số nút trong tất cả các lớp khác (1 ～ h-1) đạt đến số lượng lớn nhất và lớp thứ h có các nút lá và lá Các nút được sắp xếp theo thứ tự từ trái sang phải là một cây nhị phân hoàn chỉnh.

(2) Cây nhị phân đầy đủ - mọi nút ngoại trừ các nút lá đều có các lá mầm bên trái và bên phải và các nút lá đều ở dưới cùng của cây nhị phân.

Biểu diễn nút của cây nhị phân và tạo cây

Bằng cách sử dụng ba thuộc tính được định nghĩa trong lớp Node, chúng là giá trị của chính elem, cũng như con bên trái của lchild và con bên phải của lchild

class Node(object):
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

Tạo một cây, tạo một lớp cây và cung cấp một nút gốc gốc, nút này trống ở đầu, sau đó thêm các nút

class Tree(object):
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        node = Node(elem)
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            while queue:
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                elif cur.rchild == None:
                    cur.rchild = node
                    return
                else:
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)