Apa itu pohon biner? Saya tidak akan memperkenalkannya di sini. Anda dapat menggunakan Baidu: pohon biner. Di sini, gunakan Java untuk mengimplementasikan "pohon biner ekspresi".
Definisi Ekspresi pohon biner
Langkah pertama adalah memahami apa ekspresi pohon biner? Misalnya, ekspresi: (a+b × (cd))-e/f. Menempatkan angka di simpul daun dan operator di simpul cabang membentuk pohon biner. Karena menyimpan ekspresi, itu disebut "pohon biner ekspresi".
Sepatu bot anak -anak mungkin penasaran tentang bagaimana ini dibangun? Ambil 45+23*56/2-5 sebagai contoh. Pertama -tama keluarkan nomor pertama 45 dan masukkan ke dalam simpul daun. Setelah bertemu "+", letakkan di simpul cabang.
Kemudian letakkan "23", "*", "56", "/", dan "2" secara berurutan.
Akhirnya put "-" dan "5",
Kira -kira itu. (Saya sendiri menggambar foto -foto ini, itu jelek, lihat saja (⊙⊙))
Langkah -langkah untuk membangun pohon biner ekspresi
1. Buat objek simpul;
2. Bedakan operator dan data dan simpan di daftar yang sesuai (antrian);
3. Keluarkan dua angka pertama dan operator untuk membentuk node angka baru;
4. Ulangi Langkah 3 sampai operator selesai;
5. Biarkan simpul root sama dengan simpul terakhir.
Implementasi pohon biner ekspresi
Pertama, bangun kelas objek node, termasuk data, subtree kiri, subtree kanan dan beberapa metode set dan dapatkan.
Paket Tets0714;/** * Kelas Objek Node * @Author yuxiu * */Node kelas publik {// Data data string pribadi; // Subtree Private Node LCHILD; // Subtree Private Node RCHILD; Node () {} node (string data) {this.data = data; } Node (data string, node lChild, node rchild) {super (); this.data = data; this.lChild = lChild; this.rchild = rchild; } public String getData () {return data; } node publik getLChild () {return lChild; } node publik getRchild () {return rchild; }}Kemudian bangun pohon biner ekspresi.
Paket Tets0714; Impor java.util.arraylist;/** * Ekspresi kelas pohon biner * @Author yuxiu * */kelas publik formauetree {private string s = ""; root simpul pribadi; // root node/*** Buat pohon biner ekspresi* @param str expression*/public void creattree (string str) {// Deklarasikan daftar array, operator toko, tambahkan, kurangi, perkalian dan divisi, arraylist <string> operatorList = new ArrayList <string> (); // Nyatakan daftar array, simpan data node, arraylist <node> numlist = arraylist baru <node> (); // Pertama, bedakan operator dan data dan simpan di daftar yang sesuai untuk (int i = 0; i <str.length (); i ++) {char ch = str.charat (i); // Ambil karakter string if (ch> = '0' && ch <= '9') {s+= ch; } else {numlist.add (node baru); s = ""; operatorList.Add (ch+""); }} // Tambahkan nomor terakhir ke node node numlist.add (node baru); while (operlist.size ()> 0) {// Langkah 3, ulangi langkah kedua sampai operator selesai // Kedua, ambil dua angka pertama dan operator untuk membentuk simpul nomor node baru kiri = numlist.remove (0); Node kanan = numlist.remove (0); String operator = operatorList.remove (0); Node simpul = simpul baru (oper, kiri, kanan); numlist.add (0, node); // Lebih suka simpul baru sebagai simpul pertama, dan simpul sebelumnya dengan indeks = 0 diubah menjadi indeks = 1} // Langkah 4, biarkan node root sama dengan node terakhir root = numlist.get (0); } / *** data simpul output* / output public void () {output (root); // Berhenti Traversal dari Node Root}/*** Data Node Output* @param node*/output public void (node node) {if (node.getlChild ()! = Null) {// Jika itu adalah node daun, itu akan mengakhiri output (node.getlChild ()); } System.out.print (node.getData ()); // Transaksi termasuk traversal preorder (root kiri dan kanan), traversal in-order (kanan root kanan), dan postorder traversal (root kiri) if (node.getRChild ()! = Null) {output (node.getrChild ()); }} public static void main (string [] args) {formalUetree tree = new FormAluetree (); tree.creattree ("45+23*56/2-5"); // Buat pohon biner dari pohon ekspresi.output (); // verifikasi output}} Akhirnya, Anda dapat mengeluarkan "45+23*56/2-5" di konsol, OK. Dalam urutan tengah traversal yang digunakan di sini, teman -teman dapat mencoba apa efeknya menggunakan traversal preorder dan postorder traversal. Adapun Traversal, kita akan membicarakannya nanti.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.