Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Konsep pohon pencarian biner

Pohon pencarian biner, juga dikenal sebagai pohon pengurutan biner atau pohon pencarian biner, adalah jenis pohon biner yang memiliki tiga karakteristik berikut.

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。
1
2
3

Sederhananya, semua node dari pohon biner ini memenuhi: anak kiri < simpul induk < anak kanan.

Operasi pohon pencarian biner

Pencarian pohon pencarian biner

Pencarian dalam pohon pencarian biner agak mirip dengan pencarian biner. Jika pencarian lebih kecil dari simpul akar, lanjutkan ke subpohon kiri, dan jika lebih besar dari simpul akar, lanjutkan ke subpohon kanan. Tingginya bisa dicari sampai berkali-kali maksimal. Jika sampai kosong dan tidak ditemukan berarti nilainya tidak ada.

Penyisipan pohon pencarian biner

Pertama, ikuti metode pencarian, dan masukkan node saat kosong. Ini menyelesaikan penyisipan pohon pencarian biner.

Penghapusan pohon pencarian biner

Menghapus node di pohon pencarian biner perlu dilakukan sesuai dengan situasi yang berbeda.

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。
1
2
3
4