// 定义一个树形结构的函数
function Tree() {
const nodes = new Map();
// 添加节点
this.add = function(parent, id) {
nodes.set(id, { parent, children: new Set() });
};
// 移除节点
this.remove = function(id) {
nodes.delete(id);
// 还需要从其父节点的children中移除
};
// 获取所有子孙节点
this.getSubtree = function(id) {
const subtree = new Set([id]);
const dfs = (nodeId) => {
nodes.get(nodeId).children.forEach(child => {
subtree.add(child);
dfs(child);
});
};
nodes.get(id).children.forEach(dfs);
return subtree;
};
// 获取所有祖先节点
this.getAncestors = function(id) {
const ancestors = new Set();
let node = nodes.get(id);
while (node.parent) {
ancestors.add(node.parent);
node = nodes.get(node.parent);
}
return ancestors;
};
// 检查是否为叶子节点
this.isLeaf = function(id) {
return nodes.get(id).children.size === 0;
};
// 检查是否为根节点
this.isRoot = function(id) {
return !nodes.get(id).parent;
};
// 获取树的深度
this.getDepth = function() {
let depth = 0;
// 需要遍历所有节点并更新depth
return depth;
};
}
// 使用示例
const tree = new Tree();
tree.add(null, 'A');
tree.add('A', 'B');
tree.add('A', 'C');
tree.add('B', 'D');
tree.add('B', 'E');
tree.add('C', 'F');
console.log(tree.getSubtree('A')); // 输出节点A的所有子孙节点
console.log(tree.getAncestors('D')); // 输出节点D的所有祖先节点
console.log(tree.isLeaf('B')); // 输出节点B是否为叶子节点
console.log(tree.isRoot('D')); // 输出节点D是否为根节点
// 注意: 需要实现getDepth方法来获取树的深度这个代码示例展示了如何实现一个简单的树形数据结构，并提供了几个常用的递归方法，如获取子孙节点、祖先节点，检查叶子和根节点，以及计算树的深度。需要注意的是，示例中的getDepth方法尚未实现，因为它需要遍历所有节点并更新最大深度。