ต้นไม้เรียงลำดับไบนารีเรียกอีกอย่างว่าแผนผังไบนารี มันเป็นต้นไม้ที่ว่างเปล่าหรือต้นไม้ไบนารีที่มีคุณสมบัติดังต่อไปนี้:
①หากทรีย่อยด้านซ้ายไม่ว่างเปล่าค่าของโหนดทั้งหมดในทรีย่อยด้านซ้ายจะเล็กกว่าค่าของโหนดรูท
②หากทรีย่อยด้านขวาไม่ว่างเปล่าจากนั้นค่าของโหนดทั้งหมดในทรีย่อยด้านขวาจะมากกว่าค่าของโหนดรูท
③ทรีย่อยด้านซ้ายและขวาเป็นต้นไม้เรียงลำดับแบบไบนารีตามลำดับ
รหัสต่อไปนี้ใช้:
นำเข้า java.util.linkedList; นำเข้า java.util.queue; โหนดคลาส {ข้อมูล int สาธารณะ; โหนดสาธารณะซ้าย; โหนดสาธารณะขวา; public int lightmaxdistance; INT RITHMAXDISTANCE สาธารณะ; โหนดสาธารณะ (ข้อมูล int) {this.data = ข้อมูล; this.left = null; this.right = null; }}/*** @author ty* การใช้ทรีเรียงลำดับแบบไบนารีรวมถึงการแทรก, การเดินทางข้ามลำดับ, การเดินทางก่อนการเดินทาง, การเดินทางหลังการสั่งซื้อและการคำนวณระยะทางสูงสุดของโหนดทั้งหมด*/คลาสสาธารณะ BinaryTree Public BinaryTree () {root = null; } การแทรกโมฆะสาธารณะ (ข้อมูล int) {node newNode = new node (data); if (root == null) root = newNode; else {node current = root; โหนดพาเรนต์; ในขณะที่ (จริง) {// ค้นหาตำแหน่งแทรก parent = ปัจจุบัน; if (data <current.data) {current = current.left; if (current == null) {parent.left = newNode; กลับ; }} else {current = current.right; if (current == null) {parent.right = newNode; กลับ; }}}}}}} // ค่าตัวเลขอินพุตเพื่อสร้างโมฆะสาธารณะไบนารีสาธารณะ buildTree (int [] ข้อมูล) {สำหรับ (int i = 0; i <data.length; i ++) {insert (data [i]); }}} // วิธีการเดินทางข้ามคำสั่งซื้อซ้ำการใช้โมฆะสาธารณะภายใน (node localroot) {ถ้า (localroot! = null) {inorder (localroot.left); System.out.print (localroot.data+""); Inorder (localroot.right); }} โมฆะสาธารณะ inorder () {this.inorder (this..his.root); } // วิธีการเดินทาง preorder traversal ใช้ซ้ำการใช้โมฆะสาธารณะ preorder (node localroot) {ถ้า (localroot! = null) {system.out.print (localroot.data+""); prederger (localroot.left); preder order (localroot.right); }} โมฆะสาธารณะ preorder () {this.preorder (this.root); } // วิธีการเดินทาง traversal postorder ใช้โมฆะสาธารณะ postorder (โหนด localroot) {ถ้า (localroot! = null) {postorder (localroot.left); postorder (localroot.right); System.out.print (localroot.data+""); }} โมฆะสาธารณะ postorder () {this.postorder (this..his.root); } /*** ทรีทรีทรัวเวอร์ซัลทรีทรัวเวอร์ซัลทรี: ตอนนี้ใส่โหนดรูทลงในคิวจากนั้นใช้โหนดจากคิวทุกครั้งเพื่อพิมพ์ค่าของโหนด * หากโหนดนี้มีโหนดลูกให้วางโหนดลูกไว้ในหางของคิวจนกว่าคิวจะว่างเปล่า*/ โมฆะสาธารณะ layerTranverse () {ถ้า (this..his..his.root == null); คิว <node> q = ใหม่ LinkedList <Node> (); Q.Add (this..his.root); ในขณะที่ (! q.isempty ()) {node n = q.poll (); System.out.print (n.data+""); if (n.left! = null) q.add (n.left); ถ้า (n.right! = null) q.add (n.right); }} maxlen int ส่วนตัว = 0; INT ส่วนตัวสูงสุด (int a, int b) {return a> b? a: b; } โมฆะสาธารณะ findMaxDistance (โหนดรูท) {ถ้า (root == null) return; if (root.left == null) root.leftMaxDistance = 0; if (root.right == null) root.rightMaxDistance = 0; if (root.left! = null) findmaxdistance (root.left); if (root.right! = null) findMaxDistance (root.right); // คำนวณระยะทางสูงสุดจากโหนดรูทในแผนผังคำด้านซ้ายถ้า (root.left! = null) root.leftmaxdistance = สูงสุด (root.left.leftmaxdistance, root.left.rightmaxdistance) +1; // คำนวณระยะทางสูงสุดจากโหนดรูทในแผนผังคำที่ถูกต้องถ้า (root.right! = null) root.rightmaxdistance = สูงสุด (root.right.leftmaxdistance, root.right.rightmaxdistance) +1; // รับระยะทางสูงสุดของโหนดทั้งหมดของทรีไบนารีถ้า (root.leftmaxdistance+root.rightmaxdistance> maxlen) {maxlen = root.leftmaxdistance+root.rightmaxdistance; }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {binarytree bitree = ใหม่ binarytree (); int [] data = {2,8,7,4,9,3,1,1,6,7,5}; bitree.buildtree (ข้อมูล); System.out.print ("In-order traversal ของทรีไบนารี:"); bitree.inorder (); System.out.println (); System.out.print ("การสั่งซื้อล่วงหน้าของต้นไม้ไบนารี:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("โพสต์ลำดับการเดินทางของต้นไม้ไบนารี:"); bitree.postorder (); System.out.println (); System.out.print ("การเดินทางตามลำดับชั้นของต้นไม้ไบนารี:"); bitree.layertranverse (); System.out.println (); bitree.findmaxdistance (bitree.root); System.out.println ("ระยะทางสูงสุดของโหนดในทรีไบนารี:"+bitree.maxlen); -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะช่วยในการศึกษาหรือทำงานของทุกคน ฉันหวังว่าจะสนับสนุน Wulin.com เพิ่มเติม!