No.2 刚写了一个,似乎是对的,只是测试了2个例子:
{9, 4, 14, 2, 8, 10, 16, 1, 3, 7};
//in place swap without using addition variable
void swap(Tree *a, Tree *b)
{
a->element = a->element ^ b->element;
b->element = a->element ^ b->element;
a->element = a->element ^ b->element;
}
void BstToHeap1( Tree *root)
{
if (!root)
return;
BstToHeap1(root->left);
BstToHeap1(root->right);
if (root->right)
swap(root, root->right);
}
void Heapify(Tree *root)
{
if (!root) return;
Heapify(root->left);
Heapify(root->right);
if ((root->left) && (root->left->element > root->element))
swap(root, root->left);
if ((root->right) && (root->right->element > root->element))
swap(root, root->right);
}
void BstToHeap( Tree *root)
{
BstToHeap1(root);
Heapify(root->left);
Heapify(root->right);
return;
}
bst:
9
/ \
/ \
/ \
/ \
4 14
/ \ / \
/ \ / \
/ \ 10 16
2 8
/ \ /
1 3 7
heap:
16
/ \
/ \
/ \
8 14
/ \ / \
/ \ 9 10
/ \
3 7
/ \ /
1 2 4