02/10/2018, 14:18
Sao chép 2 cây nhị phân (Binary tree)
Để sao chép 2 cây nhị phân các bạn có thể làm như sau: void copy(Tree t, Tree &q, int pos) // pos == 0 ben trai, pos==1 ben phai { if (t == NULL) return; Node * p = getNode(t->info); if (q == NULL) q = p; else { if (pos == 0) ...
Để sao chép 2 cây nhị phân các bạn có thể làm như sau:
void copy(Tree t, Tree &q, int pos) // pos == 0 ben trai, pos==1 ben phai
{
if (t == NULL)
return;
Node * p = getNode(t->info);
if (q == NULL)
q = p;
else
{
if (pos == 0)
q->pLeft = p;
else
q->pRight = p;
}
copy(t->pLeft, p, 0); // xay cay con ben trai
copy(t->pRight, p, 1); // xay cay con ben phai
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void copy(Tree t, Tree &q, int pos) // pos == 0 ben trai, pos==1 ben phai { if (t == NULL) return; Node * p = getNode(t->info); if (q == NULL) q = p; else { if (pos == 0) q->pLeft = p; else q->pRight = p; } copy(t->pLeft, p, 0); // xay cay con ben trai copy(t->pRight, p, 1); // xay cay con ben phai } |
Để sao chép dễ dàng nhất, chúng ta bắt đầu sao chép từ trên xuống.
1. Ý tưởng thuật toán sao chép 2 cây nhị phân
Mình sẽ khởi tạo Tree q = NULL (chính là đối tượng sẽ nhận dữ liệu sao chép).
- Nếu ban đầu q==NULL, có nghĩa nó sẽ là gốc của cây, khi đó mình sẽ new 1 Node có giá trị là t->info, rồi gán địa chỉ qua là xong.
- Sau khi có Node gốc vd như trên hình là (3). mình sẽ đi vào các nhánh con của nó để sao chép tiếp. Dễ dàng thấy, mình cũng sẽ new ra 1 node mới và điều quan trọng là lấy node số (3) trỏ xuống thằng vừa tạo ra. Tuy nhiên Node ngoài info, thì nó sẽ chứa 2 thông tin là pLeft và pRight. Như vậy bạn cần xác định là pLeft hay pRight trỏ vào node bạn vừa tạo.
- Chính vì vậy, bạn sẽ có biến pos để quy định điều đó.
- Node * q (hay Tree q) truyền vào hàm, lúc này như là cha của thằng mình sẽ new node.
- Cứ như vậy bạn thực hiện đến khi đi hết cây dữ liệu gốc. (Tree: t = NULL)
2. Code thuật toán sao chép cây nhị phân c++
#include <iostream>
using namespace std;
struct Node
{
int info;
Node *pLeft;
Node *pRight;
};
typedef Node* Tree;
void init(Tree &t)
{
t = NULL;
}
Node* getNode(int x)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->info = x;
p->pLeft = NULL;
p->pRight = NULL;
return p;
}
int insert(Tree &t, int x)
{
if (t == NULL)
{
t = getNode(x);
return 1;
}
if (t->info > x)
return insert(t->pLeft, x);
if (t->info < x)
return insert(t->pRight, x);
return 0;
}
void LNR(Tree t)
{
if (t == NULL)
return;
LNR(t->pLeft);
cout << t ->info << " " << t << endl;
LNR(t->pRight);
}
void copy(Tree t, Tree &q, int pos) // pos == 0 ben trai, pos=1 ben phai
{
if (t == NULL)
return;
Node * p = getNode(t->info);
if (q == NULL)
q = p;
else
{
if (pos == 0)
q->pLeft = p;
else
q->pRight = p;
}
copy(t->pLeft, p, 0); // xay cay con ben trai
copy(t->pRight, p, 1); // xay cay con ben phai
}
int main()
{
Tree t1,t2;
init(t1);
insert(t1, 3);
insert(t1, 4);
insert(t1, 12);
insert(t1, 1);
insert(t1, -2);
insert(t1, 2);
LNR(t1);
cout << endl;
init(t2);
copy(t1, t2, 0);
LNR(t2);
cout << endl;
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <iostream> using namespace std; struct Node { int info; Node *pLeft; Node *pRight; }; typedef Node* Tree; void init(Tree &t) { t = NULL; } Node* getNode(int x) { Node* p = new Node; if (p == NULL) return NULL; p->info = x; p->pLeft = NULL; p->pRight = NULL; return p; } int insert(Tree &t, int x) { if (t == NULL) { t = getNode(x); return 1; } if (t->info > x) return insert(t->pLeft, x); if (t->info < x) return insert(t->pRight, x); return 0; } void LNR(Tree t) { if (t == NULL) return; LNR(t->pLeft); cout << t ->info << " " << t << endl; LNR(t->pRight); } void copy(Tree t, Tree &q, int pos) // pos == 0 ben trai, pos=1 ben phai { if (t == NULL) return; Node * p = getNode(t->info); if (q == NULL) q = p; else { if (pos == 0) q->pLeft = p; else q->pRight = p; } copy(t->pLeft, p, 0); // xay cay con ben trai copy(t->pRight, p, 1); // xay cay con ben phai } int main() { Tree t1,t2; init(t1); insert(t1, 3); insert(t1, 4); insert(t1, 12); insert(t1, 1); insert(t1, -2); insert(t1, 2); LNR(t1); cout << endl; init(t2); copy(t1, t2, 0); LNR(t2); cout << endl; return 0; } |
