İkili ağac (binary tree) — hər düyünün ən çox iki uşağı olan ağacdır: sol və sağ. İkili ağaclar axtarış ağaclarının, yığınların və ifadə ağaclarının əsasıdır. Ümumi ağacın terminlərini və gəzmələrini əvvəlki mövzuda gördük; indi ikili ağacı reallaşdırır və xassələrini araşdırırıq.

Üç ikili ağac növü: full, complete və perfect
Üç ikili ağac növü: full, complete və perfect

Düyün sinfi və in-order

Hər düyündə value, left və right var; olmayan uşaq None-dur. In-order gəzmə: sol alt ağac, düyün, sağ alt ağac. Bu, yalnız ikili ağacda mümkündür və ikili axtarış ağacında dəyərləri sıralı verəcək.

python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def sample():
    return Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

print(inorder(sample()))
text
[4, 2, 5, 1, 3, 6]

Hündürlük, düyün sayı, diametr

Boş ağacın hündürlüyünü -1 qəbul edirik: onda yarpaq 1 + max(-1, -1) = 0 olur. Diametr — ağacdakı ən uzun yolun kənar sayıdır. Hər düyündən keçən ən uzun yol sol hündürlük + sağ hündürlük + 2 (hündürlük -1 qəbulu ilə). Bir keçiddə hesablanır, O(n).

python
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)

def diameter(root):
    best = 0