แนวคิดของต้นไม้ไบนารี
ต้นไม้ไบนารีเป็นชุด จำกัด ของโหนด n (n> = 0) ชุดนี้เป็นชุดว่างเปล่า (ต้นไม้ไบนารีที่ว่างเปล่า) หรือประกอบด้วยโหนดรูทและต้นไม้ไบนารีสองต้นที่ไม่ตัดซึ่งกันและกันเรียกว่าโหนดรูทและทรีย่อยด้านขวาตามลำดับ
ลักษณะของต้นไม้ไบนารี
แต่ละโหนดมีทรีย่อยสองตัวดังนั้นจึงไม่มีโหนดที่มีระดับมากกว่า 2 ระดับในต้นไม้ไบนารี แต่ละโหนดในทรีไบนารีเป็นวัตถุและแต่ละโหนดข้อมูลมีสามพอยน์เตอร์คือพอยน์เตอร์ไปยังผู้ปกครองเด็กซ้ายและลูกขวา แต่ละโหนดเชื่อมต่อกันผ่านตัวชี้ ความสัมพันธ์ระหว่างพอยน์เตอร์ที่เชื่อมต่อคือความสัมพันธ์ของพ่อ-ลูกทั้งหมด
คำจำกัดความของโหนดต้นไม้ไบนารี
โหนดทรีไบนารีหมายถึงดังนี้:
การคัดลอกรหัสมีดังนี้:
โครงสร้าง BinaryTreenode
-
int m_nvalue;
BinaryTreenode* m_pleft;
BinaryTreenode* m_pright;
-
ห้ารูปแบบพื้นฐานของต้นไม้ไบนารี
ต้นไม้ไบนารีที่ว่างเปล่า
มีเพียงหนึ่งโหนดรูท
โหนดรูทมีเพียงทรีย่อยด้านซ้าย
โหนดรูทมีเพียงทรีย่อยที่เหมาะสม
โหนดรูทมีทั้งทรีย่อยด้านซ้ายและด้านขวา
มีเพียงสองกรณีสำหรับต้นไม้ธรรมดาที่มีสามโหนด: สองหรือสาม อย่างไรก็ตามเนื่องจากต้นไม้ไบนารีต้องแยกแยะความแตกต่างทางซ้ายและขวามันจะพัฒนาเป็นห้ารูปแบบต่อไปนี้:
ต้นไม้ไบนารีพิเศษ
ต้นไม้เอียง
ดังที่แสดงในภาพเล็ก ๆ ที่สองและสามในภาพย่อยสุดท้ายด้านบน
ต้นไม้ไบนารีเต็มรูปแบบ
ในต้นไม้ไบนารีหากโหนดสาขาทั้งหมดมีทรีย่อยด้านซ้ายและขวาและใบทั้งหมดอยู่ในชั้นเดียวกันต้นไม้ไบนารีนั้นเรียกว่าต้นไม้ไบนารีเต็มรูปแบบ ดังที่แสดงในรูปด้านล่าง:
ต้นไม้ไบนารีที่สมบูรณ์
ต้นไม้ไบนารีที่สมบูรณ์หมายความว่าชั้นสุดท้ายเต็มไปทางซ้ายด้านขวาอาจเต็มหรือไม่และส่วนที่เหลือของเลเยอร์เต็ม ต้นไม้ไบนารีที่มีความลึกของ K และจำนวนโหนดจำนวน 2^k - 1 เป็นต้นไม้ไบนารีเต็มรูปแบบ (ต้นไม้ไบนารีที่สมบูรณ์) มันเป็นต้นไม้ที่มีความลึกของ K และไม่มีที่ว่าง
ลักษณะของต้นไม้ไบนารีที่สมบูรณ์คือ:
โหนดใบไม้สามารถปรากฏในสองชั้นต่ำสุดเท่านั้น
ใบต่ำสุดจะต้องเข้มข้นในตำแหน่งต่อเนื่องทางด้านซ้าย
ในชั้นสุดท้ายหากมีโหนดใบไม้จะต้องอยู่ในตำแหน่งที่ต่อเนื่องทางด้านขวา
หากระดับโหนดคือ 1 โหนดจะมีเฉพาะเด็กซ้าย
สำหรับต้นไม้ไบนารีที่มีต้นโหนดเดียวกันต้นไม้ไบนารีที่สมบูรณ์มีความลึกที่เล็กที่สุด
หมายเหตุ: ต้นไม้ไบนารีเต็มรูปแบบจะต้องเป็นต้นไม้ไบนารีที่สมบูรณ์ แต่ต้นไม้ไบนารีที่สมบูรณ์อาจไม่ใช่ต้นไม้ไบนารีเต็มรูปแบบ
อัลกอริทึมมีดังนี้:
การคัดลอกรหัสมีดังนี้:
bool is_complete (ทรี *รูท)
-
คิว Q;
ต้นไม้ *ptr;
// ดำเนินการสำรวจลำดับความสำคัญที่กว้าง (การสำรวจลำดับชั้น) และใส่โหนดโมฆะลงในคิวเช่นกัน
Q.Push (รูท);
ในขณะที่ ((ptr = q.pop ())! = null)
-
Q.Push (ptr-> ซ้าย);
Q.Push (ptr-> ขวา);
-
// พิจารณาว่ายังมีโหนดที่ยังไม่ได้เข้าถึง
ในขณะที่ (! q.is_empty ())
-
ptr = q.pop ();
// หากมีโหนดที่ไม่ใช่ Null ที่ไม่สามารถเข้าถึงได้ต้นไม้มีช่องว่างและเป็นต้นไม้ไบนารีที่ไม่สมบูรณ์
ถ้า (null! = ptr)
-
กลับเท็จ;
-
-
กลับมาจริง;
-
คุณสมบัติของต้นไม้ไบนารี
คุณสมบัติ 1 ของต้นไม้ไบนารี: มีโหนดมากที่สุด 2^(i-1) บนชั้น i-th ของต้นไม้ไบนารี (i> = 1)
คุณสมบัติ 2 ของ Binary Tree: ต้นไม้ไบนารีที่มีความลึก k มีที่มากที่สุด 2^k-1 โหนด (k> = 1)
โครงสร้างการจัดเก็บตามลำดับของต้นไม้ไบนารี
โครงสร้างการจัดเก็บตามลำดับของต้นไม้ไบนารีคือการใช้อาร์เรย์หนึ่งมิติเพื่อเก็บแต่ละโหนดในทรีไบนารีและตำแหน่งการจัดเก็บของโหนดสามารถสะท้อนความสัมพันธ์เชิงตรรกะระหว่างโหนด
รายการลิงค์ไบนารี
เนื่องจากวิธีการจัดเก็บตามลำดับไม่สามารถใช้งานได้มากเราต้องพิจารณาโครงสร้างการจัดเก็บโซ่ ตามการปฏิบัติระหว่างประเทศการจัดเก็บต้นไม้ไบนารีมักใช้โครงสร้างการจัดเก็บโซ่
แต่ละโหนดของต้นไม้ไบนารีมีเด็กมากที่สุดสองคนดังนั้นจึงเป็นความคิดที่เป็นธรรมชาติในการออกแบบฟิลด์ข้อมูลและสองฟิลด์ตัวชี้สำหรับมัน เราเรียกรายการที่เชื่อมโยงดังกล่าวเป็นรายการไบนารีที่เชื่อมโยง
Traversal of Binary Trees
ต้นไม้ไบนารีที่ผ่านการสำรวจหมายถึงการเข้าถึงโหนดทั้งหมดในต้นไม้ไบนารีในลำดับที่แน่นอนจากโหนดรูทเพื่อให้แต่ละโหนดเข้าถึงได้หนึ่งครั้งและเพียงครั้งเดียว
มีสามวิธีในการสำรวจต้นไม้ไบนารีดังต่อไปนี้:
(1) การสั่งซื้อล่วงหน้า (DLR) ก่อนการเข้าถึงโหนดรูทก่อนจากนั้นจะข้ามทรีย่อยด้านซ้ายและในที่สุดก็ข้ามทรีย่อยด้านขวา รูทตัวย่อ - ซ้าย - ขวา
(2) In-order traversal (LDR), traversal แรกผ่านทรีย่อยด้านซ้ายจากนั้นเข้าถึงโหนดรูทและในที่สุดก็ข้ามทรีย่อยด้านขวา หมายเหตุย่อ: ซ้ายรากขวา
(3) โพสต์ลำดับการเดินทาง (LRD), ผ่านทรีย่อยด้านซ้ายก่อนจากนั้นข้ามทรีย่อยด้านขวาและในที่สุดก็เข้าถึงโหนดรูท ตัวย่อซ้ายขวา
การสำรวจเบื้องต้น:
หากต้นไม้ไบนารีว่างเปล่าการดำเนินการที่ว่างจะกลับมา มิฉะนั้นให้เข้าถึงโหนดรูทก่อนจากนั้นสำรวจทรีย่อยด้านซ้ายในลำดับก่อนหน้าจากนั้นสำรวจทรีย่อยด้านขวาในลำดับก่อนหน้า
คำสั่งของการเดินทางคือ: abdhiejcfkg
การคัดลอกรหัสมีดังนี้:
// การสำรวจที่แม่นยำ
ฟังก์ชั่น preorder (โหนด) {
if (! node == null) {
putstr (node.show ()+ "");
prederger (node.left);
prederger (node.right);
-
-
การเดินทางตามลำดับ:
หากต้นไม้ว่างเปล่าการทำงานที่ว่างเปล่าจะส่งคืนมิฉะนั้นจะเริ่มต้นจากโหนดรูท (โปรดทราบว่าโหนดรูทไม่ได้เข้าถึงก่อน) และทรีย่อยด้านซ้ายของโหนดรูทจะถูกเคลื่อนที่ในลำดับกลางแล้วโหนดรูทจะถูกเข้าถึงและในที่สุด
คำสั่งของการสำรวจคือ: hdibejafkcg
การคัดลอกรหัสมีดังนี้:
// ใช้วิธีการเรียกซ้ำเพื่อใช้การเดินทางแบบกลางสั่ง
ฟังก์ชั่น inorder (โหนด) {
if (! (node == null)) {
inorder (node.left); // เพิ่มลงในทรีย่อยด้านซ้ายก่อน
putstr (node.show ()+ ""); // เพิ่มลงในโหนดรูทอีกครั้ง
inorder (node.right); // การเข้าถึงครั้งล่าสุดไปยังทรีย่อยด้านขวา
-
-
โพสต์ลำดับการเดินทาง:
หากต้นไม้ว่างเปล่าการดำเนินการที่ว่างเปล่าจะกลับมา มิฉะนั้นทรีย่อยด้านซ้ายและขวาจะถูกสำรวจจากซ้ายไปขวาเพื่อเข้าถึงทรีย่อยด้านซ้ายและขวาและในที่สุดก็เข้าถึงโหนดรูท
คำสั่งของการสำรวจคือ: hidjebkfgca
การคัดลอกรหัสมีดังนี้:
// โพสต์-สั่งการเดินทาง
ฟังก์ชั่น postorder (โหนด) {
if (! node == null) {
postorder (node.left);
postorder (node.right);
putstr (node.show ()+ "");
-
-
ใช้ทรีค้นหาไบนารี
ทรีค้นหาไบนารี (BST) ประกอบด้วยโหนดดังนั้นเราจึงกำหนดวัตถุโหนดโหนดดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นโหนด (ข้อมูลซ้ายขวา) {
this.data = ข้อมูล;
this.left = ซ้าย; // บันทึกลิงค์โหนดซ้าย
this.right = ขวา;
this.show = แสดง;
-
ฟังก์ชั่นแสดง () {
ส่งคืนสิ่งนี้ data; // แสดงข้อมูลที่บันทึกไว้ในโหนด
-
ค้นหาค่าสูงสุดและต่ำสุด
การค้นหาค่าต่ำสุดและค่าสูงสุดของ BST นั้นง่ายมากเนื่องจากค่าที่เล็กกว่าอยู่ในโหนดเด็กซ้ายเสมอและมองหาค่าต่ำสุดบน BST เพียงแค่สำรวจต้นไม้เด็กซ้ายจนกระทั่งพบโหนดสุดท้าย
ค้นหาค่าต่ำสุด
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น getMin () {
var current = this.root;
ในขณะที่ (! (current.left == null)) {
current = current.left;
-
ส่งคืน current.data;
-
วิธีนี้จะเคลื่อนที่ทีละคนตามทรีย่อยด้านซ้ายของ BST จนกระทั่งมันเคลื่อนที่ไปยังโหนดซ้ายสุดของ BST ซึ่งถูกกำหนดเป็น:
การคัดลอกรหัสมีดังนี้:
current.left = null;
ในเวลานี้ค่าที่บันทึกไว้ในโหนดปัจจุบันคือค่าต่ำสุด
ค้นหาค่าสูงสุด
การค้นหาค่าสูงสุดใน BST จะต้องใช้ทรีย่อยที่ถูกต้องจนกว่าจะพบโหนดสุดท้ายและค่าที่บันทึกไว้ในโหนดนั้นเป็นค่าสูงสุด
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น getMax () {
var current = this.root;
ในขณะที่ (! (current.right == null)) {
current = current.right;
-
ส่งคืน current.data;
-