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

0 Обзор

Прежде чем мы поговорим о бинарных деревьях, давайте посмотрим, что такое дерево. Основной единицей дерева является узел, а связи между узлами называются ветвями. Верхний узел дерева называется корневым узлом, а нижние узлы — дочерними узлами. Узел может иметь 0 или более дочерних узлов, а узел без дочерних узлов называется листовым узлом.

Бинарное дерево — это дерево с не более чем 2 дочерними узлами, это очень классическая структура данных. Двоичное дерево поиска (BST) — это упорядоченное двоичное дерево, и BST должно соответствовать следующим условиям:

• Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
• Если правое поддерево любого узла не пусто, то значения всех узлов в правом поддереве равныбольше или равноЗначение его корневого узла; (некоторые книги определяют, что BST не может иметь один и тот же узел значения, в этой статье тот же узел значения вставляется в правое поддерево)
• Левое и правое поддеревья любого узла также являются соответственно бинарными деревьями поиска;

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

1 Определение

Сначала мы определяем узел бинарного дерева следующим образом:

typedef struct BTNode {
    int value;
    struct BTNode *left;
    struct BTNode *right;
} BTNode;

вvalueхранить стоимость,leftиrightУказатели указывают на левый и правый дочерние узлы соответственно. Бинарное дерево поиска может использовать ту же структуру, что и бинарное дерево, но отличается при вставке или поиске.

2 Основные операции

Далее посмотрите на некоторые основные операции двоичных и двоичных деревьев, включая узлы вставки BST, узлы поиска BST, BST-максимальные и минимальные значения, точки бифурта. Двоичный вид дерева (BST) Уникальная операция добавляется до функцииbstРазличие префиксов, другие функции являются общими для бинарных деревьев.

1) Создайте узел

Выделите память и инициализируйте значение.

/**
 * 创建BTNode
 */
BTNode *newNode(int value)
{
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

2) узел вставки BST

Узел вставки может быть реализован рекурсивно или нерекурсивно.Если вставляемое значение больше значения корневого узла, оно вставляется в правое поддерево, в противном случае - в левое поддерево. Как показано на следующем рисунке (рисунки из ссылок 1, 2, 3):

/**
 * BST中插入值，递归方法
 */
/**
 * BST中插入结点，递归方法
 */
BTNode *bstInsert(BTNode *root, int value)
{
    if (!root)
        return newNode(value);

    if (root->value > value) {
        root->left = bstInsert(root->left, value);
    } else {
        root->right = bstInsert(root->right, value);
    }
    return root;
}

/**
 * BST中插入结点，非递归方法
 */
BTNode *bstInsertIter(BTNode *root, int value)
{
    BTNode *node = newNode(value);

    if (!root)
        return node;

    BTNode *current = root, *parent = NULL;

    while (current) {
        parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }

    if (parent->value >= value)
        parent->left = node;
    else
        parent->right = node;

    return root;
}

3) Узел удаления BST

Удалить узлы немного сложно, рассмотрим 3 случая:

• Это листовой узел, который легко удалить, удалить узел и поместить родительский узел листового узла.leftилиrightУказатель можно оставить пустым.

• Если удаленный узел имеет два дочерних узла, вам необходимо найти самый большой узел левого поддерева узла (используя следующуюbstSearchIterфункция) и замените его значение на удаляемый узел, а затем рекурсивно вызовите функцию удаления, чтобы удалить самый большой узел в левом поддереве узла.

• Удаленный узел имеет только один узел для детей, затем удалите узел и заполняют значение своего ребенка в удаленном узле (необходимо судить, является ли это левый ребенок или правый узел для детей).

/**
 * BST中删除结点
 */
BTNode *bstDelete(BTNode *root, int value)
{
    BTNode *parent = NULL, *current = root;
    BTNode *node = bstSearchIter(root, &parent, value);
    if (!node) {
        printf("Value not found\n");
        return root;
    }

    if (!node->left && !node->right) {
        // 情况1：待删除结点是叶子结点
        if (node != root) {
            if (parent->left == node) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        } else {
            root = NULL;
        }
        free(node);
    } else if (node->left && node->right) {
        // 情况2：待删除结点有两个子结点
        BTNode *predecessor = bstMax(node->left);
        bstDelete(root, predecessor->value);
        node->value = predecessor->value;
    } else {
        // 情况3：待删除结点只有一个子结点
        BTNode *child = (node->left) ? node->left : node->right;
        if (node != root) {
            if (node == parent->left)
                parent->left = child;
            else
                parent->right = child;
        } else {
            root = child;
        }
        free(node);
    }
    return root;
}

4) BST найти узел

Обратите внимание, что родительские узлы также записываются при нерекурсивном поиске.

/**
 * BST查找结点-递归
 */
BTNode *bstSearch(BTNode *root, int value)
{
    if (!root) return NULL; 

    if (root->value == value) {
        return root;
    } else if (root->value > value) {
        return bstSearch(root->left, value);
    } else {
        return bstSearch(root->left, value);
    }
}

/**
 * BST查找结点-非递归
 */
BTNode *bstSearchIter(BTNode *root, BTNode **parent, int value)
{
    if (!root) return NULL;

    BTNode *current = root;

    while (current && current->value != value) {
        *parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }

    return current;
}

5) Минимальный узел BST и максимальный узел

Минимальный узел ищется рекурсивно из левого поддерева, а максимальный узел ищется рекурсивно из правого поддерева.

/**
 * BST最小值结点
 */
BTNode *bstMin(BTNode *root)
{
    if (!root->left)
        return root;

    return bstMin(root->left);
}

/**
 * BST最大值结点
 */
BTNode *bstMax(BTNode *root)
{
    if (!root->right)
        return root;

    return bstMax(root->right);
}

6) Количество и высота узлов бинарного дерева

/**
 * 二叉树结点数目
 */
int btSize(BTNode *root)
{
    if (!root) return 0;
    
    return btSize(root->left) + btSize(root->right) + 1;
}

/**
 * 二叉树高度
 */
int btHeight(BTNode *root)
{
    if (!root) return 0;

    int leftHeight = btHeight(root->left);
    int rightHeight = btHeight(root->right);
    int maxHeight = leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    return maxHeight;
}

3 Обход бинарного дерева

Рекурсивный обход - предварительный порядок, порядок, порядок следования, порядок слоев

Рекурсивная реализация обхода бинарного дерева относительно проста, и код дается напрямую. Здесь стоит упомянуть об обходе по уровням.Сначала вычисляется высота бинарного дерева, а затем вызывается вспомогательная функция для обхода узлов каждого слоя по очереди.Этот метод проще для понимания, хотя время сложность будет выше.

/**
 * 二叉树先序遍历
 */
void preOrder(BTNode *root)
{
    if (!root) return;

    printf("%d ", root->value);
    preOrder(root->left);
    preOrder(root->right);
}

/**
 * 二叉树中序遍历
 */
void inOrder(BTNode *root)
{
    if (!root) return;

    inOrder(root->left);
    printf("%d ", root->value);
    inOrder(root->right);
}

/**
 * 二叉树后序遍历
 */
void postOrder(BTNode *root)
{
    if (!root) return;

    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->value);
}

/**
 * 二叉树层序遍历
 */
void levelOrder(BTNode *root)
{
    int btHeight = height(root);    
    int level;
    for (level = 1; level <= btHeight; level++) {
        levelOrderInLevel(root, level);
    }
}

/**
 * 二叉树层序遍历辅助函数-打印第level层的结点
 */
void levelOrderInLevel(BTNode *root, int level)
{
    if (!root) return;

    if (level == 1) {
        printf("%d ", root->value);
        return;
    }
    levelOrderInLevel(root->left, level-1);
    levelOrderInLevel(root->right, level-1);
}

Нерекурсивный обход - предварительный порядок, порядок, порядок следования, порядок слоев

• При нерешительном прохождении прохождение предзаказ является простым. Используйте стек, чтобы сохранить узлы, сначала посетите корневой узел, затем выталкивайте правильный ребенок и левый ребенок на стек, и затем петлю этот процесс. Обход в заказа немного сложнее. Он должен сначала пройти левое поддель, а затем корневой узел, и, наконец, правый поддель.
• Обход после заказа с использованием метода стекаpostOrderIter()Это будет немного запутанно и подвержено ошибкам. Поэтому во время собеседования рекомендуется использовать вариант с двумя стеками.postOrderIterWith2Stack(), легче понять и легче написать.
• Обход по уровням использует очередь для хранения узлов, что довольно просто.
• Здесь я дополнительно реализую очередьBTNodeQueueи стекBTNodeStackИспользуется для нерекурсивного обхода бинарного дерева.

/*********************/
/** 二叉树遍历-非递归 **/
/*********************/
/**
 * 先序遍历-非递归
 */
void preOrderIter(BTNode *root)
{
    if (!root) return;

    int size = btSize(root);
    BTNodeStack *stack = stackNew(size);

    push(stack, root);
    while (!IS_EMPTY(stack)) {
        BTNode *node = pop(stack);
        printf("%d ", node->value);

        if (node->right)
            push(stack, node->right);

        if (node->left)
            push(stack, node->left);
    }
    free(stack);
}

/**
 * 中序遍历-非递归
 */
void inOrderIter(BTNode *root)
{
    if (!root) return;

    BTNodeStack *stack = stackNew(btSize(root));

    BTNode *current = root;
    while (current || !IS_EMPTY(stack)) {
        if (current) {
            push(stack, current);
            current = current->left;
        } else {
            BTNode *node = pop(stack);
            printf("%d ", node->value);
            current = node->right;
        }
    }
    free(stack);
}

/**
 * 后续遍历-使用一个栈非递归
 */
void postOrderIter(BTNode *root)
{
    BTNodeStack *stack = stackNew(btSize(root));
    BTNode *current = root;
    do { 
        // 移动至最左边结点
        while (current) { 
            // 将该结点右孩子和自己入栈
            if (current->right) 
                push(stack, current->right); 
            push(stack, current); 
  
            // 往左子树遍历
            current = current->left; 
        } 
  
        current = pop(stack); 
  
        if (current->right && peek(stack) == current->right) { 
            pop(stack);
            push(stack, current);
            current = current->right;
        } else { 
            printf("%d ", current->value); 
            current = NULL; 
        } 
    } while (!IS_EMPTY(stack)); 
}

/**
 * 后续遍历-使用两个栈，更好理解一点。
 */
void postOrderIterWith2Stack(BTNode *root)
{
    if (!root) return;

    BTNodeStack *stack = stackNew(btSize(root));
    BTNodeStack *output = stackNew(btSize(root));

    push(stack, root);
    BTNode *node;

    while (!IS_EMPTY(stack)) {
        node = pop(stack);
        push(output, node);

        if (node->left)
            push(stack, node->left);

        if (node->right)
            push(stack, node->right);
    }

    while (!IS_EMPTY(output)) {
        node = pop(output);
        printf("%d ", node->value);
    }
}

/**
 * 层序遍历-非递归
 */
void levelOrderIter(BTNode *root)
{
    if (!root) return;

    BTNodeQueue *queue = queueNew(btSize(root));
    enqueue(queue, root);

    while (1) {
        int nodeCount = QUEUE_SIZE(queue);
        if (nodeCount == 0)
            break;
btHeight
        while (nodeCount > 0) {
            BTNode *node = dequeue(queue);
            printf("%d ", node->value);

            if (node->left)
                enqueue(queue, node->left);

            if (node->right)
                enqueue(queue, node->right);

            nodeCount--;
        }
        printf("\n");
    }
}

использованная литература

• woohoo.techie joy.com/insertion-i…
• woohoo.techie delicious.com/search-give…
• woohoo.techie Delection.com/deletion — вставьте…
• Woohoo. geek для гиков — это .org/print-level…
• woohoo. Компьютерщик для компьютерщиков .org/iterative-afraid…
• woohoo. Компьютерщик для компьютерщиков .org/iterative-afraid…