นี่เป็นคำถามสัมภาษณ์ทั่วไปเช่นการได้รับการสำรวจแบบลำดับชั้นของต้นไม้ไบนารีผ่านการสั่งซื้อล่วงหน้าและการเดินทางตามลำดับของต้นไม้ไบนารี ฯลฯ ฯลฯ
สั่งซื้อล่วงหน้า + ลำดับกลาง -> สร้าง
สมมติว่าตอนนี้มีต้นไม้ไบนารีดังนี้:
ในเวลานี้คำสั่งข้ามคือ:
preorder: gdafemhz inorder: adefghmz postorder: aefdhzmg
ตอนนี้ให้การสั่งซื้อล่วงหน้าและคำสั่งซื้อล่วงหน้า (inorder) สร้างทรีไบนารีหรือให้คำสั่งซื้อ (ภายใน) และลำดับหลัง (postorder) สร้างทรีไบนารีจริง ๆ แล้วมันเหมือนกัน
คำจำกัดความของโหนดต้นไม้:
ต้นไม้ชั้นเรียน {char val; ต้นไม้ซ้าย; ต้นไม้ขวา; ต้นไม้ (ถ่านวาล, ต้นไม้ซ้าย, ต้นไม้ขวา) {this.val = val; this.left = ซ้าย; this.right = ขวา;} ต้นไม้ () {} ต้นไม้ (ถ่าน val) {this.val = val;สร้างความสำเร็จ:
Public Static Tree BuildTree (char [] preorder, char [] inorder) {// preorder เป็นลำดับ preorder // inorder เป็นลำดับกลางถ้า (preorder == null || preorder.length == 0) {return null;} tree root = tree ใหม่ (preorder [0]); สำหรับ (char i = 0; i <inorder.length; i ++) {ถ้า (inorder [i] == root.val) {inorderIndex = i;}} // ทรีย่อยด้านซ้าย 1+inorderIndex, preorter.length); // ทรีย่อยด้านซ้ายและส่วนย่อยด้านขวาของ char inorder [] inorderleft = arrays.copyofRange (inorder, 0, inorderIndex); char [] inordright = array.copyofRange buildtree (preorderleft, inorderleft); tree rightchild = buildtree (preordright, inorderright); root.left = leftchild; root.right = rightchild; return root;}จริงๆแล้วมันก็เหมือนกันในการสร้างลำดับกลาง + คำสั่งโพสต์ ฉันจะไม่เขียนที่นี่
การสำรวจต่าง ๆ
โพสต์สั่งการเดินทาง
โมฆะคงที่สาธารณะ postorderprint (ทรีรูท) {// traversal ที่ตามมา // ซ้ายซ้ายและขวารากถ้า (root.left! = null) {postorderprint (root.left); } if (root.right! = null) {postorderprint (root.right); } system.out.print (root.val + ""); -เรียนรู้จากตัวอย่างหนึ่งและคำสั่งซื้อเหมือนกับคำสั่งที่อยู่ตรงกลาง ฉันจะไม่เขียนที่นี่
ลำดับเลเยอร์
คุณสามารถใช้คิวคิวคิวเพื่อเพิ่มโหนดรูทลงในคิวก่อน เมื่อคิวไม่ว่างให้ใช้โหนดโหนดของส่วนหัวคิวและพิมพ์ค่าโหนดของโหนด หากเด็กซ้ายและขวาของโหนดไม่ว่างให้เพิ่มเด็กซ้ายและขวาลงในคิว
โมฆะสาธารณะคงที่ layerOrderPrint (ทรีรูท) {ถ้า (root == null) {return; } // เลเยอร์ลำดับการสำรวจคิว <Tree> QE = ใหม่ LinkedList <REST TREY> (); Qe.add (รูท); ในขณะที่ (! qe.isempty ()) {tree node = qe.poll (); System.out.print (node.val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); -ความลึกและลำดับความสำคัญ
อันที่จริงมันเป็นเพียงคำพูดที่แตกต่าง ลำดับความสำคัญของความลึกคือการสั่งการเดินทางล่วงหน้าลำดับความสำคัญที่กว้างคือการเดินทางแบบเรียงลำดับชั้น
โมฆะสาธารณะคงที่ DeepFirstPrint (ทรีรูท) {// การสำรวจลำดับความสำคัญของความสำคัญลึกนั้นเทียบเท่ากับการเดินทางล่วงหน้า // เพื่อให้คุณสามารถใช้การเดินทางล่วงหน้าล่วงหน้าได้โดยตรงถ้า (root == null) {return; } system.out.print (root.val + ""); if (root.left! = null) {deepFirstPrint (root.left); } if (root.right! = null) {deepFirstPrint (root.right); }} โมฆะคงที่สาธารณะ DeepFirstPrintNonerec (ทรีรูท) {// รูปแบบที่ไม่ได้รับการตอบโต้ความลึกที่มีลำดับความสำคัญข้ามไปหาก (root == null) {return; } สแต็ก <Ree> st = ใหม่สแต็ก <Ree> (); St.Add (ราก); ในขณะที่ (! st.isempty ()) {tree node = st.pop (); System.out.print (node.val + ""); // สแต็คกลับเข้ามาและออกก่อน // เพิ่มลูกที่ถูกต้องก่อนแล้วจึงเด็กซ้ายถ้า (node.right! = null) {st.add (node.right); } if (node.left! = null) {st.add (node.left); -ฟังก์ชั่นหลัก:
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {char [] preorter = "gdafemhz" .tochararray (); char [] inorder = "adefghmz" .tochararray (); tree root = main.buildtree (preorder, inorder); // main.postorderprint (root); // postorder traversal // main.layerorderprint (root); // เลเยอร์ลำดับการเดินทาง // main.deepfirstprint (root); // Deep Priority Traversal // main.deepfirstprintnonerec (root); // เวอร์ชันที่ไม่ได้รับการย้อนกลับของการสำรวจความลึกครั้งแรก}}สรุป
ข้างต้นคือทั้งหมดที่เกี่ยวกับการจัดตั้งต้นไม้ไบนารีและรหัสอินสแตนซ์ข้ามต่างๆในชวา ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงเว็บไซต์นี้ต่อไปได้:
" รู้เบื้องต้นเกี่ยวกับสองวิธีในการสะท้อนในต้นไม้ไบนารีการเขียนโปรแกรม Java "
" ภาษา Java อธิบายถึงความลึกและความกว้างของต้นไม้ไบนารี "
เส้นทางและตัวอย่างรหัสของ Java Binary Tree
หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!