Trích:
| Viết thủ tục chuyển một danh sách liên kết kép thành một cây nhị phân tìm kiếm, không cấp phát thêm bộ nhớ, chỉ thay đổi các liên kết.
|
1 node của danh sách kép được định nghĩa ( dùng luôn cho cây nhị phân luôn)
struct Node2ptr{
kiểu Info;
Node2ptr *left, *right;
};
Thuat toan chen 1 node q vao cay nhi phan tim kiem
void ChenBST(Node2ptr *&T, Node2ptr *q){
if(T==NULL) T=q;
else if(T->Info > q->Info) ChenBST(T->left, q);
else if(T->Info < q->Info) ChenBST(T->right, q);
cout<<” ko chen, vi cay BST khong co gia tri trung”;
}
Thuat toan chuyen danh sach lien ket kep thanh cay nhi phan tim kiem T
void Chuyen(Node2ptr*& first, Node2ptr*&T){
T = NULL;
While(first !=NULL){
Node2ptr *q = first;
first = q -> right;
q ->left = q->right = NULL;
ChenBST(T, q);
}
}