ไบนารีทรีในซี
ในซี, ก ต้นไม้ไบนารี เป็นอินสแตนซ์ของโครงสร้างข้อมูลแบบต้นไม้ที่มีโหนดหลักซึ่งอาจมีโหนดย่อยได้สูงสุดสองโหนด 0, 1 หรือ 2 โหนดลูกหลาน ทุก ๆ โหนดในไฟล์ ต้นไม้ไบนารี มีค่าของตัวเองและตัวชี้สองตัวสำหรับลูกของมัน ตัวชี้หนึ่งตัวสำหรับลูกด้านซ้ายและอีกตัวสำหรับลูกด้านขวา
การประกาศไบนารีทรี
ก ต้นไม้ไบนารี สามารถประกาศในภาษาซีโดยใช้วัตถุที่เรียกว่า โครงสร้าง ที่แสดงโหนดหนึ่งในต้นไม้
โครงสร้าง โหนด {
ชนิดข้อมูล var_name ;
โครงสร้าง โหนด * ซ้าย ;
โครงสร้าง โหนด * ขวา ;
} ;
ด้านบนเป็นประกาศของหนึ่ง ต้นไม้ไบนารี ชื่อโหนดเป็นโหนด มันมีสามค่า; หนึ่งคือตัวแปรเก็บข้อมูลและอีกสองตัวเป็นตัวชี้ไปยังลูก (ชายด์ซ้ายและขวาของโหนดพาเรนต์)
ข้อเท็จจริงของไบนารีทรี
แม้แต่ชุดข้อมูลขนาดใหญ่ การใช้ a ต้นไม้ไบนารี ช่วยให้ค้นหาได้ง่ายและรวดเร็วขึ้น ไม่จำกัดจำนวนกิ่งของต้นไม้ ตรงกันข้ามกับอาร์เรย์ ต้นไม้ชนิดใดก็ได้ที่สามารถสร้างขึ้นและเพิ่มขึ้นตามความต้องการของแต่ละคน
การใช้งานไบนารีทรีในซี
ต่อไปนี้เป็นคำแนะนำทีละขั้นตอนในการดำเนินการ ไบนารี่ทรี ในซี
ขั้นตอนที่ 1: ประกาศแผนผังการค้นหาแบบไบนารี
สร้างโหนดโครงสร้างที่มีข้อมูลสามประเภท เช่น ข้อมูล *left_child และ *right_child โดยที่ข้อมูลสามารถเป็นประเภทจำนวนเต็มได้ และทั้งโหนด *left_child และ *right_child สามารถประกาศเป็น NULL หรือไม่ก็ได้
โครงสร้าง โหนด{
นานาชาติ ข้อมูล ;
โครงสร้าง โหนด * right_child ;
โครงสร้าง โหนด * left_child ;
} ;
ขั้นตอนที่ 2: สร้างโหนดใหม่ใน Binary Search Tree
สร้างโหนดใหม่โดยสร้างฟังก์ชันที่ยอมรับจำนวนเต็มเป็นอาร์กิวเมนต์ และให้ตัวชี้ไปยังโหนดใหม่ที่สร้างขึ้นด้วยค่านั้น ใช้ฟังก์ชัน malloc() ใน C สำหรับการจัดสรรหน่วยความจำแบบไดนามิกสำหรับโหนดที่สร้างขึ้น เริ่มต้นลูกซ้ายและขวาเป็น NULL และส่งคืน nodeName
โครงสร้าง โหนด * สร้าง ( ข้อมูลประเภทข้อมูล )
{
โครงสร้าง โหนด * ชื่อโหนด = มัลลอค ( ขนาดของ ( โครงสร้าง โหนด ) ) ;
ชื่อโหนด -> ข้อมูล = ค่า ;
ชื่อโหนด -> left_child = ชื่อโหนด -> right_child = โมฆะ ;
กลับ ชื่อโหนด ;
}
ขั้นตอนที่ 3: ใส่ Childs ขวาและซ้ายใน Binary Tree
สร้างฟังก์ชัน insert_left และ insert_right ที่จะรับสองอินพุต ซึ่งเป็นค่าที่จะแทรกและตัวชี้ไปยังโหนดที่จะเชื่อมต่อลูกทั้งสอง เรียกฟังก์ชัน create เพื่อสร้างโหนดใหม่และกำหนดตัวชี้ที่ส่งคืนให้กับตัวชี้ด้านซ้ายของลูกด้านซ้ายหรือตัวชี้ด้านขวาของลูกด้านขวาของพาเรนต์หลัก
โครงสร้าง โหนด * แทรก_ซ้าย ( โครงสร้าง โหนด * ราก , ข้อมูลประเภทข้อมูล ) {ราก -> ซ้าย = สร้าง ( ข้อมูล ) ;
กลับ ราก -> ซ้าย ;
}
โครงสร้าง โหนด * แทรก_ขวา ( โครงสร้าง โหนด * ราก , ข้อมูลประเภทข้อมูล ) {
ราก -> ขวา = สร้าง ( ข้อมูล ) ;
กลับ ราก -> ขวา ;
}
ขั้นตอนที่ 4: แสดงโหนดของ Binary Tree โดยใช้วิธี Traversal
เราสามารถแสดงต้นไม้โดยใช้วิธีการสำรวจสามวิธีใน C วิธีการสำรวจเหล่านี้คือ:
1: การผ่านคำสั่งซื้อล่วงหน้า
ในวิธีการสำรวจนี้ เราจะผ่านโหนดในทิศทางจาก parent_node->left_child->right_child .
เป็นโมฆะ สั่งของล่วงหน้า ( โหนด * ราก ) {ถ้า ( ราก ) {
พิมพ์ฉ ( '%d \n ' , ราก -> ข้อมูล ) ;
display_pre_order ( ราก -> ซ้าย ) ;
display_pre_order ( ราก -> ขวา ) ;
}
}
2: การส่งผ่านคำสั่งซื้อภายหลัง
ในวิธีการเดินทางผ่านนี้ เราจะผ่านโหนดในทิศทางจาก left_child->right_child->parent_node-> .
เป็นโมฆะ display_post_order ( โหนด * ราก ) {ถ้า ( binary_tree ) {
display_post_order ( ราก -> ซ้าย ) ;
display_post_order ( ราก -> ขวา ) ;
พิมพ์ฉ ( '%d \n ' , ราก -> ข้อมูล ) ;
}
}
3: การข้ามผ่านคำสั่งซื้อ
ในวิธีการสำรวจนี้ เราจะผ่านโหนดในทิศทางจาก left_node->root_child->right_child .
เป็นโมฆะ display_in_order ( โหนด * ราก ) {ถ้า ( binary_tree ) {
display_in_order ( ราก -> ซ้าย ) ;
พิมพ์ฉ ( '%d \n ' , ราก -> ข้อมูล ) ;
display_in_order ( ราก -> ขวา ) ;
}
}
ขั้นตอนที่ 5: ดำเนินการลบในไบนารีทรี
เราสามารถลบสิ่งที่สร้างขึ้นได้ ไบนารี่ทรี โดยลบลูกทั้งสองด้วยฟังก์ชันโหนดแม่ใน C ดังนี้
เป็นโมฆะ delete_t ( โหนด * ราก ) {ถ้า ( ราก ) {
delete_t ( ราก -> ซ้าย ) ;
delete_t ( ราก -> ขวา ) ;
ฟรี ( ราก ) ;
}
}
โปรแกรม C ของ Binary Search Tree
ต่อไปนี้คือการนำแผนผังการค้นหาแบบไบนารีไปใช้อย่างสมบูรณ์ในการเขียนโปรแกรม C:
#include#include
โครงสร้าง โหนด {
นานาชาติ ค่า ;
โครงสร้าง โหนด * ซ้าย , * ขวา ;
} ;
โครงสร้าง โหนด * โหนด 1 ( นานาชาติ ข้อมูล ) {
โครงสร้าง โหนด * ทีเอ็มพี = ( โครงสร้าง โหนด * ) มัลลอค ( ขนาดของ ( โครงสร้าง โหนด ) ) ;
ทีเอ็มพี -> ค่า = ข้อมูล ;
ทีเอ็มพี -> ซ้าย = ทีเอ็มพี -> ขวา = โมฆะ ;
กลับ ทีเอ็มพี ;
}
เป็นโมฆะ พิมพ์ ( โครงสร้าง โหนด * รูท_โหนด ) // แสดงโหนด!
{
ถ้า ( รูท_โหนด != โมฆะ ) {
พิมพ์ ( รูท_โหนด -> ซ้าย ) ;
พิมพ์ฉ ( '%d \n ' , รูท_โหนด -> ค่า ) ;
พิมพ์ ( รูท_โหนด -> ขวา ) ;
}
}
โครงสร้าง โหนด * แทรก_โหนด ( โครงสร้าง โหนด * โหนด , นานาชาติ ข้อมูล ) // กำลังแทรกโหนด!
{
ถ้า ( โหนด == โมฆะ ) กลับ โหนด 1 ( ข้อมูล ) ;
ถ้า ( ข้อมูล < โหนด -> ค่า ) {
โหนด -> ซ้าย = แทรก_โหนด ( โหนด -> ซ้าย , ข้อมูล ) ;
} อื่น ถ้า ( ข้อมูล > โหนด -> ค่า ) {
โหนด -> ขวา = แทรก_โหนด ( โหนด -> ขวา , ข้อมูล ) ;
}
กลับ โหนด ;
}
นานาชาติ หลัก ( ) {
พิมพ์ฉ ( 'การใช้งาน C ของ Binary Search Tree! \n \n ' ) ;
โครงสร้าง โหนด * พ่อแม่ = โมฆะ ;
พ่อแม่ = แทรก_โหนด ( พ่อแม่ , 10 ) ;
แทรก_โหนด ( พ่อแม่ , 4 ) ;
แทรก_โหนด ( พ่อแม่ , 66 ) ;
แทรก_โหนด ( พ่อแม่ , สี่ห้า ) ;
แทรก_โหนด ( พ่อแม่ , 9 ) ;
แทรก_โหนด ( พ่อแม่ , 7 ) ;
พิมพ์ ( พ่อแม่ ) ;
กลับ 0 ;
}
ในโค้ดข้างต้น ขั้นแรกเราจะประกาศ a โหนด โดยใช้ โครงสร้าง . จากนั้นเราจะเริ่มต้นโหนดใหม่เป็น “ โหนด 1 ” และจัดสรรหน่วยความจำแบบไดนามิกโดยใช้ มัลลอค() ใน C ที่มีข้อมูลและตัวชี้สองตัวพิมพ์เด็กโดยใช้โหนดที่ประกาศ หลังจากนี้ เราจะแสดงโหนดโดย พิมพ์f() ฟังก์ชั่นและเรียกใช้ใน หลัก() การทำงาน. จากนั้น insertion_node() ฟังก์ชันถูกสร้างขึ้นโดยที่หากข้อมูลโหนดเป็น NULL แล้ว โหนด 1 ถูกยกเลิก มิฉะนั้น ข้อมูลจะถูกวางไว้ใน โหนด (ผู้ปกครอง) ของเด็กซ้ายและขวา โปรแกรมเริ่มดำเนินการจาก หลัก() ฟังก์ชัน ซึ่งสร้างโหนดโดยใช้โหนดตัวอย่างสองสามโหนดเป็นโหนดย่อย จากนั้นจึงใช้วิธีการแวะผ่านตามคำสั่งเพื่อพิมพ์เนื้อหาของโหนด
เอาต์พุต
บทสรุป
ต้นไม้มักถูกใช้เพื่อเก็บข้อมูลในรูปแบบที่ไม่ใช่เชิงเส้น ต้นไม้ไบนารี เป็นประเภทของต้นไม้ที่แต่ละโหนด (พาเรนต์) มีลูกสองคน ลูกซ้ายและลูกขวา ก ต้นไม้ไบนารี เป็นวิธีการถ่ายโอนและจัดเก็บข้อมูลที่หลากหลาย มีประสิทธิภาพมากกว่าเมื่อเปรียบเทียบกับ Linked-List ใน C ในบทความข้างต้น เราได้เห็นแนวคิดของ ไบนารี่ทรี ด้วยการดำเนินการทีละขั้นตอนของก ต้นไม้ค้นหาแบบไบนารี ในซี