1. 项目概述:Treebook作业的设计初衷
这个作业是斯坦福CS106L课程中一个经典的树形数据结构实践项目。Treebook这个名字很有意思,它把"Tree"和"Facebook"结合起来,暗示我们要用树结构来实现一个简化版的社交网络系统。作为课程第五个作业,它处在学生已经掌握基础数据结构后,开始接触更复杂系统设计的阶段。
我当年做这个作业时,最大的感受是它完美展现了树结构在真实场景中的应用价值。不像教科书上那些抽象的例子,Treebook要求我们处理好友关系、信息传播路径这些具体问题,让数据结构的理论学习突然变得生动起来。作业通常会提供基础框架代码,我们需要实现核心的树操作算法和特定功能接口。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 核心数据结构解析
2.1 多叉树 vs 二叉树的选择
作业一般会明确要求使用多叉树结构,因为社交网络中的好友关系天然适合这种形式。每个用户节点可以有多个子节点(好友),这与二叉树限制两个子节点的情况不同。在C++中,我们通常会这样定义节点结构:
cpp复制struct UserNode {
std::string name;
std::vector<UserNode*> friends; // 使用vector存储可变数量的好友
// 其他元数据如注册时间、个人简介等
};
选择vector而不是原生数组来存储子节点,是因为好友数量不确定且可能变化。这种设计也体现了C++标准库容器在实际工程中的优势。
2.2 内存管理要点
由于树结构涉及动态内存分配,有几个易错点需要特别注意:
- 在树的析构函数中要实现递归删除所有节点,防止内存泄漏
- 拷贝构造函数和赋值运算符需要实现深拷贝,避免多个树对象共享节点指针
- 使用智能指针(如unique_ptr)可以简化内存管理,但作业可能限制使用原始指针来训练基本功
3. 关键算法实现细节
3.1 好友关系建立算法
添加好友关系本质上是树节点的插入操作。一个健壮的实现需要考虑:
cpp复制void addFriend(UserNode* parent, const std::string& newFriendName) {
// 1. 检查是否已经是好友(防止重复)
for (auto* friendNode : parent->friends) {
if (friendNode->name == newFriendName) {
throw std::runtime_error("Already friends!");
}
}
// 2. 创建新节点
UserNode* newNode = new UserNode{newFriendName};
// 3. 双向关联(视具体需求而定)
parent->friends.push_back(newNode);
newNode->friends.push_back(parent);
}
注意这里没有处理循环引用的情况,实际项目中需要更复杂的检测逻辑。
3.2 信息传播路径查找
这是作业的经典问题:给定两
