Rumah  >  Artikel  >  pembangunan bahagian belakang  >  Tambahkan semua nilai yang lebih besar dalam pepohon carian binari yang diberikan kepada setiap nod

Tambahkan semua nilai yang lebih besar dalam pepohon carian binari yang diberikan kepada setiap nod

WBOY
WBOYke hadapan
2023-09-07 12:17:041281semak imbas

Tambahkan semua nilai yang lebih besar dalam pepohon carian binari yang diberikan kepada setiap nod

BST atau Binary Search Tree ialah satu bentuk pepohon binari di mana semua nod kiri mempunyai nilai kurang daripada nilai nod akar dan semua nod kanan mempunyai nilai lebih besar daripada nilai nod akar. Untuk masalah ini, kami akan mengambil pokok binari dan menambah padanya semua nilai yang lebih besar daripada nilai nod semasa. Masalah "menambah semua nilai yang lebih besar pada setiap nod BST" dipermudahkan kepada, untuk BST, menambah semua nilai nod yang lebih besar daripada nilai nod semasa kepada nilai nod itu.

Tambah semua nod nilai yang lebih besar pada setiap nod dalam Pernyataan Masalah BST:

Memandangkan Pokok Carian Binari (BST), kita perlu menambah untuk setiap nod jumlah semua nod nilai yang lebih besar. .

Tambah semua nilai yang lebih besar pada setiap nod dalam penyelesaian pokok carian binari:

Kami menggunakan reverse inorder traversal (secara rekursif memanggil subtree kanan dahulu bukannya subtree kiri), dan mengekalkan pembolehubah untuk menyimpan Jumlah nod yang telah dilalui setakat ini.

Kami kemudian menggunakan jumlah ini untuk mengubah suai nilai nod semasa, mula-mula menambah nilainya pada jumlah, dan kemudian menggantikan nilai nod dengan jumlah ini.

Contoh

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5

Atas ialah kandungan terperinci Tambahkan semua nilai yang lebih besar dalam pepohon carian binari yang diberikan kepada setiap nod. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam
Artikel sebelumnya:nombor dodekagon pusatArtikel seterusnya:nombor dodekagon pusat