考研笔记整理，本篇作为树与二叉树的基本概念习题，供小伙伴们参考~🥝🥝
之前的博文链接在此：数据结构05：树与二叉树[C++]-CSDN博客~🥝🥝
- 第1版：王道书的课后习题~🧩🧩
编辑：梅头脑🌸
参考用书：王道考研《2025年 数据结构考研复习指导》
目录
🧵01 三叉树最小高度
🧩题目
含有n个结点的三叉树的最小高度是多少？
📇解题思路
高度为1的三叉树有1个结点，等比数列求和公式为：1 = 1x(3^1-1)/(3-1) = 1
高度为2的三叉树有4个结点，等比数列求和公式为：1+3 = 1x(3^2-1)/(3-1) = 4
高度为3的三叉树有13个结点，等比数列求和公式为：1+3+9 = 1x(3^3-1)/(3-1) = 13
...
高度为n的三叉树有1+3+9+...+3^(n-1)个结点，等比数列求和公式为：n = 1+3+9+...+3^(h-1) = 1x(3^h-1)/(3-1) = (3^h-1)/2
移项：3^h = 2*n + 1，取对数：h = log3(2*n + 1)，向上取整，即为最小高度。
🧵02 节点与度（一）
🧩题目
已知一棵度为4的树中，度为0,1,2,3 的结点数分别为14,4,3,2个，求该树的节点总数n和度为4的结点个数，并给出推导过程。
📇解题思路
节点数 = 分支数 + 1，因为没有指向根节点的分支；
节点数 = 14 + 4 + 3 + 2 = 23；
度为1、2、3的分支数 = 14*0 + 4*1 + 3*2 + 2*3 = 4 + 6 + 6 = 16；
度为4的分支数 = 总分支数 - 度为1、2、3的分支数 = 23 - 16 = 7；
度为4的结点数 = (度为4的分支数 + 1) / 4 = (7 + 1) / 4 = 2；
节点总数 = 度为1、2、3的结点数 + 度为4的结点数 = 14 + 4 + 3 + 2 + 2 = 25；
🧵03 节点与度（二）
🧩题目
已知一棵度为m的树中，有n1个度为1的节点，有n2个度为2的节点……有nm个度为m的节点，问该树有多少叶节点？
📇解题思路
节点数 = 分支数 + 1，因为没有指向根节点的分支；
节点数 = n0 + n1 + n2 + n3 + …… + nm；
分支数 = n0*0 + n1*1 + n2*2 + n3*3 + …… + nm*m；
代入等式，n0 + n1 + n2 + n3 + …… + nm = n0*0 + n1*1 + n2*2 + n3*3 + …… + nm*m + 1；
n0节点总数 = n1*(1-0) + n2*(2-1) + n3*(3-1) + …… + nm*(m-1) + 1 ；
🧵04 二叉树节点与度
🧩题目
在一棵完全二叉树中, 含有n0个叶结点, 当度为1的结点数为1时, 该树的高度是多少 ? 当度为1的结点数为0时，该树的高度是多少 ?
📇解题思路
二叉树的节点数n = n0 + n1 + n2，其中n0为叶子节点数，n1为度为1的节点数，n2为度为2的节点数；
二叉树的节点数n = 分支数 + 1 = n1 + 2 * n2 + 1；
联立以上两个等式，得到n0 = n2 + 1；
又因为完全二叉树的高度h = log2(n + 1)，向上取整；
当度为1的结点数为1时，n = n0 + 1 + n0 - 1 = 2 * n0，所以 h = log2[2 * n0 + 1]，向上取整；
当度为1的结点数为0时，n = n0 + n0 - 1 = 2 * n0 - 1，所以 h = log2[2 * n0]，向上取整；
🧵05 满二叉树节点数
🧩题目
一棵有n个结点的满二叉树有多少个分支结点和多少个叶结点?该满二叉树的高度是多少?
📇解题思路
二叉树的节点数n = n0 + n1 + n2，其中n0为叶子节点数，n1为度为1的节点数，n2为度为2的节点数；
满二叉树不存在n1。又因为二叉树满足 n0 = n2 + 1;
所以，满二叉树的节点数n = 2 * n0 - 1 = 2 * n2 + 1; 节点 n0 = (n + 1) / 2， 节点 n2 = (n - 1) / 2;
满二叉树的节点n = 2^h - 1，高度h = log2(n + 1)。
🧵06 完全二叉树节点数
🧩题目
已知完全二叉树的第9层有 240个结点，则整个完全二叉树有多少个结点 ? 有多少个叶结点 ?
📇解题思路
完全二叉树的第n层最多有 2^(n-1) 个结点，第9层最多有 2^8 = 256 个结点；因此，考虑到完全二叉树的性质，240个节点均为叶结点；
但叶结点并非仅有第9层才有，第8层也有叶结点，第8层最多有 2^7 = 128 个结点，被第9层用掉 240 / 2 = 120个叶结点，还剩 8 个叶结点；整棵树共计248个叶结点，没有 n1 节点；
完全二叉树的结点数 n = n0 + n1 + n2 = n0 + (n0 - 1) = 2 * (240 + 8) - 1 = 495 个结点；
🧵07 满二叉树节点与编号
🧩题目
一棵高度为h的满 m又树有如下性质 : 根结点所在层次为第1层，第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树，若按层次自顶向下，同一层自左向右
顺序从1开始对全部结点进行编号，试问 :
1)各层的结点个数是多少 ?
2)编号为i的结点的双亲结点(若存在)的编号是多少 ?
3)编号为i的结点的第k个孩子结点(若存在)的编号是多少 ?
4)编号为i的结点有右兄弟的条件是什么 ? 其右兄弟结点的编号是多少 ?
📇解题思路
1）等比数列，第i层的结点个数是 m^(i-1)；
3）在三叉树中，节点2、3、4的双亲节点为1，节点5、6、7的双亲节点为2，即孩子节点 = (双亲节点i - 1) * 3 + 1 + k；同理，在m叉树中，第2、3、...m + 1的双亲节点为1，节点m + 2、m + 3、...2m + 1的双亲节点为2，即孩子节点 = (双亲节点i - 1) * m + 1 + k；
2）根据3)题，第1个孩子节点 = (双亲节点i - 1) * m + 2；因此，编号为i的结点的双亲结点的编号是 ((i - 2) / m) + 1，向下取整；
4）根据3)题，最后1个孩子节点i = (双亲节点 - 1) * m + 1；因此，编号为i的结点有右兄弟的条件是 (i - 1) % m != 0，其右兄弟结点的编号是 i + 1；
🧵08 顺序存储二叉树的公共祖先
🧩题目
已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近的公共祖先结点的值。
📇友情配图
我们以下的代码以这棵树为例，为了方便求祖先，这里将数组编号与内容对应一致~
以下解法的核心思路都是建立在：
- 父节点序号 = （子节点序号 - 1）/ 2 的基础上，注意计算机运算会自动向下取整；
- 假设树中节点没有负值，返回-1表示该节点不存在。
📇解题思路1：使用2个栈完成遍历
使用两个栈，分别存储节点 1 和 2 的祖先。
然后从两个栈的起点开始同时遍历，如果节点相同，表明该节点是二者公共祖先；否则，该节点不满足题目要求，停止循环。
这个解题代码的空间复杂度和时间复杂度都很高，完全不推荐！
⌨️解题代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树的顺序存储结构
typedef struct {
vector<int> tree;
} SqBiTree;
int find_common_ancestor(SqBiTree T, int i, int j) {
if (i < 0 || i >= T.tree.size() || j == -1 || j >= T.tree.size()) {
return -1;
}
// 根据节点下标，确认祖先节点的位置，并将祖先全部入栈
int index1 = i;
int index2 = j;
stack<int> ancestor1;
stack<int> ancestor2;
do {
ancestor1.push(T.tree[index1]);
if (index1 > 1) { index1 = (index1 - 1) / 2; }
else { index1 = index1 - 1; }
} while (index1 >= 0);
do {
ancestor2.push(T.tree[index2]);
if (index2 > 1) index2 = (index2 - 1) / 2;
else { index2 = index2 - 1; }
} while (index2 >= 0);
// 从栈顶开始遍历，如果节点相同，继续往下遍历；如果节点不同，退出循环
int common_ancestor = -1;
while (!ancestor1.empty() && !ancestor2.empty()) {
if (ancestor1.top() != ancestor2.top()) { break; }
common_ancestor = ancestor1.top();
ancestor1.pop();
ancestor2.pop();
}
return common_ancestor;
}
int main() {
SqBiTree T = { {0, 1, 2, 3, 4, 5, 6, 7, 8} };
int node1 = -1, node2 = -1, result = -1;
node1 = 7, node2 = 8;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 5, node2 = 2;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 3, node2 = 6;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 9, node2 = 3;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
return 0;
}⌨️跑题代码
以下这个代码跑题了，传入的参数是节点值，而非节点编号，😣——
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树的顺序存储结构
typedef struct {
vector<int> tree;
} SqBiTree;
int find_common_ancestor(SqBiTree T, int node1, int node2) {
// 从数组中找到 node1, node2的下标
int locate1 = -1;
int locate2 = -1;
for(int i = 0; i < T.tree.size(); i++){
if (T.tree[i] == node1) { locate1 = i; }
if (T.tree[i] == node2) { locate2 = i; }
}
if (locate1 == -1 || locate2 == -1) { return -1; }
// 根据节点下标，确认祖先节点的位置，并将祖先全部入栈
int index1 = locate1;
int index2 = locate2;
stack<int> ancestor1;
stack<int> ancestor2;
do {
ancestor1.push(T.tree[index1]);
if (index1 > 1) { index1 = (index1 - 1) / 2; }
else {index1 = index1 - 1;}
} while (index1 >= 0);
do {
ancestor2.push(T.tree[index2]);
if (index2 > 1) index2 = (index2 - 1) / 2;
else { index2 = index2 - 1; }
} while (index2 >= 0);
// 从栈顶开始遍历，如果节点相同，继续往下遍历；如果节点不同，退出循环
int common_ancestor = -1;
while (!ancestor1.empty() && !ancestor2.empty()) {
if (ancestor1.top() != ancestor2.top()) { break; }
common_ancestor = ancestor1.top();
ancestor1.pop();
ancestor2.pop();
}
return common_ancestor;
}
int main() {
SqBiTree T = { {0, 1, 2, 3, 4, 5, 6, 7, 8} };
int node1 = -1, node2 = -1, result = -1;
node1 = 7, node2 = 8;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 5, node2 = 2;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 3, node2 = 6;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 9, node2 = 3;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
return 0;
}
📇解题思路2：使用2个循环完成遍历
从2个节点的位置开始向祖先遍历，每次循环时，较远的节点找到其祖先，然后判断2个节点的祖先此时是否相等~
相比上一个代码，代码的数量、遍历的次数和使用的空间都减少了很多~
⌨️解题代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树的顺序存储结构
typedef struct {
vector<int> tree;
} SqBiTree;
int find_common_ancestor(SqBiTree T, int i, int j) {
if (i < 0 || i >= T.tree.size() || j == -1 || j >= T.tree.size()) {
return -1;
}
// 根据节点下标，确认祖先节点的位置
while (i != j) {
if (i > j)
i = (i - 1) / 2;
else
j = (j - 1) / 2;
}
return T.tree[i];
}
int main() {
SqBiTree T = { {0, 1, 2, 3, 4, 5, 6, 7, 8} };
int node1 = -1, node2 = -1, result = -1;
node1 = 7, node2 = 8;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 5, node2 = 2;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 3, node2 = 6;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 9, node2 = 3;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
return 0;
}⌨️跑题代码
和上面的理由一样，以下这个代码跑题了，传入的参数是节点值，而非节点编号，😣——
#include <iostream>
#include <vector>
using namespace std;
// 二叉树的顺序存储结构
typedef struct {
vector<int> tree;
} SqBiTree;
int find_common_ancestor(SqBiTree T, int node1, int node2) {
// 从数组中找到 node1, node2的下标
int locate1 = -1;
int locate2 = -1;
for(int i = 0; i < T.tree.size(); i++){
if (T.tree[i] == node1) { locate1 = i; }
if (T.tree[i] == node2) { locate2 = i; }
}
if (locate1 == -1 || locate2 == -1) { return -1; }
// 根据节点下标，确认祖先节点的位置
while (locate1 != locate2) {
if (locate1 > locate2)
locate1 = (locate1 - 1) / 2;
else
locate2 = (locate2 - 1) / 2;
}
return T.tree[locate1];
}
int main() {
SqBiTree T = { {0, 1, 2, 3, 4, 5, 6, 7, 8} };
int node1 = -1, node2 = -1, result = -1;
node1 = 7, node2 = 8;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 5, node2 = 2;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 3, node2 = 6;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
node1 = 9, node2 = 3;
result = find_common_ancestor(T, node1, node2);
cout << "节点 " << node1 << " 与 " << node2 << " 的公共祖先是节点 " << result << endl;
return 0;
}
🧵09 k二叉树节点
🧩题目
【2016统考真题】若一棵非空k(k >= 2)又树T中的每个非叶结点都有k个孩子，则称I为正则k叉树。请回答下列问题并给出推导过程。
1)若T有m个非叶结点，则T中的叶结点有多少个 ?
2)若T的高度为h(单结点的树h = 1)，则T的结点数最多为多少个 ? 最少为多少个 ?
📇解题思路
1) 最少是除了根节点层与底层外，每层有1个节点有k个孩子，其它 k-1 个节点是叶结点：n = m + n0 = 1 + k * m， n0 = (k - 1)*m + 1;
2) 最多是满二叉树：1 + k + k^2 + ... = (k^(h - 1) - 1)(k - 1); 最少是1 + k + k + ... = k * (h - 1) + 1;
🔚结语
博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶🌫️
我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟
同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客
同博主的博文：🌸随笔03 笔记整理-CSDN博客
