1. บทนำ
ในบทความนี้เราจะพูดถึงการใช้งานไบนารีทรีใน Java
เพื่อประโยชน์ของบทความนี้เราจะใช้ต้นไม้ไบนารีเรียงลำดับที่จะมีintค่า
2. ต้นไม้ไบนารี
ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลแบบวนซ้ำโดยแต่ละโหนดสามารถมีลูกได้สูงสุด 2 ลูก
ไบนารีทรีทั่วไปคือต้นไม้ค้นหาแบบทวิภาคซึ่งทุกโหนดมีค่าที่มากกว่าหรือเท่ากับค่าโหนดในแผนผังย่อยด้านซ้ายและน้อยกว่าหรือเท่ากับค่าโหนดในย่อยด้านขวา ต้นไม้.
นี่คือการแสดงภาพอย่างรวดเร็วของต้นไม้ไบนารีประเภทนี้:
สำหรับการนำไปใช้งานเราจะใช้คลาสNodeเสริมที่จะเก็บค่าintและอ้างอิงถึงลูกแต่ละคน:
class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }จากนั้นให้เพิ่มโหนดเริ่มต้นของต้นไม้ของเราซึ่งมักเรียกว่าroot:
public class BinaryTree { Node root; // ... }3. การดำเนินการทั่วไป
ตอนนี้เรามาดูการดำเนินการทั่วไปที่เราสามารถทำได้บนต้นไม้ไบนารี
3.1. การแทรกองค์ประกอบ
การดำเนินการแรกที่เราจะกล่าวถึงคือการแทรกโหนดใหม่
ขั้นแรกเราต้องไปหาสถานที่ที่เราต้องการเพิ่มโหนดใหม่เพื่อให้ต้นไม้เรียง เราจะปฏิบัติตามกฎเหล่านี้โดยเริ่มจากโหนดรูท:
- หากค่าของโหนดใหม่ต่ำกว่าโหนดปัจจุบันเราไปที่ชายด์ทางซ้าย
- ถ้าค่าของโหนดใหม่มากกว่าโหนดปัจจุบันเราจะไปที่ลูกที่ถูกต้อง
- เมื่อโหนดปัจจุบันเป็นโมฆะเรามาถึงโหนดลีฟและเราสามารถแทรกโหนดใหม่ในตำแหน่งนั้นได้
ขั้นแรกเราจะสร้างวิธีการเรียกซ้ำเพื่อทำการแทรก:
private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }ต่อไปเราจะสร้างวิธีการสาธารณะที่เริ่มต้นการเรียกซ้ำจากโหนดรูท :
public void add(int value) { root = addRecursive(root, value); }มาดูกันว่าเราจะใช้วิธีนี้สร้างต้นไม้ได้อย่างไรจากตัวอย่างของเรา:
private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }3.2. การค้นหาองค์ประกอบ
ตอนนี้ให้เพิ่มวิธีการตรวจสอบว่าต้นไม้มีค่าเฉพาะหรือไม่
ก่อนหน้านี้เราจะสร้างวิธีการเรียกซ้ำที่ข้ามต้นไม้ก่อน:
private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }ที่นี่เรากำลังค้นหาค่าโดยเปรียบเทียบกับค่าในโหนดปัจจุบันจากนั้นดำเนินการต่อในลูกทางซ้ายหรือขวาขึ้นอยู่กับว่า
ต่อไปมาสร้างวิธีการสาธารณะที่เริ่มต้นจากรูท :
public boolean containsNode(int value) { return containsNodeRecursive(root, value); }ตอนนี้เรามาสร้างการทดสอบง่ายๆเพื่อตรวจสอบว่าต้นไม้มีองค์ประกอบที่แทรกอยู่จริงๆ:
@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }โหนดทั้งหมดที่เพิ่มควรมีอยู่ในโครงสร้าง
3.3. การลบองค์ประกอบ
การดำเนินการทั่วไปอีกอย่างหนึ่งคือการลบโหนดออกจากทรี
ขั้นแรกเราต้องหาโหนดที่จะลบในลักษณะเดียวกันกับที่เราทำก่อนหน้านี้:
private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }เมื่อเราพบโหนดที่จะลบมี 3 กรณีหลักที่แตกต่างกัน:
- โหนดไม่มีลูก -นี่เป็นกรณีที่ง่ายที่สุด เราเพียงแค่ต้องแทนที่โหนดนี้ด้วยnullในโหนดแม่
- โหนดมีลูกเดียว -ในโหนดแม่เราแทนที่โหนดนี้ด้วยลูกคนเดียว
- โหนดมีลูกสองคน - นี่เป็นกรณีที่ซับซ้อนที่สุดเนื่องจากต้องมีการจัดโครงสร้างใหม่
มาดูกันว่าเราจะใช้กรณีแรกได้อย่างไรเมื่อโหนดเป็นโหนดลีฟ:
if (current.left == null && current.right == null) { return null; }ทีนี้มาดูกรณีต่อไปเมื่อโหนดมีลูกเดียว:
if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }ที่นี่เรากำลังส่งคืนเด็กที่ไม่เป็นค่าว่างเพื่อให้สามารถกำหนดให้กับโหนดหลักได้
สุดท้ายเราต้องจัดการกรณีที่โหนดมีลูกสองคน
ขั้นแรกเราต้องหาโหนดที่จะแทนที่โหนดที่ถูกลบ เราจะใช้โหนดที่เล็กที่สุดของโหนดที่จะถูกลบโครงสร้างย่อยด้านขวา:
private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }จากนั้นเรากำหนดค่าที่น้อยที่สุดให้กับโหนดที่จะลบและหลังจากนั้นเราจะลบออกจากทรีย่อยด้านขวา:
int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;สุดท้ายมาสร้างวิธีการสาธารณะที่เริ่มต้นการลบจากราก :
public void delete(int value) { root = deleteRecursive(root, value); }ตอนนี้ให้ตรวจสอบว่าการลบทำงานตามที่คาดไว้:
@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }4. สำรวจต้นไม้
ในส่วนนี้เราจะเห็นวิธีต่างๆในการสำรวจต้นไม้โดยครอบคลุมรายละเอียดการค้นหาในเชิงลึกก่อนและเชิงกว้าง
We'll use the same tree that we used before and we'll show the traversal order for each case.
4.1. Depth-First Search
Depth-first search is a type of traversal that goes deep as much as possible in every child before exploring the next sibling.
There are several ways to perform a depth-first search: in-order, pre-order and post-order.
The in-order traversal consists of first visiting the left sub-tree, then the root node, and finally the right sub-tree:
public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }If we call this method, the console output will show the in-order traversal:
3 4 5 6 7 8 9Pre-order traversal visits first the root node, then the left subtree, and finally the right subtree:
public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }And let's check the pre-order traversal in the console output:
6 4 3 5 8 7 9Post-order traversal visits the left subtree, the right subtree, and the root node at the end:
public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }Here are the nodes in post-order:
3 5 4 7 9 8 64.2. Breadth-First Search
นี้เป็นอีกหนึ่งชนิดที่พบบ่อยของการสำรวจเส้นทางที่ผู้เข้าชมโหนดทั้งหมดของระดับก่อนที่จะไปที่ระดับถัดไป
การส่งผ่านแบบนี้เรียกอีกอย่างว่าลำดับระดับและเยี่ยมชมทุกระดับของต้นไม้โดยเริ่มจากรากและจากซ้ายไปขวา
สำหรับการนำไปใช้งานเราจะใช้Queueเพื่อยึดโหนดจากแต่ละระดับตามลำดับ เราจะแยกแต่ละโหนดออกจากรายการพิมพ์ค่าจากนั้นเพิ่มลูก ๆ ในคิว:
public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }ในกรณีนี้ลำดับของโหนดจะเป็น:
6 4 8 3 5 7 95. สรุป
ในบทความนี้เราได้เห็นวิธีใช้ไบนารีทรีที่เรียงลำดับใน Java และการดำเนินการที่พบบ่อยที่สุด
ซอร์สโค้ดแบบเต็มสำหรับตัวอย่างมีอยู่บน GitHub