树(广义AVL树)实现)
回顾一下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_kTreeNodeT *root1, HB_kTreeNodeT* 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; } }; templatetypename T HB_kTreeNodeT* copyTree(HB_kTreeNodeT* root) { if (root nullptr) return nullptr; HB_kTreeNodeT* _new new HB_kTreeNodeT(*root); _new-left copyTree(root-left); _new-right copyTree(root-right); return _new; } pairsize_t, size_t getIntersection(pairsize_t, size_t l, pairsize_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 vectorT 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 vectorT key_seq, size_t start, size_t end, vectorHB_kTreeNodeT * result, const vectorsize_t Nh_max, const vectorsize_t Nh_min, maprecord, shared_ptrvectorHB_kTreeNodeT* 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树总存在 pairsize_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]))) pairsize_t, size_t(0, 0)) { --i; } //循环结束后i0总成立理由同上 pairsize_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; vectorshared_ptrvectorHB_kTreeNodeT* 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; vectorshared_ptrvectorHB_kTreeNodeT* 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); //处理右子树 pairsize_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 pairsize_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_kTreeNodeT(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_ptrvectorHB_kTreeNodeT* left_result, const shared_ptrvectorHB_kTreeNodeT* right_result, const vectorT key_seq, vectorHB_kTreeNodeT* 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_kTreeNodeT* root new HB_kTreeNodeT(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(maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed, long long H, size_t start, size_t end, shared_ptrvectorHB_kTreeNodeT* result, const vectorT key_seq, const vectorsize_t Nh_max, const vectorsize_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 pairsize_t, size_t cur, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* left, vectorshared_ptrvectorHB_kTreeNodeT* right, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur.first; run cur.second; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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 pairsize_t, size_t cur, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* left, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur.first; run cur.second; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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 pairsize_t, size_t cur_symmetric, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* right, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur_symmetric.second; run cur_symmetric.first; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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_kTreeNodeT* 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_kTreeNodeT *root) //判断以root为根节点的二叉树是否为AVL树 { struct memory { HB_kTreeNodeT* p; int direction; T lmin; int lh 0; //节点左子树高度 memory(HB_kTreeNodeT* p, int d) :p(p), direction(d) {} }; T rmin; T rmax; T lmax; int rh; int d 0; HB_kTreeNodeT* ptr root; HB_kTreeNodeT* const dest ptr; stackmemory 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_kTreeNodeT* 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_kTreeNodeT* root) { if (root nullptr) return; delHB_kTree(root-left); delHB_kTree(root-right); delete root; } /*template typename T shared_ptrvectorHB_kTreeNodeT* constructBinaryTree(vectorT inorder_traversal, size_t left_index, size_t right_index) { if (left_index right_index) //二叉树为空树直接返回空根节点 { return make_sharedvectorHB_kTreeNodeT*(1, nullptr); } shared_ptrvectorHB_kTreeNodeT* root_node_list make_sharedvectorHB_kTreeNodeT*(); //当前中序序列对应的所有二叉树的根节点表 for (size_t i left_index - 1; i right_index; i) { shared_ptrvectorHB_kTreeNodeT* left_sub(constructBinaryTree(inorder_traversal, left_index, i)); //构造所有左子树 shared_ptrvectorHB_kTreeNodeT* 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_kTreeNodeT* root new HB_kTreeNodeT(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; //节点数目 vectorsize_t Nh_max(1, 0); //各指定高度的HB(k)树最大节点数 vectorsize_t Nh_min(1, 0); //各指定高度的HB(k)树最小节点数 vectorint key_seq(N); //关键码序列 vectorHB_kTreeNodeint* result; //构造结果 for (size_t i 0; i N; i) { key_seq[i] i 1; } maprecord, shared_ptrvectorHB_kTreeNodeint* 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_ptrvectorHB_kTreeNodeint* r constructBinaryTree(key_seq, 1, N); size_t count 0; for (HB_kTreeNodeint* 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; }N10显示共有732棵HB(k)树(使用以上代码中的输入数据) 
长河君 · 2026/9/6 14:57:22 · 阅读 1.2k 构造N个节点的所有HB(k)树(广义AVL树)实现
回顾一下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_kTreeNodeT *root1, HB_kTreeNodeT* 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; } }; templatetypename T HB_kTreeNodeT* copyTree(HB_kTreeNodeT* root) { if (root nullptr) return nullptr; HB_kTreeNodeT* _new new HB_kTreeNodeT(*root); _new-left copyTree(root-left); _new-right copyTree(root-right); return _new; } pairsize_t, size_t getIntersection(pairsize_t, size_t l, pairsize_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 vectorT 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 vectorT key_seq, size_t start, size_t end, vectorHB_kTreeNodeT * result, const vectorsize_t Nh_max, const vectorsize_t Nh_min, maprecord, shared_ptrvectorHB_kTreeNodeT* 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树总存在 pairsize_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]))) pairsize_t, size_t(0, 0)) { --i; } //循环结束后i0总成立理由同上 pairsize_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; vectorshared_ptrvectorHB_kTreeNodeT* 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; vectorshared_ptrvectorHB_kTreeNodeT* 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); //处理右子树 pairsize_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 pairsize_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_kTreeNodeT(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_ptrvectorHB_kTreeNodeT* left_result, const shared_ptrvectorHB_kTreeNodeT* right_result, const vectorT key_seq, vectorHB_kTreeNodeT* 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_kTreeNodeT* root new HB_kTreeNodeT(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(maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed, long long H, size_t start, size_t end, shared_ptrvectorHB_kTreeNodeT* result, const vectorT key_seq, const vectorsize_t Nh_max, const vectorsize_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 pairsize_t, size_t cur, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* left, vectorshared_ptrvectorHB_kTreeNodeT* right, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur.first; run cur.second; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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 pairsize_t, size_t cur, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* left, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur.first; run cur.second; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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 pairsize_t, size_t cur_symmetric, const vectorT key_seq, size_t start, size_t end, const vectorsize_t Nh_max, const vectorsize_t Nh_min, vectorshared_ptrvectorHB_kTreeNodeT* right, vectorHB_kTreeNodeT* result, maprecord, shared_ptrvectorHB_kTreeNodeT* has_computed) { for (size_t run cur_symmetric.second; run cur_symmetric.first; run) { shared_ptrvectorHB_kTreeNodeT* left_result make_sharedvectorHB_kTreeNodeT*(); shared_ptrvectorHB_kTreeNodeT* right_result make_sharedvectorHB_kTreeNodeT*(); 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_kTreeNodeT* 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_kTreeNodeT *root) //判断以root为根节点的二叉树是否为AVL树 { struct memory { HB_kTreeNodeT* p; int direction; T lmin; int lh 0; //节点左子树高度 memory(HB_kTreeNodeT* p, int d) :p(p), direction(d) {} }; T rmin; T rmax; T lmax; int rh; int d 0; HB_kTreeNodeT* ptr root; HB_kTreeNodeT* const dest ptr; stackmemory 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_kTreeNodeT* 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_kTreeNodeT* root) { if (root nullptr) return; delHB_kTree(root-left); delHB_kTree(root-right); delete root; } /*template typename T shared_ptrvectorHB_kTreeNodeT* constructBinaryTree(vectorT inorder_traversal, size_t left_index, size_t right_index) { if (left_index right_index) //二叉树为空树直接返回空根节点 { return make_sharedvectorHB_kTreeNodeT*(1, nullptr); } shared_ptrvectorHB_kTreeNodeT* root_node_list make_sharedvectorHB_kTreeNodeT*(); //当前中序序列对应的所有二叉树的根节点表 for (size_t i left_index - 1; i right_index; i) { shared_ptrvectorHB_kTreeNodeT* left_sub(constructBinaryTree(inorder_traversal, left_index, i)); //构造所有左子树 shared_ptrvectorHB_kTreeNodeT* 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_kTreeNodeT* root new HB_kTreeNodeT(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; //节点数目 vectorsize_t Nh_max(1, 0); //各指定高度的HB(k)树最大节点数 vectorsize_t Nh_min(1, 0); //各指定高度的HB(k)树最小节点数 vectorint key_seq(N); //关键码序列 vectorHB_kTreeNodeint* result; //构造结果 for (size_t i 0; i N; i) { key_seq[i] i 1; } maprecord, shared_ptrvectorHB_kTreeNodeint* 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_ptrvectorHB_kTreeNodeint* r constructBinaryTree(key_seq, 1, N); size_t count 0; for (HB_kTreeNodeint* 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; }N10显示共有732棵HB(k)树(使用以上代码中的输入数据)