สมมติว่าเรามีต้นไม้ไบนารีสองทรี เราต้องหาใบแรกของต้นไม้สองต้นที่ไม่ตรงกัน หากไม่มีใบที่ไม่ตรงกันก็ไม่ต้องแสดงอะไร
หากเป็นต้นไม้สองต้น ใบแรกที่ไม่ตรงกันคือ 11 และ 15
ในที่นี้เราจะใช้การสั่งจองล่วงหน้าแบบวนซ้ำของต้นไม้ทั้งสองต้นพร้อมกันโดยใช้สแต็ก เราจะใช้กองที่แตกต่างกันสำหรับต้นไม้ต่างๆ เราจะผลักโหนดเข้าไปในสแต็กจนกว่าโหนดบนสุดจะเป็นโหนดปลายสุด เปรียบเทียบสองตัวบน หากเหมือนกัน ให้ตรวจสอบเพิ่มเติม ไม่เช่นนั้นให้แสดงสององค์ประกอบบนสุดของสแต็ก
ตัวอย่าง
#include <iostream>
#include <stack>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node *getNode(int x) {
Node * newNode = new Node;
newNode->data = x;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLeaf(Node * t) {
return ((t->left == NULL) && (t->right == NULL));
}
void findUnmatchedNodes(Node *t1, Node *t2) {
if (t1 == NULL || t2 == NULL)
return;
stack<Node*> s1, s2;
s1.push(t1); s2.push(t2);
while (!s1.empty() || !s2.empty()) {
if (s1.empty() || s2.empty() )
return;
Node *top1 = s1.top();
s1.pop();
while (top1 && !isLeaf(top1)){
s1.push(top1->right);
s1.push(top1->left);
top1 = s1.top();
s1.pop();
}
Node * top2 = s2.top();
s2.pop();
while (top2 && !isLeaf(top2)){
s2.push(top2->right);
s2.push(top2->left);
top2 = s2.top();
s2.pop();
}
if (top1 != NULL && top2 != NULL ){
if (top1->data != top2->data ){
cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl;
return;
}
}
}
}
int main() {
Node *t1 = getNode(5);
t1->left = getNode(2);
t1->right = getNode(7);
t1->left->left = getNode(10);
t1->left->right = getNode(11);
Node * t2 = getNode(6);
t2->left = getNode(10);
t2->right = getNode(15);
findUnmatchedNodes(t1,t2);
} ผลลัพธ์
First non matching leaves are: 11 15
