回顾一下HB(k)树的定义：
HB(k)树要么是空树要么是满足如下条件的二叉搜索树：
其左右子树均为HB(k)树，且右子树高度和左子树高度差的绝对值小于等于k.
现在给定从小到大排序的N个关键码,现要构造出这些关键码对应的所有HB(k)树，算法如下(C++实现)
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory>
#include <stack>
#include <map>
using namespace std;
const long long k = 2;
template <typename T>
struct HB_kTreeNode //AVL树节点类
{
long long bf; //节点平衡因子
T data; //节点数据域
HB_kTreeNode* left;
HB_kTreeNode* right;
HB_kTreeNode(long long b, const T& d) :bf(b), data(d), left(nullptr), right(nullptr) {}
HB_kTreeNode(const HB_kTreeNode& copy) :bf(copy.bf), data(copy.data), left(nullptr), right(nullptr) {}
HB_kTreeNode(const T& d) :data(d), left(nullptr), right(nullptr) {}
};
template <typename T>
bool CompareHB_KTree(HB_kTreeNode<T> *root1, HB_kTreeNode<T>* root2)
{
if (root1 != nullptr || root2 != nullptr)
{
if (root1 == nullptr || root2 == nullptr)
return false;
if (root1->data != root2->data)
return false;
if (CompareHB_KTree(root1->left, root2->left) && CompareHB_KTree(root1->right, root2->right))
return true;
return false;
}
return true;
}
struct record
{
size_t left; //HB(k)树对应的关键码序列起始点下标
size_t right; //HB(k)树对应的关键码序列终止点下标
long long H; //HB(k)树高度
record(size_t l, size_t r, long long H) :left(l), right(r), H(H) {}
bool operator<(const record& r) const
{
if (left < r.left)
return true;
if (left > r.left)
return false;
if (right < r.right)
return true;
if (right > r.right)
return false;
if (H < r.H)
return true;
if (H > r.H)
return false;
return false;
}
};
template<typename T>
HB_kTreeNode<T>* copyTree(HB_kTreeNode<T>* root)
{
if (root == nullptr)
return nullptr;
HB_kTreeNode<T>* _new = new HB_kTreeNode<T>(*root);
_new->left = copyTree(root->left);
_new->right = copyTree(root->right);
return _new;
}
pair<size_t, size_t> getIntersection(pair<size_t, size_t> l, pair<size_t, size_t> j) //返回区间l,j的交区间,l,g左右端点均为正整数,返回(0,0)表示交集不存在
{
if (l.second < j.first || l.first > j.second)
return { 0 , 0 };
if (j.first <= l.first)
{
if (j.second < l.second)
return {l.first, j.second};
return l;
}
if (j.second <= l.second)
return j;
return { j.first, l.second };
}
template <typename T>
size_t select(size_t value, const vector<T>& key_seq)
{
if (value > key_seq.size())
return key_seq.size();
return value;
}
size_t select(size_t end, size_t max)
{
if (end <= max)
return 0;
return end - max;
}
template <typename T>
void constructHB_kTree(long long H, const vector<T> &key_seq, size_t start, size_t end, vector<HB_kTreeNode<T> *> &result, const vector<size_t> &Nh_max, const vector<size_t> &Nh_min,
map<record, shared_ptr<vector<HB_kTreeNode<T>*>>> &has_computed)
{
if (H == 0) //高度为0，无树
{
result.push_back(nullptr);
return;
}
long long K = min(H - 1, k);
if (K != 0)
{ //start + Nh_max[H - 1] >= end - Nh_max[H - 1]总为真,因为调用函数时高为H的HBk树总存在
pair<size_t, size_t> cur;
long long i = K;
while ((cur = getIntersection(make_pair(start + Nh_min[H - 1 - i], select(start + Nh_max[H - 1 - i], key_seq)), make_pair(select(end, Nh_max[H - 1]), end - Nh_min[H - 1]))) == pair<size_t, size_t>(0, 0))
{
--i;
}
//循环结束后i>=0总成立理由同上
pair<size_t, size_t> cur_symmetric(end + start - cur.second, end + start - cur.first);
size_t left_start = cur.first - 1;
cur.first = 0;
cur.second -= left_start + 1;
vector<shared_ptr<vector<HB_kTreeNode<T>*>>> left(cur.second + 1, nullptr);
size_t right_start = cur_symmetric.second - 1;
cur_symmetric.first = cur_symmetric.second - cur_symmetric.first;
cur_symmetric.second = 0;
size_t pos_right_most = cur.second;
vector<shared_ptr<vector<HB_kTreeNode<T>*>>> right(cur_symmetric.first + 1, nullptr);
for (; i > 0; --i) //i == K处理完后退出
{
processLeft(left_start, i, H, cur, key_seq, start, end, Nh_max, Nh_min, left, result, has_computed); //处理左子树
processRight(right_start, i, H, cur_symmetric, key_seq, start, end, Nh_max, Nh_min, right, result, has_computed); //处理右子树
pair<size_t, size_t> after = getIntersection(make_pair(start + Nh_min[H - i], select(start + Nh_max[H - i], key_seq)), make_pair(select(end, Nh_max[H - 1]), end - Nh_min[H - 1]));
if (after == pair<size_t, size_t>(0, 0))
break;
cur_symmetric.first = right_start - (end + start - after.second) + 1;
cur_symmetric.second = right_start - (end + start - after.first) + 1;
after.first -= left_start + 1;
after.second -= left_start + 1;
if (after.second > pos_right_most)
{
left.resize(after.second + 1, nullptr);
pos_right_most = after.second;
right.resize(cur_symmetric.first + 1, nullptr);
}
cur = after;
}
if (i == 0)
processWhenBfEqualZero(right_start, left_start, H, cur, key_seq, start, end, Nh_max, Nh_min, left, right, result, has_computed); //处理左右子树高度相等的情形
}
else
{
result.push_back(new HB_kTreeNode<T>(0, key_seq[start - 1]));
}
}
enum class flag { left_visited, right_visited, non_visited };
template <typename T>
void constructSubTree (size_t offset, long long bf, const shared_ptr<vector<HB_kTreeNode<T>*>> &left_result, const shared_ptr<vector<HB_kTreeNode<T>*>>& right_result, const vector<T>& key_seq, vector<HB_kTreeNode<T>*>& result, bool left_visited, bool right_visited)
{
for (size_t j = 0; j < left_result->size(); ++j)
{
for (size_t m = 0; m < right_result->size(); ++m)
{
HB_kTreeNode<T>* root = new HB_kTreeNode<T>(bf, key_seq[offset]);
if (!left_visited && m == 0)
root->left = (*left_result)[j];
else
root->left = copyTree((*left_result)[j]);
if (!right_visited && j == 0)
root->right = (*right_result)[m];
else
root->right = copyTree((*right_result)[m]);
result.push_back(root);
}
}
}
template <typename T>
bool avoidCall(map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed, long long H, size_t start, size_t end, shared_ptr<vector<HB_kTreeNode<T>*>> &result,
const vector<T>& key_seq, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min)
{
auto t = has_computed.find(record(start, end, H - 1));
if (t != has_computed.end())
{
result = t->second;
return true;
}
else
{
constructHB_kTree(H - 1, key_seq, start, end, *result, Nh_max, Nh_min, has_computed);
has_computed.insert(make_pair(record(start, end, H - 1), result));
return false;
}
}
template <typename T>
void processWhenBfEqualZero(size_t right_start, size_t left_start, long long H, const pair<size_t, size_t>& cur, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& left, vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& right, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
for (size_t run = cur.first; run <= cur.second; ++run)
{
shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();
bool left_visited;
if (right[right_start- run -left_start] == nullptr)
{
left_visited = avoidCall(has_computed, H, start, run + left_start, left_result, key_seq, Nh_max, Nh_min);
right[right_start - run - left_start] = left_result;
}
else
{
left_visited = true;
left_result = right[right_start - run - left_start];
}
bool right_visited;
if (left[run] == nullptr)
{
right_visited = avoidCall(has_computed, H, run + left_start + 2, end, right_result, key_seq, Nh_max, Nh_min);
left[run] = right_result;
}
else
{
right_result = left[run];
right_visited = true;
}
constructSubTree(run + left_start, 0, left_result, right_result, key_seq, result, left_visited, right_visited);
}
}
template <typename T>
void processLeft(size_t left_start, const long long& i, long long H, const pair<size_t, size_t>& cur, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& left, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
for (size_t run = cur.first; run <= cur.second; ++run)
{
shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();
bool left_visited;
left_visited = avoidCall(has_computed, H - i, start, run + left_start, left_result, key_seq, Nh_max, Nh_min);
bool right_visited;
if (left[run] == nullptr)
{
right_visited = avoidCall(has_computed, H, run + left_start + 2, end, right_result, key_seq, Nh_max, Nh_min);
left[run] = right_result;
}
else
{
right_result = left[run];
right_visited = true;
}
constructSubTree(left_start + run, i, left_result, right_result, key_seq, result, left_visited, right_visited);
}
}
template <typename T>
void processRight(size_t right_start, const long long& i, long long H, const pair<size_t, size_t>& cur_symmetric, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& right, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
for (size_t run = cur_symmetric.second; run <= cur_symmetric.first; ++run)
{
shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();
bool left_visited;
if (right[run] == nullptr) //子树未求出，递归调用求子树
{
left_visited = avoidCall(has_computed, H, start, right_start - run, left_result, key_seq, Nh_max, Nh_min);
right[run] = left_result;
}
else
{
left_visited = true; //子树已求出，直接使用现成结果
left_result = right[run];
}
bool right_visited;
right_visited = avoidCall(has_computed, H - i, right_start - run + 2, end, right_result, key_seq, Nh_max, Nh_min);
constructSubTree(right_start - run, -i, left_result, right_result, key_seq, result, left_visited, right_visited);
}
}
template <typename T>
int Searchd(HB_kTreeNode<T>* ptr, int d)
{
if (d == 2)
return 0;
else
{
if (d == 1)
{
if (ptr->right == nullptr)
return 0;
else
return 2;
}
else
{
if (ptr->left != nullptr)
return 1;
else
{
if (ptr->right != nullptr)
return 2;
else
return 0;
}
}
}
}
template <typename T>
bool isHBTree(HB_kTreeNode<T> *root) //判断以root为根节点的二叉树是否为AVL树
{
struct memory
{
HB_kTreeNode<T>* p;
int direction;
T lmin;
int lh = 0; //节点左子树高度
memory(HB_kTreeNode<T>* p, int d) :p(p), direction(d) {}
};
T rmin;
T rmax;
T lmax;
int rh;
int d = 0;
HB_kTreeNode<T>* ptr = root;
HB_kTreeNode<T>* const dest = ptr;
stack<memory> arrange;
bool TF = false;
while (true)
{
if (Searchd(ptr, d) == 0)
{
if (ptr == dest)
{
if (d == 0)
return true;
}
if (d == 0)
{
if (arrange.top().direction == 1)
{
arrange.top().lh = 1;
arrange.top().lmin = ptr->data;
lmax = ptr->data;
}
else
{
rh = 1;
rmin = ptr->data;
rmax = ptr->data;
}
}
else
{
if (d == 1)
{
if (lmax >= ptr->data)
{
cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
return false;
}
if (arrange.top().lh > k)
{
cout << "存在左右子树高度差绝对值大于" << k << "的子树,原树非HB(" << k << ")树" << endl;
return false;
}
if (ptr == dest)
return true;
T lmin = arrange.top().lmin;
int lh = arrange.top().lh;
arrange.pop();
if (arrange.top().direction == 1)
{
arrange.top().lmin = lmin;
arrange.top().lh = lh + 1;
lmax = ptr->data;
}
else
{
rmin = lmin;
rmax = ptr->data;
rh = lh + 1;
}
}
else
{
if (rmin <= ptr->data)
{
cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
return false;
}
if (abs(rh - arrange.top().lh) > k)
{
cout << "存在左右子树高度差绝对值大于" << k << "的子树,原树非HB(" << k << ")树" << endl;
return false;
}
if (ptr == dest)
return true;
if (ptr->left == nullptr)
{
arrange.pop();
if (arrange.top().direction == 1)
{
arrange.top().lmin = ptr->data;
lmax = rmax;
arrange.top().lh = rh + 1;
}
else
{
rmin = ptr->data;
++rh;
}
}
else
{
T lmin = arrange.top().lmin;
int lh = arrange.top().lh;
arrange.pop();
if (arrange.top().direction == 1)
{
arrange.top().lmin = lmin;
arrange.top().lh = max(lh, rh) + 1;
lmax = rmax;
}
else
{
rmin = lmin;
rh = max(lh, rh) + 1;
}
}
}
}
ptr = arrange.top().p;
d = arrange.top().direction;
}
else
{
HB_kTreeNode<T>* interval = nullptr;
if (d == 0)
{
arrange.push(memory(ptr, Searchd(ptr, d)));
if (arrange.top().direction == 1)
ptr = ptr->left;
else
ptr = ptr->right;
}
else
{
if (ptr->data <= lmax)
{
cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
return false;
}
arrange.top().direction = 2;
ptr = ptr->right;
}
d = 0;
}
}
}
template <typename T>
void delHB_kTree(HB_kTreeNode<T>* root)
{
if (root == nullptr)
return;
delHB_kTree(root->left);
delHB_kTree(root->right);
delete root;
}
/*template <typename T>
shared_ptr<vector<HB_kTreeNode<T>*>> constructBinaryTree(vector<T>& inorder_traversal, size_t left_index, size_t right_index)
{
if (left_index > right_index) //二叉树为空树，直接返回空根节点
{
return make_shared<vector<HB_kTreeNode<T>*>>(1, nullptr);
}
shared_ptr<vector<HB_kTreeNode<T>*>> root_node_list = make_shared<vector<HB_kTreeNode<T>*>>(); //当前中序序列对应的所有二叉树的根节点表
for (size_t i = left_index - 1; i < right_index; ++i)
{
shared_ptr<vector<HB_kTreeNode<T>*>> left_sub(constructBinaryTree(inorder_traversal, left_index, i)); //构造所有左子树
shared_ptr<vector<HB_kTreeNode<T>*>> right_sub(constructBinaryTree(inorder_traversal, i + 2, right_index)); //构造所有右子树
for (size_t j = 0; j < left_sub->size(); ++j)
{
for (size_t k = 0; k < right_sub->size(); ++k) //由构造出的左右子树合成当前中序序列对应的所有二叉树
{
HB_kTreeNode<T>* root = new HB_kTreeNode<T>(inorder_traversal[i]);
if (k == 0)
root->left = (*left_sub)[j];
else
root->left = copyTree((*left_sub)[j]);
if (j == 0)
root->right= (*right_sub)[k];
else
root->right = copyTree((*right_sub)[k]);
root_node_list->push_back(root);
}
}
}
return root_node_list;
}*/
int main()
{
const size_t N = 10; //节点数目
vector<size_t> Nh_max(1, 0); //各指定高度的HB(k)树最大节点数
vector<size_t> Nh_min(1, 0); //各指定高度的HB(k)树最小节点数
vector<int> key_seq(N); //关键码序列
vector<HB_kTreeNode<int>*> result; //构造结果
for (size_t i = 0; i < N; ++i)
{
key_seq[i] = i + 1;
}
map<record, shared_ptr<vector<HB_kTreeNode<int>*>>> has_computed;
while (true)
{
if (Nh_min.back() <= key_seq.size() && key_seq.size() <= Nh_max.back()) //节点数在最大数最小数之间，对应的HB(k)树存在，执行构造算法
{
constructHB_kTree(Nh_min.size() - 1, key_seq, 1, key_seq.size(), result, Nh_max, Nh_min, has_computed);
}
if (k > Nh_min.size() - 1)
Nh_min.push_back(Nh_min.back() + 1);
else
Nh_min.push_back(Nh_min[Nh_min.size() - 1 - k] + Nh_min.back() + 1);
if (key_seq.size() < Nh_min.back()) //节点数小于最小节点数，此后HB(k)树不存在，结束构造
break;
else
Nh_max.push_back(2 * Nh_max.back() + 1);
}
cout << "共生成了" << result.size() << "棵HB(" << k << ")树"<< endl;
/*shared_ptr<vector<HB_kTreeNode<int>*>> r = constructBinaryTree(key_seq, 1, N);
size_t count = 0;
for (HB_kTreeNode<int>*& go : *r)
{
if (isHBTree(go))
{
++count;
}
}
cout << "一共有" << count << "棵HB树" << endl;
/*for (size_t i = 0; i < result.size(); ++i)
{
if (isHBTree(result[i]) == false)
{
cout << "错误!生成结果中存在非HB(" << k << ")树" << endl;
exit(-1);
}
}
for (size_t i = 0; i < result.size() - 1; ++i)
{
for (size_t j = i + 1; j < result.size(); ++j)
{
if (CompareHB_KTree(result[i], result[j]))
{
cout << "错误生成的HB树中存在相等的一对HB树!" << endl;
exit(-1);
}
}
}
cout << "生成结果正确!" << endl;
for (size_t i = 0; i < result.size(); ++i)
{
delHB_kTree(result[i]);
}
cout << "销毁成功!" << endl; //需要比较一下树是否两两不同 */
return 0;
}N=10显示共有732棵HB(k)树(使用以上代码中的输入数据)