Binary Trees ใน C: คู่มือสำหรับผู้เริ่มต้นใช้งานโดยสมบูรณ์

อินฟอร์เมเทค ดิจิตอล » อัลกอริทึม » Binary Trees ใน 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;
}

ฟังก์ชันนี้รับตัวชี้ไปยังรากของต้นไม้และค่าของโหนดที่ต้องการแทรก หาก root เป็นค่าว่าง แสดงว่าต้นไม้ว่างเปล่า และเราจะสร้างโหนดใหม่ที่ root มิฉะนั้น เราจะเปรียบเทียบค่าของโหนดกับค่าของรูทและตัดสินใจว่าจะแทรกโหนดไปทางซ้ายหรือขวา

การลบโหนด

การลบโหนดในไบนารีทรีอาจซับซ้อนกว่าเล็กน้อย ขึ้นอยู่กับหลายกรณี เช่น โหนดที่ต้องการลบมีโหนดย่อยหรือไม่ ด้านล่างนี้เป็นฟังก์ชัน 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;
}

ในฟังก์ชั่นนี้ เราจะตรวจสอบว่าค่าของโหนดมีค่าน้อยกว่า มากกว่า หรือเท่ากับค่าของรูทปัจจุบันหรือไม่ เราดำเนินการดังต่อไปนี้ตามกรณี:

• ถ้าค่าน้อยกว่าเราจะไปทางซ้ายของต้นไม้
• ถ้าค่ามากกว่าเราจะไปทางขวาของต้นไม้
• หากค่าเท่ากัน เราจะค้นหาโหนดที่ใกล้เคียงที่สุด (โหนดที่เล็กที่สุดในซับทรีทางขวา) และแทนที่ด้วยโหนดปัจจุบัน จากนั้นเราลบตัวสืบทอดจากซับทรีทางขวา

การท่องไปในไบนารีทรี

การทราเวอร์สคือการดำเนินการที่ให้เราสามารถเยี่ยมชมโหนดทั้งหมดในไบนารีทรีตามลำดับที่กำหนด ทัวร์มีอยู่สามประเภททั่วไป:

การท่องต้นไม้แบบเรียงลำดับ (In-order traversal ): จะท่องต้นไม้ย่อยด้านซ้ายก่อน จากนั้นจึงท่องโหนดปัจจุบัน และสุดท้ายจึงท่องต้นไม้ย่อยด้านขวา นี่คือฟังก์ชันภาษา C ที่ทำการท่องต้นไม้ไบนารีแบบเรียงลำดับ:

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

การท่องต้นไม้แบบ Pre-order : จะเยี่ยมชมโหนดปัจจุบันก่อน จากนั้นจึงเยี่ยมชมซับทรีด้านซ้าย และสุดท้ายจึงเยี่ยมชมซับทรีด้านขวา นี่คือฟังก์ชันภาษา C ที่ทำการท่องต้นไม้แบบ Pre-order บนต้นไม้ไบนารี:

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

การท่องต้นไม้แบบโพสต์ ออร์เดอร์ (Post-order traversal ): จะท่องไปที่ซับทรีด้านซ้ายก่อน จากนั้นจึงท่องไปที่ซับทรีด้านขวา และสุดท้ายจึงท่องไปที่โหนดปัจจุบัน นี่คือฟังก์ชันภาษาซีที่ทำการท่องต้นไม้แบบไบนารีด้วยวิธีการโพสต์ออร์เดอร์:

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. ความแตกต่างระหว่างไบนารีทรีและไบนารีเสิร์ชทรีคืออะไร?

Binary search tree (BST) เป็น Binary search tree ประเภทพิเศษซึ่งองค์ประกอบต่างๆ จะถูกจัดเรียงโดยค่าที่น้อยกว่าจะอยู่ทางด้านซ้าย และค่าที่มากกว่าจะอยู่ทางด้านขวา วิธีนี้ช่วยให้การค้นหาองค์ประกอบมีประสิทธิภาพมากขึ้นเมื่อเทียบกับไบนารีทรีปกติ

2. ฉันสามารถมีโหนดที่มีค่าซ้ำกันในไบนารีทรีได้หรือไม่

ใช่ เป็นไปได้ที่จะมีโหนดที่มีค่าซ้ำกันในไบนารีทรี อย่างไรก็ตาม ขึ้นอยู่กับการใช้งานและกฎเฉพาะของไบนารีทรี อาจมีวิธีที่แตกต่างกันในการจัดการกับโหนดที่ซ้ำกัน การใช้งานบางอย่างอาจอนุญาตให้มีข้อมูลซ้ำกันได้และจัดเก็บไว้ในลำดับใดก็ได้ ในขณะที่บางกรณีอาจกำหนดให้จัดการค่าซ้ำกันเป็นพิเศษหรือทิ้งไป

3. ฉันจะลบโหนดเฉพาะออกจากไบนารีทรีได้อย่างไร

หากต้องการลบโหนดเฉพาะออกจากไบนารีทรี คุณต้องทำตามขั้นตอนเหล่านี้:

1. ค้นหาโหนดที่คุณต้องการลบโดยใช้การค้นหาแบบต้นไม้
2. พิจารณาตัวอย่างการกำจัดที่แตกต่างกัน:
   • หากโหนดไม่มีโหนดย่อย คุณก็สามารถลบโหนดนั้นและปลดปล่อยหน่วยความจำได้
   • หากโหนดมีโหนดย่อยเพียงโหนดเดียว คุณสามารถแทนที่โหนดด้วยโหนดย่อยของโหนดนั้นได้
   • หากโหนดมีโหนดย่อยสองโหนด คุณจะต้องค้นหาตัวสืบทอดที่ใกล้ที่สุด (โหนดที่เล็กที่สุดในซับทรีทางขวา) และแทนที่ค่าของโหนดที่ต้องการลบด้วยค่าของตัวสืบทอด จากนั้นเอาตัวสืบทอดออกจากต้นไม้
3. ปรับเปลี่ยนลิงก์และตัวชี้ตามต้องการเพื่อรักษาโครงสร้างแบบต้นไม้ที่ถูกต้อง

4. ฟูลไบนารีทรีคืออะไร?

ต้นไม้ไบนารีแบบเต็มคือต้นไม้ไบนารีประเภทพิเศษซึ่งระดับทั้งหมด ยกเว้นระดับสุดท้าย จะถูกเติมเต็มอย่างสมบูรณ์ และโหนดของระดับสุดท้ายจะตั้งอยู่ทางด้านซ้ายสุดเท่าที่จะเป็นไปได้ ซึ่งหมายความว่าโหนดทั้งหมดจะมีโหนดลูกสองโหนด ยกเว้นโหนดในระดับสุดท้ายซึ่งอาจมีโหนดลูกหนึ่งโหนดหรือไม่มีเลยก็ได้

5. ความสูงของต้นไม้ไบนารีคือเท่าใด

ความสูงของต้นไม้แบบไบนารีคือความยาวของเส้นทางที่ยาวที่สุดจากรากถึงใบ กล่าวอีกนัยหนึ่ง มันคือจำนวนขอบสูงสุดระหว่างรากและใบใด ๆ ในต้นไม้ ความสูงจะวัดจากจำนวนระดับ ดังนั้น ต้นไม้ที่มีโหนดเดียวจะมีความสูงเท่ากับ 0 และต้นไม้ว่างจะไม่มีความสูง

6. ฉันควรใช้ไบนารีทรีในโปรแกรมของฉันเมื่อใด?

ต้นไม้ไบนารีมีประโยชน์ในสถานการณ์ต่างๆ มากมาย กรณีทั่วไปบางกรณีที่คุณอาจใช้ไบนารีทรีได้แก่:

• การค้นหาองค์ประกอบที่มีประสิทธิภาพ: หากคุณต้องการค้นหาองค์ประกอบในโครงสร้างข้อมูลอย่างรวดเร็ว ต้นไม้แบบไบนารีสามารถให้การเข้าถึงข้อมูลที่มีประสิทธิภาพได้
• การแสดงความสัมพันธ์แบบลำดับชั้น: ต้นไม้แบบไบนารีเหมาะอย่างยิ่งสำหรับการแสดงความสัมพันธ์แบบลำดับชั้น เช่น โครงสร้างไดเร็กทอรีใน ระบบไฟล์.
• การเรียงลำดับข้อมูล: คุณสามารถใช้ไบนารี่ทรีในการเรียงลำดับข้อมูลอย่างมีประสิทธิภาพ และดำเนินการค้นหา แทรก และลบในเวลาลอการิทึม

อย่าลืมประเมินความต้องการของคุณและพิจารณาความซับซ้อนของการดำเนินการบนไบนารีทรีก่อนตัดสินใจใช้ในโปรแกรมของคุณ

ข้อสรุป

ในคู่มือที่ครอบคลุมนี้ เราได้สำรวจแนวคิดพื้นฐานของไบนารีทรีในภาษา C เราได้เรียนรู้เกี่ยวกับโครงสร้าง การแทรกและลบโหนด การสืบค้น และการค้นหาองค์ประกอบในไบนารีทรี

เราหวังว่าคู่มือนี้จะทำให้คุณเข้าใจไบนารีทรีได้ดีขึ้น รวมไปถึงวิธีนำไปใช้ในภาษา C ไบนารีทรีเป็นโครงสร้างข้อมูลอเนกประสงค์และทรงพลังที่จะช่วยคุณแก้ปัญหาด้านการเขียนโปรแกรมได้หลากหลาย

อย่าลืมฝึกฝนและทดลองใช้ตัวอย่างที่ให้มาเพื่อเสริมความเข้าใจของคุณเกี่ยวกับไบนารีทรีในภาษา C ขอให้โชคดีกับการเรียนรู้และพัฒนาซอฟต์แวร์!