2020考研-王道数据结构-树和二叉树-树和森林 朱雀 2022-01-20 23:27 217阅读 0赞 # 头文件定义 # #include <iostream> #include <string> #include <vector> #include <algorithm> #include <queue> # 数据结构定义 # typedef char ElemType; typedef struct CSNode // 孩子兄弟表示法的树 { ElemType data; struct CSNode *first, *next; }CSNode, *CSTree; # 第五题 # ##### 题目描述 ##### 编程求以孩子兄弟表示法存储的森林的叶子结点数。 ##### 题目分析 ##### 无左孩子的结点就是叶子。 ##### 代码 ##### // 求以孩子兄弟表示法的树的叶子节点的个数 int getLeafNodeCounter(CSTree tree) { static int res = 0; if (!tree) return 0; if (!tree->first) res++; getLeafNodeCounter(tree->first); getLeafNodeCounter(tree->next); return res; } # 第六题 # ##### 题目描述 ##### 以孩子兄弟链表为存储结构,设计递归算法求树的深度。 ##### 题目分析 ##### 对于孩子兄弟表示法来说,二叉树的递归求深度的时候: 1. 向左子树走,左子树是当前结点的子节点,所以深度+1. 2. 向右子树走,右子树是当前结点的兄弟结点,深度不变。 3. 总深度 = max(左子树的深度+1,右子树的深度) ##### 代码 ##### // 求以孩子兄弟表示法的树的深度 int getHeight(CSTree tree) { if (!tree) return 0; return max(getHeight(tree->first) + 1, getHeight(tree->next)); } # 第七题 # ##### 题目描述 ##### 已知一棵树的层次序列以及每个结点的度,编写算法构造此树的孩子-兄弟链表。 ##### 题目分析 ##### 我说一下下面代码的思路: 从根节点开始看,根节点有3个度,意思就是能收留3个结点。则向后收留三个结点,按照逻辑顺序连接即可。 然后把这三个结点入队。 根节点已经满了,所以出队。依次进行,知道队列为空,整棵树就建好了。 建议大家先在纸上模拟一下。给大家一棵树。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70][] ##### 代码 ##### // 一直一棵树的层序遍历序列和每个结点的度,求这棵树的孩子兄弟表示法的树 CSTree getCSTree(string level, vector<int> degree) { if (!level.size()) return NULL; CSTree tree = new CSNode(); queue<CSTree> que; que.push(tree); int i = 0, j = 0; tree->data = level[i++]; tree->first = tree->next = NULL; while (que.size()) { CSTree node = que.front(), p = NULL; que.pop(); if (!degree[j]){ j++; continue; } for (int k = 0; k < degree[j]; k++) { CSTree cst = new CSNode(); cst->data = level[i++]; cst->first = cst->next = NULL; if (!k) { node->first = cst; p = cst; que.push(p); } else { p->next = cst; p = cst; que.push(p); } } j++; } return tree; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]: /images/20220121/fb5b8615868649a59b5e6697f2375db3.png
还没有评论,来说两句吧...