以以下4叉树为例(K4)结点旁的数字代表结点数据域中存放的值ROOT表示根结点根结点数据域为0问题求K叉树叶子结点的数目和深度解答(C):#include iostream #include vector #include stdio.h #include malloc.h #define K 4 //树的最大分叉数 struct TreeNode //表示K叉树节点的结构体类型 { int data; //节点数据域 TreeNode* Link[K]; //节点指针域,结构体指针数组 }; struct Path //遍历K叉树过程中链表栈的节点 { TreeNode* current; //指向链表节点代表的K叉树节点的指针 int direction; //指向由链表节点代表的K叉树节点的下一个节点的Link数组元素的下标加一后的值 Path(TreeNode* c, int d) :current(c), direction(d) {} }; int ComputeLeaf(TreeNode* root, int* depth); //计算K叉树叶子数目和深度的函数 int Search(TreeNode* ptr, int d); //寻找ptr指向的K叉树节点上从d开始下一可走方向 bool Enable(TreeNode* ptr, int m); //判定在ptr指向的K叉树节点上方向m是否可走 using std::vector; void main() { int i, depth; //depth为K叉树深度 TreeNode *temp1, *temp2; //创建4叉树 TreeNode* root new TreeNode(); root-data 0; root-Link[0] nullptr; for (i 1; i 3; i) { root-Link[i] new TreeNode(); root-Link[i]-data i; } for (i 1; i 4; i) root-Link[1]-Link[i - 1] nullptr; temp1 root-Link[2]; for (i 1; i 4; i) { temp1-Link[i - 1] new TreeNode(); temp1-Link[i - 1]-data i 3; } temp2 temp1-Link[0]; temp2-Link[1] new TreeNode(); temp2-Link[1]-data 10; for (i 1; i 4; i) temp2-Link[1]-Link[i - 1] nullptr; temp2-Link[3] new TreeNode(); temp2-Link[3]-data 11; for (i 1; i 4; i) temp2-Link[3]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[2] nullptr; temp2 temp1-Link[2]; temp2-Link[2] new TreeNode(); temp2-Link[2]-data 12; for (i 1; i 4; i) temp2-Link[2]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[1] temp2-Link[3] nullptr; temp2 temp1-Link[1]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp2 temp1-Link[3]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1 root-Link[3]; temp1-Link[1] new TreeNode(); temp2 temp1-Link[1]; temp2-data 8; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[3] new TreeNode(); temp2 temp1-Link[3]; temp2-data 9; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[0] temp1-Link[2] nullptr; std::cout K叉树的叶子结点数目为 ComputeLeaf(root, depth) std::endl; //计算叶子数目和深度输出叶子数目 std::cout K叉树的深度为 depth - 1; //输出深度 } int ComputeLeaf(TreeNode* root, int* depth) { int i; for (i 0; i K; i) { if (root-Link[i] ! nullptr) break; } if (i K) //K叉树为只有根节点的空树 { *depth 0; return 1; //深度为0,叶子数为1 } else { bool flag false; int d, k; //d为当前方向,k为K叉树层数 int count; //计数变量统计叶子数目 TreeNode *ptr; //ptr指向遍历过程中的当前节点 int interval; ptr root; //ptr初始化指向根节点 d -1; //方向初始化为0 count 0; //计数变量初始化 k 1; //层数初始化 vectorPath stack; while (true) { if ((interval Search(ptr, d)) -1) { if (ptr root) //在根节点无下一可走方向遍历结束退出循环 break; else { if (d -1) //找到一个叶子 { count; //计数变量加一 if (flag false) { *depth k; flag true; //通过比较确定叶子深度最大值求出K叉树深度 } else { if (*depth k) *depth k; } } else { stack.pop_back(); } ptr stack.back().current; //回溯 d stack.back().direction; --k; } } else { if (d -1) { stack.push_back(Path(ptr, interval)); //找到下一个节点当前节点加入路径链表 } else { stack.back().direction interval; //在当前节点找到新方向更新当前节点方向 } ptr ptr-Link[interval]; //递进至下一节点 d -1; k; continue; } } return count; //返回叶子总数 } } int Search(TreeNode* ptr, int d) { for (d; d K; d) { if (Enable(ptr, d)) return d; } return -1; } bool Enable(TreeNode* ptr, int m) { if (ptr-Link[m] ! nullptr) return true; else return false; }以上程序有多个变体详见下文问题求K叉树m层节点总数解答(C)#include iostream #include vector #define K 4 using namespace std; struct TreeNode { int data; struct TreeNode* Link[K]; }; struct Path { TreeNode* current; int direction; Path(TreeNode* c, int d) :current(c), direction(d) {} }; int ComputeLeaf(TreeNode* root, int m); //函数求第m层节点总数 int Search(TreeNode* ptr, int d); bool Enable(TreeNode* ptr, int m); int main() { int i, m; //m指定要搜索结点数目的层数 TreeNode* temp1, * temp2; TreeNode* root new TreeNode(); root-data 0; root-Link[0] nullptr; for (i 1; i 3; i) { root-Link[i] new TreeNode(); root-Link[i]-data i; } for (i 1; i 4; i) root-Link[1]-Link[i - 1] nullptr; temp1 root-Link[2]; for (i 1; i 4; i) { temp1-Link[i - 1] new TreeNode(); temp1-Link[i - 1]-data i 3; } temp2 temp1-Link[0]; temp2-Link[1] new TreeNode(); temp2-Link[1]-data 10; for (i 1; i 4; i) temp2-Link[1]-Link[i - 1] nullptr; temp2-Link[3] new TreeNode(); temp2-Link[3]-data 11; for (i 1; i 4; i) temp2-Link[3]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[2] nullptr; temp2 temp1-Link[2]; temp2-Link[2] new TreeNode(); temp2-Link[2]-data 12; for (i 1; i 4; i) temp2-Link[2]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[1] temp2-Link[3] nullptr; temp2 temp1-Link[1]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp2 temp1-Link[3]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1 root-Link[3]; temp1-Link[1] new TreeNode(); temp2 temp1-Link[1]; temp2-data 8; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[3] new TreeNode(); temp2 temp1-Link[3]; temp2-data 9; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[0] temp1-Link[2] nullptr; cout 请输入想求节点数目的K叉树层数 endl; cin m; //输入想求结点数目的层数 if ((i ComputeLeaf(root, m)) 0) //m层不存在 cout m 超出K叉树深度,第 m 层不存在 endl; cout K叉树第 m 层的结点数目为 i endl; return 0; } int ComputeLeaf(TreeNode* root, int m) { int i; for (i 0; i K; i) { if (root-Link[i] ! NULL) break; } if (i K) { if (m 1) return 1; //第一层一个节点即根节点 else return 0; //其余各层不存在 } else { if (m 1) return 1; else { int d, k; int count; //计数变量统计m层结点数 TreeNode* ptr; int interval; ptr root; d -1; count 0; k 1; vectorPath stack; while (1) { if ((interval Search(ptr, d)) -1) { if (ptr root) break; else { if (d ! -1) { stack.pop_back(); } --k; ptr stack.back().current; d stack.back().direction; } } else { if (d -1) { stack.push_back(Path(ptr, interval)); } else { stack.back().direction Search(ptr, d); } ptr ptr-Link[interval]; d -1; k; if (k m) //到达第m层 { count; //计数变量加一 ptr stack.back().current; d stack.back().direction; //回溯 --k; } } } return count; //返回m层结点总数 } } } int Search(TreeNode* ptr, int d) { for (d; d K; d) { if (Enable(ptr, d)) return d; } return -1; } bool Enable(TreeNode* ptr, int m) { if (ptr-Link[m] ! nullptr) return true; else return false; }问题:在K叉树中搜索给定值m解答(C)#include iostream #include vector #include list #include memory #define K 4 using namespace std; struct TreeNode { int data; TreeNode* Link[K]; }; struct Path { TreeNode* current; int direction; Path(TreeNode* c, int d) :current(c), direction(d) {} }; struct SearchNode //用于存放搜索到的为给定值m项的结构体类型 { int plies; //所在层数 TreeNode* goal; //指向该项的指针 TreeNode* before; //指向该项父结点的指针 SearchNode(int p, TreeNode* g, TreeNode* b) :plies(p), goal(g), before(b) {} SearchNode() :plies(0) {} }; shared_ptrlistSearchNode ComputeLeaf(TreeNode* root, int m, int count); //函数在K叉树中搜索给定值m统计K叉树中值为m的结点个数返回SearchNode1链表头结点 void Order(int i, int m, int number, listSearchNode::iterator before, TreeNode* root, int plies, listSearchNode::iterator Location); //函数输出以*Location为起点,before为终点的SearchNode1链表段中各结点项位置 int Search(TreeNode* ptr, int d); bool Enable(TreeNode* ptr, int m); int main() { int i, m, count 0, number 0; //m为要搜索的值,count为m项总数 TreeNode* temp1, * temp2; TreeNode* root new TreeNode(); root-data 0; root-Link[0] nullptr; for (i 1; i 3; i) { root-Link[i] new TreeNode(); root-Link[i]-data i; } for (i 1; i 4; i) root-Link[1]-Link[i - 1] nullptr; temp1 root-Link[2]; for (i 1; i 4; i) { temp1-Link[i - 1] new TreeNode(); temp1-Link[i - 1]-data i 3; } temp2 temp1-Link[0]; temp2-Link[1] new TreeNode(); temp2-Link[1]-data 10; for (i 1; i 4; i) temp2-Link[1]-Link[i - 1] nullptr; temp2-Link[3] new TreeNode(); temp2-Link[3]-data 11; for (i 1; i 4; i) temp2-Link[3]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[2] nullptr; temp2 temp1-Link[2]; temp2-Link[2] new TreeNode(); temp2-Link[2]-data 12; for (i 1; i 4; i) temp2-Link[2]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[1] temp2-Link[3] nullptr; temp2 temp1-Link[1]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp2 temp1-Link[3]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1 root-Link[3]; temp1-Link[1] new TreeNode(); temp2 temp1-Link[1]; temp2-data 8; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[3] new TreeNode(); temp2 temp1-Link[3]; temp2-data 9; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[0] temp1-Link[2] nullptr; for (i 0; i K; i) { if (root-Link[i] ! NULL) { break; } } cout 请输入要在K叉树中搜索的值; cin m; //输入要搜索的值 shared_ptrlistSearchNode head nullptr; if ((head ComputeLeaf(root, m, count))-size() 1) //m项不存在 { cout m 在K叉树中不存在 endl; cout K叉树中共有 count 个 m 项 endl; } else { listSearchNode::iterator before head-begin(); listSearchNode::iterator after before; after; listSearchNode::iterator Location after; while (after ! head-end()) { if (before-plies after-plies) //按层数由小到大,每层从左至右的顺序输出所有m项位置 { if (before ! head-begin()) { Order(i, m, number, before, root, before-plies, Location); } } after; before; } Order(i, m, number, before, root, before-plies, Location); cout K叉树中共有 count 个 m 项 endl; } return 0; } shared_ptrlistSearchNode ComputeLeaf(TreeNode* root, int m, int count) { int i; shared_ptrlistSearchNode head1 make_sharedlistSearchNode(1, SearchNode()); for (i 0; i K; i) { if (root-Link[i] ! NULL) break; } if (root-data m) { head1-insert(head1-end(), SearchNode(1, root, nullptr)); //只有根节点需要加入SearchNode链表中 count; } if (i K) return head1; else { int d, k; TreeNode* ptr; int interval; ptr root; d -1; k 1; vectorPath stack; while (1) { if ((interval Search(ptr, d)) -1) { if (ptr root) break; else { if (d ! -1) { stack.pop_back(); } k--; ptr stack.back().current; d stack.back().direction; } } else { if (d -1) { stack.push_back(Path(ptr, interval)); } else { stack.back().direction interval; } ptr ptr-Link[interval]; d -1; k; if (ptr-data m) //找到一个m项 { count; listSearchNode::iterator before head1-begin(); listSearchNode::iterator after before; after; while (after ! head1-end()) { if (before-plies after-plies) //将SearchNode1结点插入至SearchNode1链表中确保插入后链表中相同层数的结点所属的块按层数大小以从小到大顺序从左至右排列且每个块中各节点排列顺序与他们在树的同一层中出现的顺序一致 { if (k after-plies) { before; head1-insert(before, SearchNode(k, ptr, stack.back().current)); break; } } after; before; } if (after head1-end()) { head1-insert(head1-end(), SearchNode(k, ptr, stack.back().current)); } } } } return head1; } } void Order(int i, int m, int number, listSearchNode::iterator before, TreeNode* root, int plies, listSearchNode::iterator Location) { if (i K) { number; cout 第 number 个 m 结点位于第 1 层上从左自由数起第 1 个位置 endl; } else { if (plies 1) //要处理链表块只有一个结点,层数1,即为根节点 { number; cout 第 number 个 m 结点位于第 1 层上从左自由数起第 1 个位置 endl; Location; } else { int d, k, count; TreeNode* ptr; int interval; ptr root; count 0; d -1; k 1; vectorPath stack; while (1) { if ((interval Search(ptr, d)) -1) { if (ptr root) break; else { if (d ! -1) { stack.pop_back(); } --k; ptr stack.back().current; d stack.back().direction; } } else { if (d -1) { stack.push_back(Path(ptr, interval)); } else { stack.back().direction Search(ptr, d); } ptr ptr-Link[interval]; d -1; k; if (k plies) //抵达第plies层 { count; if (ptr-data m) //在plies层找到m项 { number; cout 第 number 个 m 结点位于第 plies 层上从左自由数起第 count 个位置 endl; //输出找到的m项位置 if (Location before) //到达链表块尾部链表块中结点位置输出完毕 { Location; //*Location指向下一链表块第一个结点 return; } Location; //递进至本链表块下一结点 } ptr stack.back().current; d stack.back().direction; k--; } } } } } } int Search(TreeNode* ptr, int d) { for (d; d K; d) { if (Enable(ptr, d)) return d; } return -1; } bool Enable(TreeNode* ptr, int m) { if (ptr-Link[m] ! nullptr) return true; else return false; }问题:求K叉树结点总数并输出所有结点值解答(C)#include iostream #include vector #include list #include memory #define K 4 using namespace std; struct TreeNode { int data; struct TreeNode* Link[K]; }; struct Path { TreeNode* current; int direction; Path(TreeNode* c, int d) :current(c), direction(d) {} }; struct SearchNode { int value; int plies; TreeNode* goal; TreeNode* before; SearchNode(int p, int v, TreeNode* g, TreeNode* b) :plies(p), value(v), goal(g), before(b) {} SearchNode() :plies(0) {} }; shared_ptrlistSearchNode ComputeLeaf(TreeNode* root, int count); //函数用于求节点总数返回SearchNode1链表头结点 int Search(TreeNode* ptr, int d); bool Enable(TreeNode* ptr, int m); int main() { int i, count; //count记录结点总数 TreeNode* temp1, * temp2; TreeNode* root new TreeNode(); root-data 0; root-Link[0] nullptr; for (i 1; i 3; i) { root-Link[i] new TreeNode(); root-Link[i]-data i; } for (i 1; i 4; i) root-Link[1]-Link[i - 1] nullptr; temp1 root-Link[2]; for (i 1; i 4; i) { temp1-Link[i - 1] new TreeNode(); temp1-Link[i - 1]-data i 3; } temp2 temp1-Link[0]; temp2-Link[1] new TreeNode(); temp2-Link[1]-data 10; for (i 1; i 4; i) temp2-Link[1]-Link[i - 1] nullptr; temp2-Link[3] new TreeNode(); temp2-Link[3]-data 11; for (i 1; i 4; i) temp2-Link[3]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[2] nullptr; temp2 temp1-Link[2]; temp2-Link[2] new TreeNode(); temp2-Link[2]-data 12; for (i 1; i 4; i) temp2-Link[2]-Link[i - 1] nullptr; temp2-Link[0] temp2-Link[1] temp2-Link[3] nullptr; temp2 temp1-Link[1]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp2 temp1-Link[3]; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1 root-Link[3]; temp1-Link[1] new TreeNode(); temp2 temp1-Link[1]; temp2-data 8; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[3] new TreeNode(); temp2 temp1-Link[3]; temp2-data 9; for (i 1; i 4; i) temp2-Link[i - 1] nullptr; temp1-Link[0] temp1-Link[2] nullptr; shared_ptrlistSearchNode head ComputeLeaf(root, count); listSearchNode::iterator before head-begin(); listSearchNode::iterator after before; after; i 0; while (after ! head-end()) { if (before-plies after-plies) //按层数有小到大每层从左至右顺序输出所有结点值 { if (before ! head-begin()) { cout endl; } i; cout K叉树的第 i 行从左至右为:; } cout after-value; after; before; } cout endl; cout 多叉树中共有 count 个节点 endl; //输出结点总数 return 0; } shared_ptrlistSearchNode ComputeLeaf(TreeNode* root, int count) { int i; shared_ptrlistSearchNode head1 make_sharedlistSearchNode(1, SearchNode()); for (i 0; i K; i) { if (root-Link[i] ! NULL) break; } head1-insert(head1-end(), SearchNode(1, root-data, root, nullptr)); if (i K) { count 1; //节点总数为1 return head1; } else { int d, k; TreeNode* ptr; int interval; ptr root; d -1; count 1; k 1; vectorPath stack; while (1) { if ((interval Search(ptr, d)) -1) { if (ptr root) break; else { if (d ! -1) { stack.pop_back(); } --k; ptr stack.back().current; d stack.back().direction; } } else { if (d -1) { stack.push_back(Path(ptr, interval)); } else { stack.back().direction interval; } ptr ptr-Link[interval]; d -1; k; count; //计数变量加一 listSearchNode::iterator before head1-begin(); listSearchNode::iterator after before; after; while (after ! head1-end()) { if (before-plies after-plies) { if (k after-plies) { before; head1-insert(before, SearchNode(k, ptr-data, ptr, stack.back().current)); //将SearchNode1结点插入至SearchNode1链表中确保插入后链表中相同层数的结点所属的块按层数大小以从小到大顺序从左至右排列且每个块中各节点排列顺序与他们在树的同一层中出现的顺序一致 break; } } after; before; } if (after head1-end()) { head1-insert(head1-end(), SearchNode(k, ptr-data, ptr, stack.back().current)); } } } return head1; } } int Search(TreeNode* ptr, int d) { for (d; d K; d) { if (Enable(ptr, d)) return d; } return -1; } bool Enable(TreeNode* ptr, int m) { if (ptr-Link[m] ! nullptr) return true; else return false; }