利用Java二叉树写一个族谱代码,要求:可以使用插入、删除功能
时间: 2024-11-09 11:28:44 浏览: 15
在Java中,我们可以创建一个二叉树结构来表示家族成员的族谱。通常会使用`TreeNode`作为节点类,包含姓名(`name`)属性和两个子节点(`left` 和 `right`)。下面是一个简单的示例,包含了插入和删除功能:
```java
public class FamilyTree {
static class TreeNode {
String name;
TreeNode left;
TreeNode right;
TreeNode(String name) {
this.name = name;
}
}
private TreeNode root;
// 插入新成员
public void insert(String name) {
if (root == null) {
root = new TreeNode(name);
} else {
insertHelper(root, name);
}
}
private void insertHelper(TreeNode node, String name) {
if (name.compareTo(node.name) < 0) {
if (node.left == null) {
node.left = new TreeNode(name);
} else {
insertHelper(node.left, name);
}
} else if (name.compareTo(node.name) > 0) {
if (node.right == null) {
node.right = new TreeNode(name);
} else {
insertHelper(node.right, name);
}
}
}
// 删除成员(这里仅给出简单版本,实际删除需要考虑情况复杂度)
public boolean delete(String name) {
return deleteHelper(root, name);
}
private boolean deleteHelper(TreeNode node, String name) {
if (node == null) {
return false;
}
if (name.equals(node.name)) {
// 如果找到了要删除的节点,根据不同情况处理
if (node.left == null && node.right == null) { // 叶子节点
node = null;
} else if (node.left == null) { // 只有一个子节点
node = node.right; // 将非叶子节点移动到原位置
} else if (node.right == null) { // 只有一个子节点
node = node.left;
} else { // 有两个子节点
TreeNode minNode = findMinNode(node.right); // 找到右子树最小节点
node.name = minNode.name; // 更新值
node.right = deleteHelper(node.right, minNode.name); // 递归删除找到的最小节点
}
return true;
} else if (name.compareTo(node.name) < 0) {
node.left = deleteHelper(node.left, name);
} else {
node.right = deleteHelper(node.right, name);
}
return node != null;
}
// 辅助方法,查找最小节点
private TreeNode findMinNode(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// 其他如查找、遍历等操作可按照类似思路实现
}
阅读全文