Cari laluan palindrom terkecil dari segi leksikografi dalam pokok binari

Pokok binari ialah struktur data asas dalam sains komputer, menyediakan cara yang cekap untuk menyusun data secara hierarki. Apabila melintasi pokok-pokok ini, kita sering menemui masalah pengiraan yang menarik. Antaranya, menentukan laluan palindromik terkecil dari segi leksikografi adalah satu cabaran yang menarik. Artikel ini menggambarkan algoritma C++ yang cekap untuk menyelesaikan masalah ini dan menyediakan contoh terperinci untuk pemahaman yang lebih baik.

Pernyataan Masalah

Dalam pepohon binari di mana setiap nod mewakili huruf Inggeris huruf kecil, matlamat kami adalah untuk mencari laluan palindrom terkecil dari segi leksikografi. Jika berbilang laluan sepadan dengan kriteria, kami boleh mengembalikan mana-mana laluan. Jika tiada laluan palindrom wujud, kita harus mengembalikan rentetan kosong.

Kaedah

Penyelesaian kami untuk masalah ini melibatkan merentasi pokok binari menggunakan teknik carian pertama mendalam (DFS). Kaedah DFS membolehkan kita meneroka setiap laluan dari nod akar ke nod daun.

Penyelesaian C++

Ini adalah kod C++ yang melaksanakan kaedah di atas -

Contoh

#include<bits/stdc++.h>
using namespace std;

struct Node {
   char data;
   Node *left, *right;
   Node(char c) : data(c), left(NULL), right(NULL) {}
};

string smallestPalindrome(Node* node, string s) {
   if(node == NULL)
      return "";
   
   s += node->data;
   
   if(node->left == NULL && node->right == NULL)
      return string(s.rbegin(), s.rend()) == s ? s : "";
   
   string left = smallestPalindrome(node->left, s);
   string right = smallestPalindrome(node->right, s);
   
   if(left == "")
      return right;
   if(right == "")
      return left;
   
   return min(left, right);
}

string smallestPalindromicPath(Node* root) {
   return smallestPalindrome(root, "");
}

int main() {
   Node* root = new Node('a');
   root->left = new Node('b');
   root->right = new Node('a');
   root->left->left = new Node('a');
   root->left->right = new Node('a');
   root->right->left = new Node('b');
   root->right->right = new Node('a');
   
   cout << smallestPalindromicPath(root) << endl;
   
   return 0;
}

Output

aaa

Kes ujian dan arahan

Mari kita semak pokok binari dengan struktur berikut -

     a
   /   \
  b     a
 / \   / \
a   a b   a

Dalam pokok binari ini, terdapat berbilang laluan dari nod akar ke nod daun. Di antara semua laluan ini, fungsi mengembalikan laluan palindrom terkecil dari segi leksikografi. Dalam kes ini, laluan palindrom yang mungkin adalah "aaa" dan "aba". Oleh itu, output akan menjadi "aaa", yang merupakan laluan palindrom terkecil dari segi leksikografi.

Kesimpulan

Menentukan laluan palindrom minimum dari segi leksikografi dalam pokok binari ialah masalah menarik yang menggabungkan lintasan pokok dan konsep manipulasi rentetan. Penyelesaian C++ yang disediakan di atas menggunakan pendekatan carian mendalam pertama untuk menyelesaikan masalah ini dengan berkesan. Memahami masalah ini boleh meningkatkan pemahaman anda tentang pokok binari dan meningkatkan keupayaan anda untuk menyelesaikan masalah sains komputer.

Atas ialah kandungan terperinci Cari laluan palindrom terkecil dari segi leksikografi dalam pokok binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!