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。

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;
}

本範例將以升序列印樹中的值。

Preguntas frecuentes

1.二元樹和二元搜尋樹有什麼差別？

二元搜尋樹 (BST) 是一種特殊類型的二元樹，其中元素的排列方式是較小的值在左邊，較大的值在右邊。與常規二元樹相比，這可以更有效地搜尋元素。

2.二叉樹中可以有重複值的節點嗎？

是的，二元樹中有可能存在重複值的節點。但是，根據二元樹的實作和具體規則的不同，處理重複節點的方法可能會有所不同。一些實作可能允許重複並以任何順序儲存它們，而其他實作可能要求對重複值進行特殊處理或丟棄。

3. 如何從二元樹中刪除特定節點？

要從二元樹中刪除特定節點，需要遵循以下步驟：

1. 使用樹搜尋找到要刪除的節點。
2. 考慮不同的消除情況：
   • 如果該節點沒有子節點，您可以直接刪除它並釋放其記憶體。
   • 如果節點只有一個子節點，則可以用其子節點取代該節點。
   • 如果節點有兩個子節點，則必須找到最近的後繼節點（右子樹中最小的節點），並用後繼節點的值取代要刪除的節點的值。然後從樹中刪除後繼者。
3. 根據需要調整連結和指針以維持正確的樹狀結構。

4.什麼是滿二叉樹？

滿二叉樹是一種特殊類型的二元樹，其中除最後一級之外的所有級都被完全填充，並且最後一級的節點位於盡可能靠左的位置。這意味著所有節點都有兩個子節點，除了最後一層的節點可能有一個子節點或沒有子節點。

5.二元樹的高度是多少？

二元樹的高度是從根到葉的最長路徑的長度。換句話說，它是樹中的根和任意葉子之間的最大邊數。高度以層數來衡量，因此只有一個節點的樹的高度為 0，而空樹沒有高度。

6. 我應該在什麼時候在程式中使用二元樹？

二叉樹在各種情況下都很有用。一些可能使用二元樹的常見情況包括：

• 高效元素查找：如果您需要快速查找資料結構中的元素，二叉樹可以提供高效率的資料存取。
• 表示層次關係：二元樹非常適合表示層次關係，例如資料庫中的目錄結構 文件系統.
• 資料排序：您可以使用二元搜尋樹對資料進行有效排序，並以對數時間執行搜尋、插入和刪除。

在決定在程式中使用二元樹之前，請記住評估您的要求並考慮二元樹操作的複雜性。

結論

在本綜合指南中，我們探討了 C 中二元樹的基本概念。

我們希望本指南能讓您對二元樹以及如何在 C 中實現它們有紮實的了解。

請記住使用提供的範例進行練習和試驗，以加強您對 C 語言中二叉樹的理解。