Post-Order Tree pada C | Rizky Abdul Ghani S

00:21 Pemrograman Web 6 Comments


Dalam ilmu komputer, traversal pohon (juga dikenal sebagai pencarian pohon) adalah bentuk grafik traversal dan mengacu pada proses mengunjungi (memeriksa dan / atau memperbarui) setiap node dalam struktur data pohon, tepat sekali. traversals seperti diklasifikasikan oleh urutan node yang dikunjungi. Algoritma berikut dijelaskan untuk pohon biner, tetapi mereka mungkin digeneralisasi untuk pohon lain juga.
Pohon dapat dilalui dalam pre-order, di-order, atau pasca-order. [1] pencarian ini disebut sebagai pencarian mendalam-pertama (DFS), sebagai pohon pencarian diperdalam sebanyak mungkin pada setiap anak sebelum pergi ke saudara berikutnya. Untuk pohon biner, mereka didefinisikan sebagai operasi layar rekursif pada setiap node, dimulai dengan akar, algoritma yang adalah sebagai berikut:
Pola rekursif umum untuk melintasi (non-kosong) pohon biner adalah ini: Pada simpul N Anda harus melakukan tiga hal ini:
(L) secara rekursif melintasi subpohon kiri. Ketika langkah ini selesai Anda kembali di N lagi.
(R) secara rekursif melintasi subtree kanan. Ketika langkah ini selesai Anda kembali di N lagi.
(N) Sebenarnya memproses N itu sendiri.
Kita mungkin melakukan hal-hal dalam urutan apapun dan masih memiliki traversal yang sah. Jika kita melakukan (L) sebelum (R), kita menyebutnya kiri ke kanan traversal, kalau tidak kita menyebutnya traversal kanan-ke-kiri.
Traversal adalah proses untuk mengunjungi semua node dari pohon dan mungkin mencetak nilai-nilai mereka juga. Karena, semua node yang terhubung melalui tepi (link) kita selalu mulai dari akar (kepala) node. Artinya, kita tidak bisa random akses node di pohon. Ada tiga cara yang kita gunakan untuk melintasi pohon.
  • In-order Traversal
  • Pre-order Traversal
  • Post-order Traversal

Post-Order :
1.       Melintasi subtree kiri oleh rekursif memanggil fungsi pasca-order.
2.       Melintasi subtree kanan oleh rekursif memanggil fungsi pasca-order.
3.       Menampilkan bagian data akar (atau node saat ini).
Jejak traversal yang disebut sequentialisation tree. Jejak traversal adalah daftar setiap akar dikunjungi. Tidak ada satu sequentialisation menurut pra, di-atau pasca-order menggambarkan pohon yang mendasari unik. Mengingat pohon dengan unsur-unsur yang berbeda, baik pre-order atau pasca-order dipasangkan dengan di-order cukup untuk menggambarkan pohon unik. Namun, pre-order dengan pasca-order daun beberapa ambiguitas dalam struktur pohon.
Penggunaan Postorder
Postorder traversal digunakan untuk menghapus pohon. Postorder traversal juga berguna untuk mendapatkan ekspresi postfix dari pohon ekspresi.
Dan ini adalah program Post-Order Tree yang saya buat :

#include <stdio.h>
 #include <stdlib.h>

  struct tnode {
        int angka;
        struct tnode *kiri, *kanan;
  };

  struct tnode *root = NULL;

  struct tnode * BuatNode(int angka) {
        struct tnode *NodeBaru;
        NodeBaru  = (struct tnode *) malloc(sizeof(struct tnode));
        NodeBaru->angka = angka;
        NodeBaru->kiri = NULL;
        NodeBaru->kanan = NULL;
        return (NodeBaru);
  }

  void insertion(struct tnode **node, int angka) {
        if (!*node) {
                *node = BuatNode(angka);
        } else if (angka < (*node)->angka) {
                insertion(&(*node)->kiri, angka);
        } else if (angka > (*node)->angka) {
                insertion(&(*node)->kanan, angka);
        }
  }

  void postOrder(struct tnode *node) {
        if (node) {
                postOrder(node->kiri);
                postOrder(node->kanan);
                printf("%d  ", node->angka);
        }
        return;
  }

  int main() {
        int angka, ch;
        while (1) {
                printf("\n1. Masukan Data");
                printf("\n2. Post-order");
                printf("\n3. Keluar");
                printf("\n\nMasukan pilihan anda : ");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Masukan angka anda : ");
                                scanf("%d", &angka);
                                insertion(&root, angka);
                                break;
                        case 2:
                                postOrder(root);
                                break;
                        case 3:
                                exit(0);
                        default:
                                printf("Pilihan anda salah\n");
                                break;
                }
        }
        return 0;

  }


Rizky Abdul Ghani Suherli
1154058

6 komentar: