วิธีสร้าง Binary Tree ใน C

จัดโครงสร้างต้นไม้ไบนารีของคุณ ไบนารีทรีทุกต้นจะต้องมีโครงสร้าง แม้ว่าจะมีเพียงตัวแปรเดียวเท่านั้น เลือกชื่อ จากนั้นใช้ typedef เพื่อสร้าง: typedef struct student_data STUDENT_DATA;

กำหนดโครงสร้าง รวมตัวชี้สองตัวในโครงสร้างเดียวกัน: struct student_data { int student_ID; int student_grade; STUDENT_DATA ซ้าย, ขวา;};

จัดสรรตัวชี้ให้กับโครงสร้างข้อมูลนี้ โดยกำหนดค่าเริ่มต้นเป็น NULL ให้เป็นส่วนหัวของต้นไม้: STUDENT_DATA *students = NULL;

จัดสรรตัวชี้ชั่วคราวสองตัวให้กับโครงสร้างข้อมูล: STUDENT_DATA new_student, cur_student;

ใช้ malloc() เพื่อสร้างองค์ประกอบใหม่ ตรวจสอบข้อผิดพลาดเสมอ: if ((new_student = malloc (sizeof (STUDENT_DATA))) == NULL) { abort(); }

เติมฟิลด์ขององค์ประกอบใหม่ ตั้งค่าฟิลด์ซ้ายและขวาเป็น NULL: new_student->student_ID = newID; new_student->student_size = ขนาดใหม่; new_student->left = NULL; new_student->right = NULL;

พิจารณาตัวแปรหัว หากตัวแปร head เป็น NULL นี่เป็นองค์ประกอบแรกที่เพิ่มลงในแผนผัง ดังนั้นให้ตั้งค่าตัวแปร head ให้ชี้ไปที่ตัวแปรนั้น เท่านี้ก็เรียบร้อย: if (!students) { students = new_student; กลับ; }

จัดการกับรายการที่ซ้ำกันหากค่าใหม่และค่าปัจจุบันเท่ากัน: if (newID == cur_student->student_ID) { abort(); }

จัดการกับค่านิยมที่ไม่เท่ากัน หากค่าใหม่น้อยกว่าค่าปัจจุบัน องค์ประกอบใหม่จะอยู่ทางด้านซ้าย เพิ่มทันทีถ้าไม่มีอะไรทางด้านซ้าย มิฉะนั้น ให้เลื่อนไปทางซ้ายแล้ววนซ้ำ: if (newID student_ID) { if (cur_student->left == NULL) { cur_student->left = newstudent; ส่งคืน 1; } cur_student = cur_student->left;

ทำสิ่งเดียวกันทางด้านขวา มิฉะนั้น: } else { if (cur_student->right == NULL) { cur_student->right = newstudent; ส่งคืน 1; } cur_student = cur_student->ขวา; }}

สร้างตัวแปรชั่วคราวที่ชี้ไปที่โครงสร้างข้อมูล: STUDENT_DATA *cur_student;

วนรอบองค์ประกอบ ตรวจสอบค่าที่ต้องการ: ในขณะที่ (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }

สาขาซ้ายหรือขวา และวนซ้ำ หากไม่พบ: if (cur_student->student_ID < 15) { cur_student = cur_student->right; } อื่น ๆ { cur_student = cur_student->left; }

ดูว่าลูปสิ้นสุดหรือไม่ หากพบ แสดงว่าคุณไม่เคยพบรายการนั้น: }return 0;

จัดสรรคืนไบนารีทรีเมื่อโปรแกรมของคุณสิ้นสุด เนื่องจากไม่ใช่ทุกระบบปฏิบัติการจะจัดการสิ่งนี้โดยอัตโนมัติ วิธีนี้ทำได้ดีที่สุดโดยใช้ฟังก์ชันเรียกซ้ำ: void deallocate_binary_tree (STUDENT_DATA *tree) {

Deallocate ทรีย่อยด้านซ้ายและขวาแบบวนซ้ำ: deallocate_binary_tree (tree->left); Deallocate_binary_tree (ต้นไม้ -> ขวา);