C 语言中的二叉树：完整的初学者指南

Informatec Digital »算法» C 语言中的二叉树：初学者完全指南

欢迎阅读本篇关于 C 语言二叉树的综合指南。在本文中，我们将探讨二叉树的基础知识以及如何在 C 编程语言中实现它们。如果您是编程初学者或只是想提高您的 C 语言技能，本指南适合您。

二叉树是计算机科学中的基础数据结构，应用范围非常广泛。理解二叉树的工作原理和实现方法，将有助于你更高效、更优雅地解决复杂问题。

本文将探讨二叉树的基础知识，包括其结构、节点插入和删除、遍历以及元素查找。我们还将提供C 语言的实际示例，以便您了解这些概念在实践中的应用。

让我们开始吧！

什么是二叉树？

二叉树是由相互连接的节点组成的分层数据结构。每个节点最多可以有两个子节点：一个在左边，一个在右边。这种双分支结构是二叉树与其他数据结构的区别所在。

在二叉树中，第一个节点称为根节点。有子节点的节点称为子节点，没有子节点的节点称为叶节点。同一层级的节点称为兄弟节点。

二叉树的好处

二叉树在高效数据存储和搜索方面具有多种优势。一些主要优点包括：

1. 高效搜索二叉树允许在运行时比其他数据结构（例如链表）更快地搜索元素。这是由于树的层次结构及其快速划分数据集的能力。
2. 灵活插入和移除二叉树对于节点插入和删除操作的适应性很强。与数组等静态数据结构不同，二叉树可以动态增长并改变其结构。
3. 层次关系的表示二叉树对于表示元素之间的层次关系特别有用。例如，在文件目录结构中，每个目录可以表示为树中的一个节点，子目录和文件作为其子节点。

二叉树的结构

在深入研究 C 语言中二叉树的实现之前，了解它们的基本结构非常重要。二叉树中的每个节点都包含一个值和对其左子节点和右子节点的引用（如果有）。

下表显示了二叉树中节点的结构：

二进制节点
勇气
左节点
右节点

每个节点可以存储任何类型的数据，例如整数、字符或更复杂的结构。根节点是树的起点，从它我们可以访问所有其他节点。

用 C 实现二叉树

现在我们已经对二叉树有了基本的了解，接下来就该用C 语言实现它们了。接下来，我们将学习如何在 C 语言中声明和使用二叉树结构。

声明二叉树结构

在 C 语言中，我们可以使用结构和指针声明二叉树的结构。以下是该结构的基本声明：

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

在这个结构中， valor 表示存储在节点中的值，并且 izquierdo y derecho 分别是指向左、右子节点的指针。

创建新节点

为了在二叉树中创建一个新节点，我们需要为该节点分配内存并设置其值。以下是创建新节点的 C 函数：

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

功能 malloc 它用于为节点分配动态内存。然后我们设置节点值并返回创建的节点。

插入节点

节点插入是二叉树中的一个基本过程。允许您根据节点值将新元素添加到树的正确位置。下面是将节点插入二叉树的 C 函数：

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

该函数接收指向树根的指针和要插入的节点的值。如果根为空，则表示树为空，我们在根处创建一个新节点。否则，我们将节点的值与根的值进行比较，并决定是否将节点插入到左侧或右侧。

删除节点

删除二叉树中的节点可能稍微复杂一些。这取决于几种情况，例如要删除的节点是否有子节点。下面是一个用于删除二叉树中节点的 C 函数：

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

在此函数中，我们检查节点的值是否小于、大于或等于当前根的值。根据具体情况，我们将采取以下行动：

• 如果值较小，我们就转到树的左边。
• 如果值更大，我们就转到树的右边。
• 如果值相等，我们就找到该节点的最近后继（右子树中最小的节点）并将其替换为当前节点。然后我们从右子树中删除后继。

二叉树的遍历

遍历是允许我们按照特定顺序访问二叉树的所有节点的操作。常见的旅游类型有三种：

中序遍历：先访问左子树，然后访问当前节点，最后访问右子树。以下是一个执行二叉树中序遍历的 C 函数：

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

前序遍历：首先访问当前节点，然后访问左子树，最后访问右子树。以下是一个执行二叉树前序遍历的 C 函数：

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

后序遍历：先访问左子树，然后访问右子树，最后访问当前节点。以下是一个执行二叉树后序遍历的 C 函数：

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

搜索元素

在二叉树中搜索元素可以让我们快速找到数据结构中的特定值。这是一个在二叉树中搜索元素的 C 函数：

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

该函数在二叉树中执行递归搜索。如果当前节点的值等于搜索的值，则返回该节点。否则，根据值搜索左子树或右子树，并重复该过程，直到找到该值或到达空节点。

C 语言中实现二叉树的示例

现在我们已经介绍了二叉树的基础知识以及如何用 C 实现它们，让我们看一些实际的例子。

示例 1：创建二叉树

假设我们要创建一个具有以下值的二叉树：10、5、15、3、7、13、18。以下是我们可以在 C 语言中执行的操作：

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

在此示例中，我们创建一个指向树根的指针，然后使用函数 insertarNodo 将值添加到树中。

示例 2：二叉树的中序遍历

要按顺序打印二叉树的值，我们可以调用该函数 inOrden 如下：

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

本示例将按升序打印树中的值。

常见问题

1.二叉树和二叉搜索树有什么区别？

二叉搜索树 (BST) 是一种特殊类型的二叉树，其中元素的排列方式是较小的值在左边，较大的值在右边。与常规二叉树相比，这可以更有效地搜索元素。

2.二叉树中可以有重复值的节点吗？

是的，二叉树中有可能存在重复值的节点。但是，根据二叉树的实现和具体规则的不同，处理重复节点的方法可能会有所不同。一些实现可能允许重复并以任何顺序存储它们，而其他实现可能要求对重复值进行特殊处理或丢弃。

3. 如何从二叉树中删除特定节点？

要从二叉树中删除特定节点，需要遵循以下步骤：

1. 使用树搜索找到要删除的节点。
2. 考虑不同的消除情况：
   • 如果该节点没有子节点，您可以直接删除它并释放其内存。
   • 如果节点只有一个子节点，则可以用其子节点替换该节点。
   • 如果节点有两个子节点，则必须找到最近的后继节点（右子树中最小的节点），并用后继节点的值替换要删除的节点的值。然后从树中删除后继者。
3. 根据需要调整链接和指针以维持正确的树结构。

4.什么是满二叉树？

满二叉树是一种特殊类型的二叉树，其中除最后一级之外的所有级都被完全填充，并且最后一级的节点位于尽可能靠左的位置。这意味着所有节点都有两个子节点，除了最后一级的节点可能有一个子节点或没有子节点。

5.二叉树的高度是多少？

二叉树的高度是从根到叶的最长路径的长度。换句话说，它是树中的根和任意叶子之间的最大边数。高度以层数来衡量，因此只有一个节点的树的高度为 0，而空树没有高度​​。

6. 我应该在什么时候在程序中使用二叉树？

二叉树在各种情况下都很有用。一些可能使用二叉树的常见情况包括：

• 高效元素查找：如果您需要快速查找数据结构中的元素，二叉树可以提供高效的数据访问。
• 表示层次关系：二叉树非常适合表示层次关系，例如数据库中的目录结构 文件系统.
• 数据排序：您可以使用二叉搜索树对数据进行有效排序，并以对数时间执行搜索、插入和删除。

在决定在程序中使用二叉树之前，请记住评估您的要求并考虑二叉树操作的复杂性。

结论

在本综合指南中，我们探讨了 C 中二叉树的基本概念。我们了解了它们的结构、如何插入和删除节点、执行遍历以及在二叉树中搜索元素。

我们希望本指南能让您对二叉树以及如何在 C 中实现它们有扎实的了解。二叉树是一种多功能且强大的数据结构，可以帮助您解决编程中的各种问题。

请记住使用提供的示例进行练习和试验，以加强您对 C 语言中二叉树的理解。祝您在软件学习和开发之旅中好运！