Konsep pohon biner
Pohon biner adalah set node N (n> = 0) yang terbatas. Set ini adalah set kosong (pohon biner kosong), atau terdiri dari simpul akar dan dua pohon biner yang tidak saling berpotongan, masing -masing disebut node akar dan subtree kanan.
Karakteristik pohon biner
Setiap node memiliki paling banyak dua subtree, jadi tidak ada node dengan derajat lebih dari 2 di pohon biner. Setiap simpul di pohon biner adalah objek, dan setiap node data memiliki tiga pointer, yaitu pointer ke induk, anak kiri dan anak kanan. Setiap node terhubung satu sama lain melalui pointer. Hubungan antara pointer yang terhubung adalah semua hubungan ayah-anak.
Definisi node pohon biner
Simpul pohon biner didefinisikan sebagai berikut:
Salinan kode adalah sebagai berikut:
Struct Binarytreenode
{
int m_nvalue;
BinaryTreeNode* m_pleft;
BinaryTreeNode* m_pright;
};
Lima bentuk dasar pohon biner
Pohon biner kosong
Hanya ada satu node root
Simpul root hanya memiliki subtree kiri
Simpul root hanya memiliki subtree yang tepat
Simpul root memiliki subtree kiri dan kanan
Hanya ada dua kasus untuk pohon biasa dengan tiga node: dua atau tiga. Namun, karena pohon biner harus membedakan kiri dan kanan, itu akan berevolusi menjadi lima bentuk berikut:
Pohon biner khusus
Pohon miring
Seperti yang ditunjukkan pada gambar kecil kedua dan ketiga di sub-gambar kedua dari belakang.
Pohon biner penuh
Di pohon biner, jika semua node cabang memiliki subtree kiri dan kanan, dan semua daun berada di lapisan yang sama, pohon biner seperti itu disebut pohon biner penuh. Seperti yang ditunjukkan pada gambar di bawah ini:
Pohon biner lengkap
Pohon yang benar -benar biner berarti bahwa lapisan terakhir penuh di sebelah kiri, sisi kanan mungkin penuh atau tidak, dan sisa lapisan penuh. Pohon biner dengan kedalaman K dan sejumlah node 2^K - 1 adalah pohon biner penuh (pohon biner lengkap). Ini adalah pohon dengan kedalaman K dan tanpa ruang.
Karakteristik pohon biner yang sepenuhnya adalah:
Node daun hanya bisa muncul di dua lapisan terendah.
Daun terendah harus dikonsentrasikan dalam posisi kontinu di sebelah kiri.
Di lapisan kedua dari belakang, jika ada node daun, mereka harus berada di posisi terus menerus di sebelah kanan.
Jika derajat simpul adalah 1, maka simpul hanya memiliki anak kiri.
Untuk pohon biner dengan pohon simpul yang sama, pohon biner lengkap memiliki kedalaman terkecil.
Catatan: Pohon biner penuh harus menjadi pohon biner yang benar -benar, tetapi pohon biner yang benar -benar mungkin bukan pohon biner penuh.
Algoritme adalah sebagai berikut:
Salinan kode adalah sebagai berikut:
bool is_complete (pohon *root)
{
antrian q;
pohon *ptr;
// Lakukan traversal prioritas luas (traversal hierarkis) dan masukkan node nol ke dalam antrian juga
q.push (root);
while ((ptr = q.pop ())! = null)
{
q.push (ptr-> kiri);
q.push (ptr-> kanan);
}
// Tentukan apakah masih ada node yang belum diakses
While (! Q.is_empty ())
{
ptr = q.pop ();
// Jika ada node non-null yang tidak diakses, pohon memiliki kekosongan dan merupakan pohon biner yang tidak lengkap.
if (null! = ptr)
{
mengembalikan false;
}
}
Kembali Benar;
}
Sifat pohon biner
Properti 1 dari pohon biner: Ada paling banyak node 2^(I-1) di lapisan i-th dari pohon biner (i> = 1)
Properti 2 dari pohon biner: pohon biner dengan kedalaman k memiliki paling banyak node 2^k-1 (k> = 1)
Struktur penyimpanan berurutan pohon biner
Struktur penyimpanan berurutan dari pohon biner adalah menggunakan array satu dimensi untuk menyimpan setiap node di pohon biner, dan lokasi penyimpanan node dapat mencerminkan hubungan logis antara node.
Daftar Tautan Biner
Karena metode penyimpanan berurutan tidak terlalu berlaku, kita harus mempertimbangkan struktur penyimpanan rantai. Menurut praktik internasional, penyimpanan pohon biner umumnya mengadopsi struktur penyimpanan rantai.
Setiap simpul pohon biner memiliki paling banyak dua anak, jadi itu adalah ide alami untuk merancang bidang data dan dua bidang pointer untuk itu. Kami menyebut daftar tertaut tersebut sebagai daftar tertaut biner.
Traversal pohon biner
Melintasi pohon biner mengacu pada mengakses semua node di pohon biner dalam urutan tertentu dari node akar, sehingga setiap node diakses sekali dan hanya sekali.
Ada tiga cara untuk melintasi pohon biner, sebagai berikut:
(1) Pre-order Traversal (DLR), pertama mengakses node root, kemudian melintasi subtree kiri, dan akhirnya melintasi subtree kanan. Root Singkat - Kiri - Kanan.
(2) In-order Traversal (LDR), Traversal Pertama Subtree kiri, kemudian mengakses node root, dan akhirnya melintasi subtree kanan. Catatan Singkat: Right-Right Kiri.
(3) Pasca-orde Traversal (LRD), pertama-tama melintasi subtree kiri, kemudian melintasi subtree kanan, dan akhirnya mengakses node root. Root-right-root-root yang disingkat.
Preamble Traversal:
Jika pohon biner kosong, operasi kosong kembali. Kalau tidak, pertama -tama akses node root, lalu lintasi subtree kiri dalam urutan sebelumnya, dan kemudian lintasi subtree kanan dalam urutan sebelumnya.
Urutan Traversal adalah: Abdhiejcfkg
Salinan kode adalah sebagai berikut:
// traversal yang tepat
function preorder (node) {
if (! node == null) {
putstr (node.show ()+ "");
preorder (node.left);
preorder (node.right);
}
}
Traversal in-order:
Jika pohon kosong, operasi kosong kembali, jika tidak, ia dimulai dari simpul root (perhatikan bahwa simpul root tidak diakses terlebih dahulu), dan subtree kiri dari simpul root dilintasi dalam urutan tengah, maka simpul root diakses, dan akhirnya subtree kanan dilintasi dalam urutan tengah.
Urutan Traversal adalah: hdibeJafkcg
Salinan kode adalah sebagai berikut:
// Gunakan metode rekursif untuk mengimplementasikan traversal urutan menengah
fungsi inorder (node) {
if (! (node == null)) {
inorder (node.left); // Tambahkan ke subtree kiri terlebih dahulu
putstr (node.show ()+ ""); // Tambahkan ke node root lagi
inorder (node.right); // akses terakhir ke subtree kanan
}
}
Traversal pasca-pesanan:
Jika pohon kosong, operasi kosong kembali. Kalau tidak, subtree kiri dan kanan dilintasi dari kiri ke kanan untuk mengakses subtree kiri dan kanan, dan akhirnya mengakses node akar.
Urutan Traversal adalah: hidjebkfgca
Salinan kode adalah sebagai berikut:
// Traversal pasca-pemesanan
function postorder (node) {
if (! node == null) {
Posting (Node.Left);
Posting (Node.Right);
putstr (node.show ()+ "");
}
}
Menerapkan pohon pencarian biner
Pohon pencarian biner (BST) terdiri dari node, jadi kami mendefinisikan objek simpul node sebagai berikut:
Salinan kode adalah sebagai berikut:
node fungsi (data, kiri, kanan) {
this.data = data;
this.left = kiri; // simpan tautan simpul kiri
this.right = benar;
this.show = show;
}
function show () {
kembalikan this.data; // Tampilkan data yang disimpan di node
}
Temukan nilai maksimum dan minimum
Menemukan nilai minimum dan maksimum pada BST sangat sederhana, karena nilai yang lebih kecil selalu pada simpul anak kiri, dan mencari nilai minimum pada BST, cukup lintasi pohon anak kiri sampai simpul terakhir ditemukan
Temukan Nilai Minimum
Salinan kode adalah sebagai berikut:
function getmin () {
var current = this.root;
while (! (current.left == null)) {
arus = arus.Left;
}
return arus.data;
}
Metode ini melintasi satu per satu di sepanjang subtree kiri BST sampai melintasi ke simpul paling kiri BST, yang didefinisikan sebagai:
Salinan kode adalah sebagai berikut:
Current.Left = null;
Saat ini, nilai yang disimpan pada simpul saat ini adalah nilai minimum
Temukan nilai maksimum
Menemukan nilai maksimum pada BST hanya membutuhkan melintasi subtree kanan sampai simpul terakhir ditemukan, dan nilai yang disimpan pada node itu adalah nilai maksimum.
Salinan kode adalah sebagai berikut:
fungsi getmax () {
var current = this.root;
while (! (current.right == null)) {
Current = Current.Right;
}
return arus.data;
}