การจำแนกประเภทของต้นไม้ไบนารี (โดยโครงสร้างการจัดเก็บ)
การจำแนกประเภทของต้นไม้ (ตามโครงสร้างการจัดเก็บ)
การจัดเก็บตามลำดับ (แสดงโดยอาร์เรย์ (ต้นไม้ไบนารีคงที่))
ที่เก็บโซ่
รากไบนารีพิเศษบางอย่าง:
ต้นไม้ไบนารีที่สมบูรณ์, ต้นไม้ไบนารีที่สมดุล (AVL), เบาะแสต้นไม้ไบนารี, สามฟอร์ค (ตัวชี้กับพ่อ)
แผนผังค้นหาไบนารีหรือแผนผังไบนารี (BST)
ต้นไม้ไบนารีที่ใช้แสดงในรูปต่อไปนี้:
การใช้งาน Java ของต้นไม้ไบนารี (โครงสร้างการจัดเก็บโซ่)
คลาส treenode {คีย์ int ส่วนตัว = 0; ข้อมูลสตริงส่วนตัว = null; บูลีนส่วนตัว isvisted = false; treenode ส่วนตัว leftchild = null; treenode ส่วนตัว rightChild = null; public treenode () {} treenode สาธารณะ (คีย์ int, ข้อมูลสตริง) {this.key = key; this.data = ข้อมูล; this.leftchild = null; this.rightChild = null; } public int getKey () {คีย์ return; } โมฆะสาธารณะ setKey (คีย์ int) {this.key = key; } สตริงสาธารณะ getData () {ส่งคืนข้อมูล; } โมฆะสาธารณะ setData (ข้อมูลสตริง) {this.data = ข้อมูล; } สาธารณะ treenode getleftchild () {return leftchild; } โมฆะสาธารณะ setleftchild (treenode leftchild) {this.leftchild = leftchild; } สาธารณะ treenode getriveHild () {return rightchild; } โมฆะสาธารณะ setrightChild (treenode rightChild) {this.rightChild = RightChild; } บูลีนสาธารณะ isvisted () {return isvisted; } โมฆะสาธารณะ setVisted (บูลีน isvisted) {this.isvisted = isvisted; }} คลาสสาธารณะ BinaryTree {Private treenode root = null; Public BinaryTree () {root = new treenode (1, "rootnode (a)"); } โมฆะสาธารณะ createBinTree (treenode root) {// การสร้างด้วยตนเอง (โครงสร้างแสดงในรูป) treenode newNodeB = new Treenode (2, "B"); treenode newNodec = new Treenode (3, "C"); treenode newNoded = new Treenode (4, "D"); treenode newNodee = new Treenode (5, "E"); treenode newNodef = new Treenode (6, "F"); root.setleftchild (newnodeb); root.setrightchild (newnodec); root.getleftchild (). setleftchild (newnoded); root.getleftchild (). setrightchild (newnodee); root.getrightchild (). setrightchild (newNodef); } บูลีนสาธารณะ isempty () {// พิจารณาว่าต้นไม้ไบนารีว่างเปล่าหรือไม่คืนรูท == null; } ความสูง int สาธารณะ () {// ค้นหาความสูงของความสูงของต้นไม้ (รูท); } ความสูง int สาธารณะ (treenode subtree) {ถ้า (subtree == null) return 0; // การเรียกซ้ำสิ้นสุด: ความสูงของต้นไม้ที่ว่างเปล่าคือ 0 else {int i = ความสูง (subtree.getLeftchild ()); int j = ความสูง (subtree.getrightchild ()); return (i <j)? J + 1: i + 1; }} ขนาด int สาธารณะ () {// ค้นหาจำนวนของโหนดส่งคืนขนาด (รูท); } ขนาด int สาธารณะ (treenode subtree) {ถ้า (subtree == null) return 0; else {return 1 + size (subtree.getLeftchild ()) + size (subtree.getrightchild ()); }} parent parent สาธารณะ (องค์ประกอบ treenode) {// ส่งคืนโหนดพาเรนต์ส่งคืน (root == null || root == องค์ประกอบ)? NULL: ผู้ปกครอง (รูท, องค์ประกอบ); } Public Treenode Parent (Treenode subtree, องค์ประกอบ treenode) {ถ้า (subtree == null) ส่งคืน null; if (subtree.getLeftchild () == องค์ประกอบ || subtree.getrightChild () == องค์ประกอบ) // เสร็จสิ้นให้ส่งคืนที่อยู่โหนดพาเรนต์ที่อยู่ส่งคืนทรี subtree; Treenode P; // ก่อนดูในทรีย่อยด้านซ้าย หากไม่พบในทรีย่อยด้านซ้ายให้ไปที่ทรีย่อยด้านขวาเพื่อค้นหาว่า ((p = parent (tree.tree.getLeftchild (), องค์ประกอบ))! = null) // ค้นหา return p; ELLE // ค้นหาอีกครั้งสำหรับ PRANTY RETURN (SUBTREE.GetRightChild (), องค์ประกอบ); } สาธารณะ treenode leftChild (องค์ประกอบ treenode) {// ส่งคืนทรีย่อยด้านซ้าย (องค์ประกอบ! = null)? Element.getLeftChild (): NULL; } สาธารณะ treenode RightChild (องค์ประกอบ treenode) {// ส่งคืนทรีย่อยกลับ (องค์ประกอบ! = null)? Element.getRightChild (): NULL; } สาธารณะ treenode getRoot () {// รับรูทรูทส่งคืนรูท; } โมฆะสาธารณะทำลาย (treenode subtree) {// ฟังก์ชั่นส่วนตัว: ลบทรีย่อยด้วยทรีรูท subtree ถ้า (subtree! = null) {ทำลาย (subtree.getleftchild ()); // ลบทรีย่อยด้านซ้ายทำลาย (tree.getrightchild ()); // ลบทรีย่อยด้านขวา // ลบทรีย่อย; // ลบทรีย่อยโหนดรูท = null; }} โมฆะสาธารณะ traverse (treenode subtree) {system.out.println ("คีย์:" + subtree.getKey () + "-name:" + subtree.getData ()); Traverse (Subtree.getLeftchild ()); Traverse (subtree.getrightchild ()); } โมฆะสาธารณะ preorder (treenode subtree) {// root ก่อนถ้า (subtree! = null) {visted (subtree); prederger (subtree.getLeftchild ()); prederger (subtree.getrightchild ()); }} โมฆะสาธารณะ inorder (treenode subtree) {// รูทกลางถ้า (subtree! = null) {inorder (subtree.getLeftchild ()); Visted (ทรีย่อย); inorder (subtree.getrightchild ()); }} โมฆะสาธารณะ postorder (treenode subtree) {// post root ถ้า (subtree! = null) {postorder (subtree.getLeftchild ()); postorder (subtree.getrightchild ()); Visted (ทรีย่อย); }} public void levelorder (treenode subtree) {// horily periphery} การแทรกบูลีนสาธารณะ (องค์ประกอบ treenode) {// แทรกคืนกลับจริง; } บูลีนสาธารณะค้นหา (องค์ประกอบ treenode) {// ค้นหา return true; } โมฆะสาธารณะเป็นพยาน (Treenode subtree) {subtree.setVisted (จริง); System.out.println ("คีย์:" + subtree.getKey () + "-name:" + subtree.getData ()); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {binarytree bt = ใหม่ binarytree (); Bt.CreateBinTree (BT..Root); System.out.println ("ขนาดของต้นไม้คือ" + bt.size ()); System.out.println ("ความสูงของต้นไม้คือ" + bt.height ()); System.out.println ("********* preorder (preorder) [abdecf] โอน **************"); bt.preorder (bt..root); System.out.println ("********* รูทกลาง (ลำดับภายใน) [dbeacf] โอน ****************"); bt.inorder (bt.root); System.out.println ("********* รูทสุดท้าย (คำสั่งโพสต์) [debfca] โอน **************"); bt.postorder (bt..root); - ผลลัพธ์ผลลัพธ์:
ขนาดของต้นไม้คือ 6
ความสูงของต้นไม้คือ 3
******* รากแรก (preorder) [abdecf] Traversal **************
คีย์: 1-ชื่อ: rootnode (a)
คีย์: 2-ชื่อ: B
คีย์: 4-ชื่อ: D
คีย์: 5-ชื่อ: E
คีย์: 3-ชื่อ: C
คีย์: 6-ชื่อ: F
******* รากขนาดกลาง (ลำดับกลาง) [dbeacf] Traversal ****************
คีย์: 4-ชื่อ: D
คีย์: 2-ชื่อ: B
คีย์: 5-ชื่อ: E
คีย์: 1-ชื่อ: rootnode (a)
คีย์: 3-ชื่อ: C
คีย์: 6-ชื่อ: F
******* รูทสุดท้าย (คำสั่งโพสต์) [DEBFCA] Traversal **************
คีย์: 4-ชื่อ: D
คีย์: 5-ชื่อ: E
คีย์: 2-ชื่อ: B
คีย์: 6-ชื่อ: F
คีย์: 3-ชื่อ: C
คีย์: 1-ชื่อ: rootnode (a)
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับนักเรียนที่เรียนการเขียนโปรแกรม Java