Обзор

• предисловие
• что такое дерево
• Что такое бинарное дерево
• глубина первая
• сначала в ширину
• постскриптум

предисловие

Ранее я упоминал, что алгоритмом злоупотребляли, на этот раз я уберу его. Вставай с того места, где ты упал. Это небольшая заметка, когда я рассмотрел алгоритм и структуру данных, я выложу ее здесь, а также проверю старые точки знаний, чтобы все проверили и восполнили пробелы.Если моя статья будет вам полезна, подпишитесь, поставьте лайк и перешлите ее, чтобы у меня было больше мотивации делиться оригинальными публикациями.

что такое дерево

В информатике,Дерево(английский: дерево) — это абстрактный тип данных (ADT) или структура данных, которая реализует этот абстрактный тип данных и используется для моделирования набора данных с древовидной структурой. Он состоит из n (n>0) конечных узлов, образующих набор с иерархическими отношениями.

особенности дерева

• каждый узел имеет ноль или более дочерних узлов;
• Узел без родительского узла называется корневым узлом;
• Каждый некорневой узел имеет один и только один родительский узел;
• За исключением корневого узла, каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев.

срок

• Степень узла: количество поддеревьев, содержащихся в узле, называется степенью узла;
• Степень дерева: В дереве степень наибольшего узла называется степенью дерева;
• Листовые узлы или конечные узлы: узлы с нулевой степенью;
• Нетерминальные узлы или узлы ветвления: узлы, степень которых не равна нулю;
• Родительский узел или родительский узел: если узел содержит дочерние узлы, этот узел называется родительским узлом своих дочерних узлов;
• Дочерний узел или дочерний узел: корневой узел поддерева, содержащегося в узле, называется дочерним узлом узла;
• Братские узлы: узлы с одним и тем же родительским узлом называются родственными узлами;
• Уровень узлов: начиная с определения корня, корень — это первый слой, дочерние узлы корня — это второй слой и так далее;
• Глубина: для любого узла n глубина n — это длина уникального пути от корня к n, а глубина корня равна 0;
• Высота: для любого узла n высота n — это длина самого длинного пути от n до листа, а высота всех листьев равна 0;
• Двоюродный узел: узлы, чьи родительские узлы находятся в одном слое, являются двоюродными братьями друг друга;
• Предки узла: все узлы на ветке от корня до узла;
• Потомки: любой узел в поддереве с корнем в узле называется потомком узла.
• Лес: совокупность m (m>=0) непересекающихся деревьев называется лесом;

Что такое бинарное дерево

бинарное дерево: дерево с не более чем двумя поддеревьями на узел называется бинарным деревом;полное бинарное дерево: Для бинарного дерева предполагается, что его глубина равна d (d>1). За исключением d-го слоя, количество узлов в других слоях достигло максимального значения, а все узлы d-го слоя тесно расположены непрерывно слева направо, такое бинарное дерево называется полным бинарным деревом ;

полное бинарное дерево: полное бинарное дерево со всеми листовыми узлами внизу;

глубина первая

Обход в глубину заключается в том, чтобы сначала пройти по бинарному дереву по глубине, в том числе:

обход предварительного заказа
Порядок обхода -> корневой узел -> левое поддерево -> правое поддерево

Неупорядоченный обход
Порядок обхода -> левое поддерево -> корневой узел -> правое поддерево

пост-порядковый обход
Порядок обхода --> левое поддерево -> правое поддерево -> корневой узел

Сначала определите TreeNode:

class TreeNode:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

Создайте экземпляр TreeNode:

node1 = TreeNode("A",
                 TreeNode("B",
                          TreeNode("D"),
                          TreeNode("E")
                          ),
                 TreeNode("C",
                          TreeNode("F"),
                          TreeNode("G")
                          )
                 )

обход предварительного заказа

def preTraverse(root):
    if root is None:
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)

результат операции:

A
B
D
E
C
F
G

Неупорядоченный обход

def midTraverse(root):
    if root is None:
        return
    midTraverse(root.left)
    print(root.value)
    midTraverse(root.right)

результат операции:

D
B
E
A
F
C
G

пост-порядковый обход

def afterTraverse(root):
    if root is None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)

результат операции:

D
E
B
F
G
C
A

сначала в ширину

Обход в ширину — это иерархический обход, который выполняется слой за слоем.

def levelOrder(root):
    # write your code here
    res = []
    # 如果根节点为空，则返回空列表
    if root is None:
        return res
    # 模拟一个队列储存节点
    q = []
    # 首先将根节点入队
    q.append(root)
    # 列表为空时，循环终止
    while len(q) != 0:
        length = len(q)
        for i in range(length):
            # 将同层节点依次出队
            r = q.pop(0)
            if r.left is not None:
                # 非空左孩子入队
                q.append(r.left)
            if r.right is not None:
                # 非空右孩子入队
                q.append(r.right)
            res.append(r.value)
            print(r.value)
    return res

результат операции:

A
B
C
D
E
F
G

постскриптум

Этот обзор здесь первый. Давайте ныть здесь, структура данных и расчет очень важны. Реализация многих вещей необходима для структуры данных и алгоритма. Например, реализация mysql использует дерево B +. Если мы поймем принцип, это значительно улучшит производительность базы данных. Помогите . Еще одним важным моментом является то, что алгоритмы и структуры данных определенно незаменимы для собеседований на крупных фабриках. Хотите попасть на большой завод? Или послушно выучить алгоритм.

Эта статья была впервые опубликована в общедоступной учетной записи «zone7». Подпишитесь на общедоступную учетную запись, чтобы получать последние твиты, и отвечайте на [Индекс национального дня] в фоновом режиме, чтобы получить исходный код.