Klasifikasi pohon biner (berdasarkan struktur penyimpanan)
Klasifikasi pohon (berdasarkan struktur penyimpanan)
Penyimpanan berurutan (diwakili oleh array (pohon biner statis))
Penyimpanan rantai
Beberapa akar biner khusus:
Pohon biner lengkap, pohon biner seimbang (AVL), petunjuk pohon biner, tri-fork (pointer dengan ayah)
Pohon pencarian biner atau pohon pencarian biner (BST)
Pohon biner yang digunakan ditunjukkan pada gambar berikut:
Java Implementasi pohon biner (struktur penyimpanan rantai)
kelas treenode {private int key = 0; data string pribadi = null; private boolean isvisted = false; Private Treeenode LeftChild = NULL; Private Treeenode RightChild = NULL; public treenode () {} public treenode (kunci int, data string) {this.key = key; this.data = data; this.leftchild = null; this.rightchild = null; } public int getKey () {return key; } public void setKey (int key) {this.key = key; } public String getData () {return data; } public void setData (string data) {this.data = data; } public treenode getLeftChild () {return leftchild; } public void setleftChild (TreeNode LeftChild) {this.LeftChild = LeftChild; } public treenode getRightChild () {return rightChild; } public void setRightChild (treenode rightChild) {this.rightchild = rightChild; } public boolean isVisted () {return isvisted; } public void setVisted (boolean isvisted) {this.isvisted = isVisted; }} kelas publik BinaryTree {private treenode root = null; BinaryTree publik () {root = treenode baru (1, "rootnode (a)"); } public void createBintree (root TreeNode) {// Pembuatan manual (struktur ditampilkan pada gambar) 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); } public boolean isEmpty () {// Tentukan apakah pohon biner kosong atau tidak mengembalikan root == null; } public int height () {// Temukan tinggi pengembalian tinggi pohon (root); } public int height (treenode subtree) {if (subtree == null) return 0; // ujung rekursif: ketinggian pohon kosong adalah 0 else {int i = tinggi (subtree.getleftchild ()); int j = tinggi (subtree.getRightChild ()); kembali (i <j)? j + 1: i + 1; }} public int size () {// Temukan jumlah node ukuran pengembalian (root); } Ukuran int publik (TreeNode Subtree) {if (subtree == null) return 0; else {return 1 + size (subtree.getleftchild ()) + size (subtree.getRightChild ()); }} public TreeNode Parent (elemen treenode) {// return The Parte node return (root == null || root == elemen)? null: induk (root, elemen); } public treenode induk (treenode subtree, elemen treenode) {if (subtree == null) return null; if (subtree.getleftchild () == elemen || subtree.getRightChild () == elemen) // Selesai, kembalikan subtree pengembalian alamat node node induk; Treeenode P; // tampilan pertama di subtree kiri. Jika tidak ditemukan di subtree kiri, buka subtree kanan untuk menemukan jika ((p = induk (subtree.getleftchild (), elemen))! = Null) // Cari secara rekursif untuk pengembalian p; else // Seekursif mencari induk pengembalian (subtree.getRightChild (), elemen); } public treenode leftChild (elemen treenode) {// return subtree return kiri (elemen! = null)? element.getleftchild (): null; } public treenode rightChild (elemen treenode) {// return subtree return kanan (elemen! = null)? element.getRightChild (): null; } public treenode getroot () {// Dapatkan root root root root; } public void hancurkan (TreeNode Subtree) {// Fungsi Privat: Hapus Subtree dengan Root Subtree if (Subtree! = Null) {Destroy (Subtree.GetLeftChild ()); // hapus subtree hancur kiri (subtree.getRightChild ()); // hapus subtree kanan // hapus subtree; // hapus subtree simpul root = null; }} public void traverse (TreeNode Subtree) {System.out.println ("KEY:" + SUBTREE.GETKEY () + "--NAME:" + SUBTREE.GetData ()); Traverse (subtree.getleftchild ()); Traverse (subtree.getRightChild ()); } public void preorder (TreeNode Subtree) {// root pertama if (subtree! = null) {visted (subtree); Preorder (subtree.getleftchild ()); Preorder (subtree.getRightChild ()); }} public void inorder (TreeNode Subtree) {// medium root if (subtree! = null) {inorder (subtree.getleftchild ()); visted (subtree); Inorder (subtree.getRightChild ()); }} public void postorder (TreeNode Subtree) {// Posting root if (subtree! = null) {postorder (subtree.getleftChild ()); POSTORDER (SUBTREE.GETRIGHTCHILD ()); visted (subtree); }} public void LevelOrder (TreeNode Subtree) {// Horiy Perifery} Public Boolean Insert (elemen TreeNode) {// Masukkan return true; } find public boolean (elemen treenode) {// temukan return true; } public void disaksikan (TreeNode Subtree) {Subtree.setVisted (true); System.out.println ("Kunci:" + Subtree.GetKey () + "--Name:" + Subtree.getData ()); } public static void main (string [] args) {BinaryTree bt = new BinaryTree (); bt.createBintree (bt.root); System.out.println ("Ukuran pohon adalah" + bt.size ()); System.out.println ("Ketinggian pohon adalah" + bt.height ()); System.out.println ("********* Preorder (preorder) [Abdecf] Transfer ****************"); bt.preorder (bt.root); System.out.println ("********* medium root (urutan dalam) [dbeAcf] transfer ****************"); bt.inorder (bt.root); System.out.println ("********* Root Terakhir (Posting Pesan) [Debfca] Transfer ****************"); bt.postorder (bt.root); }} Hasil hasil:
Ukuran pohon adalah 6
Ketinggian pohon adalah 3
******* root pertama (preorder) [abdecf] traversal ****************
KUNCI: 1-Nama: rootnode (a)
KUNCI: 2-Nama: b
Kunci: 4-Nama: d
Kunci: 5-Nama: e
Kunci: 3-Nama: c
KUNCI: 6-Nama: f
******* Medium Root (Tengah Urutan) [DBeAcf] Traversal ******************
Kunci: 4-Nama: d
KUNCI: 2-Nama: b
Kunci: 5-Nama: e
KUNCI: 1-Nama: rootnode (a)
Kunci: 3-Nama: c
KUNCI: 6-Nama: f
******* root terakhir (pesanan pasca) [debfca] traversal **************
Kunci: 4-Nama: d
Kunci: 5-Nama: e
KUNCI: 2-Nama: b
KUNCI: 6-Nama: f
Kunci: 3-Nama: c
KUNCI: 1-Nama: rootnode (a)
Saya berharap artikel ini akan membantu siswa yang mempelajari pemrograman Java.