Cho một cây nhị phân. Nhiệm vụ là hoán đổi từng cặp các nút lá, chẳng hạn -
Đầu vào -
Đầu ra -
Chúng tôi sẽ theo dõi hai con trỏ trỏ đến hai nút lá liền kề và hoán đổi giá trị của chúng trong bài toán đã cho.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi đi ngang cây, tìm các nút lá và theo dõi bộ đếm của chúng tôi để kiểm tra số lượng hiện tại. Bí quyết chính là bộ đếm của chúng tôi là kỳ lạ, vì vậy con trỏ đầu tiên của chúng tôi trỏ đến nút đó ngay bây giờ. Khi bộ đếm của chúng tôi trở nên đồng đều, chúng tôi hoán đổi dữ liệu và do đó các nút lá của chúng tôi được hoán đổi.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
struct Node{ // structure of our tree node
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // the swapping utility function
Node * temp = *a;
*a = *b;
*b = temp;
}
/********Pointers for leaf nodes for swapping********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//recursive function for
//Swapping leaf nodes
if (!(*root)) // if root is null we return
return;
if(!(*root)->left &&!(*root)->right){ // condition for leaf node
secondleaf = root; // now we firstly make our second pointer point to this node
count++; // we also increment the count
if (count%2 == 0) // now if our count is even that means we have a pair so we can swap them
Swap(firstleaf, secondleaf);
else // if count is odd so that means we only got first node yet
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // function for initializing new node
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // inorder traversal function
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* Creating binary tree*/
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
int count = 0; // out counter for keeping track of leaf nodes
SwapTheLeafNodes(&root, count); // swapping the nodes
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
} Đầu ra
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
Giải thích về Quy tắc trên
Trong cách tiếp cận trên, chúng tôi chỉ đơn giản là tạo ra hai con trỏ sẽ theo dõi các nút lá của chúng tôi. Chúng ta đi ngang qua cây khi gặp một nút lá. Đầu tiên, chúng tôi làm cho con trỏ thứ hai trỏ đến nút đó, bây giờ chúng tôi tăng một biến đếm ngay bây giờ nếu số của chúng tôi là chẵn, vì vậy chúng tôi hoán đổi các nút và nếu số đếm là lẻ, điều đó có nghĩa là chúng tôi chỉ tìm thấy phần tử đầu tiên của cặp của chúng tôi, vì vậy chúng tôi lưu trữ giá trị đó trong con trỏ đầu tiên và đây là cách hàm của chúng tôi hoạt động.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết vấn đề về hoán đổi cặp nút lá trong cây nhị phân. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.