删除族树中的节点(Deleting a node in a family tree)

删除族树中的节点(Deleting a node in a family tree)

我正在尝试计算删除族树中节点的最佳方法。 首先，稍微描述应用程序的工作原理。

我的应用程序做出以下假设：

任何节点只能有一个伙伴。 这意味着单个节点拥有的任何子节点，它也将是伙伴节点子节点。 因此，阶梯关系，离婚等不予补偿。 节点总是有两个父母 - 母亲和父亲不能单独添加。 如果用户不知道详细信息 - 节点属性设置为默认值。

此外，任何节点都可以添加父母，兄弟姐妹，孩子。 因此在法律上可以增加关系。

编辑：在研究了安德烈亚斯的回答之后，我逐渐意识到我的代码可能需要一些重新工作。 我正在尝试添加我的源代码，但它超出了charracters的限制......有什么建议吗？

这是FamilyTree类：

package familytree; import java.io.PrintStream; public class FamilyTree { private static final int DISPLAY_FAMILY_MEMBERS = 1; private static final int ADD_FAMILY_MEMBER = 2; private static final int REMOVE_FAMILY_MEMBER = 3; private static final int EDIT_FAMILY_MEMBER = 4; private static final int SAVE_FAMILY_TREE = 5; private static final int LOAD_FAMILY_TREE = 6; private static final int DISPLAY_ANCESTORS = 7; private static final int DISPLAY_DESCENDANTS = 8; private static final int QUIT = 9; private Input in; private Family family; private PrintStream out; public FamilyTree(Input in, PrintStream out) { this.in = in; this.out = out; family = new Family(); } public void start() { out.println("\nWelcome to the Family Tree Builder"); initialise(); while (true) { displayFamilyTreeMenu(); int command = getCommand(); if (quit(command)) { break; } executeOption(command); } } private int getCommand() { return getInteger("\nEnter command: "); } private int getInteger(String message) { while (true) { out.print(message); if (in.hasNextInt()) { int n = in.nextInt(); in.nextLine(); return n; } else { in.nextLine(); out.println("Your input was not understood. Please try again."); } } } //good private void displayFamilyTreeMenu() { out.println("\nFamily Tree Menu"); out.println(DISPLAY_FAMILY_MEMBERS + ". Display Family Members"); out.println(ADD_FAMILY_MEMBER + ". Add Family Member"); out.println(REMOVE_FAMILY_MEMBER + ". Remove Family Member"); out.println(EDIT_FAMILY_MEMBER + ". Edit Family Member"); out.println(SAVE_FAMILY_TREE + ". Save Family Tree"); out.println(LOAD_FAMILY_TREE + ". Load Family Tree"); out.println(DISPLAY_ANCESTORS + ". Display Ancestors"); out.println(DISPLAY_DESCENDANTS + ". Display Descendants"); out.println(QUIT + ". Quit"); } //good private boolean quit(int opt) { return (opt == QUIT) ? true : false; } //good private void executeOption(int choice) { switch (choice) { case DISPLAY_FAMILY_MEMBERS: displayFamilyMembers(); break; case ADD_FAMILY_MEMBER: addFamilyMember(); break; case REMOVE_FAMILY_MEMBER: removeMember(); break; case EDIT_FAMILY_MEMBER: editMember(); break; case SAVE_FAMILY_TREE: saveFamilyTree(); break; case LOAD_FAMILY_TREE: loadFamilyTree(); break; case DISPLAY_ANCESTORS: displayAncestors(); break; case DISPLAY_DESCENDANTS: displayDescendants(); break; default: out.println("Not a valid option! Try again."); break; } } private void removeMember() { displayFamilyMembers(); int choice = selectMember(); if (choice >= 0) { FamilyMember f = family.getFamilyMember(choice); if (f.getIndex() == 0) { out.println("Cannot delete yourself!"); return; } deleteMember(f); } } private void deleteMember(FamilyMember f) { //remove from tree family.removeMember(f); //remove all links to this person if (f.hasParents()) { f.getMother().removeChild(f); f.getFather().removeChild(f); } if(f.getPartner()!=null){ f.getPartner().setPartner(null); f.setPartner(null); } if (f.hasChildren()) { for (FamilyMember member : f.getChildren()) { if (f == member.getMother()) { member.setMother(null); } if (f == member.getFather()) { member.setFather(null); } if (f == member.getPartner()) { member.setPartner(null); } } } } private void saveFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileOutput output = new FileOutput(fileName); family.save(output); output.close(); saveRelationships(); } private void saveRelationships() { FileOutput output = new FileOutput("Relationships.txt"); family.saveRelationships(output); output.close(); } private void loadFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileInput input = new FileInput(fileName); family.load(input); input.close(); loadRelationships(); } private void loadRelationships() { FileInput input = new FileInput("Relationships.txt"); family.loadRelationships(input); input.close(); } //for selecting family member for editing adding nodes etc private void displayFamilyMembers() { out.println("\nDisplay Family Members"); int count = 0; for (FamilyMember member : family.getFamilyMembers()) { out.println(); if (count + 1 < 10) { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } else { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } count++; } } private int selectRelative() { out.println("\nSelect Relative"); out.println("1. Add Parents"); out.println("2. Add Child"); out.println("3. Add Partner"); out.println("4. Add Sibling"); //out.print("\nEnter Choice: "); //int choice = in.nextInt(); int choice = getInteger("\nEnter Choice: "); if (choice > 0 && choice < 5) { return choice; } return (-1); } private void addFamilyMember() { if (family.getFamilyMembers().isEmpty()) { out.println("No Members To Add To"); return; } int memberIndex = selectMember(); if (memberIndex >= 0) { FamilyMember member = family.getFamilyMember(memberIndex); int relative = selectRelative(); if (relative > 0) { out.println("\nAdd Member"); //if choice is valid switch (relative) { case 1: //adding parents FamilyMember mum, dad; if (!member.hasParents()) { out.println("Enter Mothers Details"); mum = addMember(relative, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(relative, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has parents."); } break; case 2: //adding child if (member.getPartner() == null) { FamilyMember partner; if (member.getGender().equals("Male")) { out.println("Enter Mothers Details"); partner = addMember(1, "Female"); } else { out.println("Enter Fathers Details"); partner = addMember(1, "Male"); } //create partner member.linkPartner(partner); partner.setGeneration(member.getGeneration()); out.println(); } out.println("Enter Childs Details"); FamilyMember child = addMember(relative, ""); child.linkParent(member); child.linkParent(member.getPartner()); child.setGeneration(member.getGeneration() + 1); sortGenerations(); break; case 3: //adding partner if (member.getPartner() == null) { out.println("Enter Partners Details"); FamilyMember partner = addMember(relative, ""); member.linkPartner(partner); partner.setGeneration(member.getGeneration()); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has a partner."); } break; case 4: //adding sibling if (member.getFather() == null) { out.println("Enter Mothers Details"); mum = addMember(1, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(1, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); out.println("\nEnter Siblings Details"); } else { out.println("Enter Siblings Details"); } FamilyMember sibling = addMember(relative, ""); //create mum and dad mum = member.getMother(); dad = member.getFather(); sibling.linkParent(mum); sibling.linkParent(dad); sibling.setGeneration(member.getGeneration()); break; } } else { out.println("Invalid Option!"); } } else { out.println("Invalid Option!"); } } private int selectMember() { displayFamilyMembers(); //out.print("\nSelect Member: "); //int choice = in.nextInt(); int choice = getInteger("\nSelect Member: "); if (choice > 0 && choice <= family.getFamilyMembers().size()) { return (choice - 1); } return -1; } private void editMember() { int choice = selectMember(); if (choice >= 0) { out.println("Select Detail To Edit: "); out.println("1. Name"); out.println("2. Gender"); out.println("3. Date of Birth"); //out.print("\nEnter Choice: "); //int opt = in.nextInt(); int opt = getInteger("\nEnter Choice: "); if (opt > 0 && opt < 4) { switch (opt) { case 1: //name out.print("Enter New First Name: "); String fName = in.nextLine(); out.print("Enter New Last Name: "); String lName = in.nextLine(); family.changeName(fName, lName, choice); break; case 2: //Gender FamilyMember f = family.getFamilyMember(choice); String gender = f.getGender(); if (f.getChildren().isEmpty()) { gender = selectGender(); family.changeGender(gender, choice); } else { //swap genders //swap mother father relationships for kids swapGenders(f, choice); } break; case 3: String dob = enterDateOfBirth(); family.changeDOB(dob, choice); } } else { out.println("Invalid Choice!"); } } } private FamilyMember addMember(int option, String gender) { out.print("Enter First Name: "); String fName = formatString(in.nextLine().trim()); out.print("Enter Last Name: "); String lName = formatString(in.nextLine().trim()); //String gender; if (option != 1) { //if not adding parents gender = selectGender(); } String dob = enterDateOfBirth(); FamilyMember f = family.getFamilyMember(family.addMember(fName, lName, gender, dob)); f.setIndex(family.getFamilyMembers().size() - 1); return (f); } private String selectGender() { String gender = null; out.println("Select Gender"); out.println("1. Male"); out.println("2. Female"); //out.print("Enter Choice: "); //int gOpt = in.nextInt(); int gOpt = getInteger("Enter Choice: "); if (gOpt == 1) { gender = "Male"; } else if (gOpt == 2) { gender = "Female"; } else { out.println("Invalid Choice"); } return gender; } private void swapGenders(FamilyMember f, int choice) { String gender; out.println("\nNOTE: Editing A Parent Nodes Gender Will Swap Parents Genders\n" + "And Swap Mother/Father Relationships For All Children."); out.println("\nContinue:"); out.println("1. Yes"); out.println("2. No"); //out.print("\nEnter Choice: "); //int select = in.nextInt(); int select = getInteger("\nEnter Choice: "); if (select > 0 && select < 3) { switch (select) { case 1: //swap relationships gender = selectGender(); //if selected gender is different if (!gender.equals(f.getGender())) { //swap String g = f.getGender(); family.changeGender(gender, choice); family.changeGender(g, f.getPartner().getIndex()); if (g.equals("Male")) { for (FamilyMember m : f.getChildren()) { m.setMother(f); m.setFather(f.getPartner()); } } else { for (FamilyMember m : f.getChildren()) { m.setFather(f); m.setMother(f.getPartner()); } } } break; case 2: break; } } else { out.println("Invalid Choice"); } } private String formatString(String s) { String firstLetter = s.substring(0, 1); String remainingLetters = s.substring(1, s.length()); s = firstLetter.toUpperCase() + remainingLetters.toLowerCase(); return s; } private String enterDateOfBirth() { out.print("Enter Year Of Birth (0 - 2011): "); String y = in.nextLine(); out.print("Enter Month Of Birth (1-12): "); String m = in.nextLine(); if (m.trim().equals("")) { m = "0"; } if (Integer.parseInt(m) < 10) { m = "0" + m; } m += "-"; out.print("Enter Date of Birth (1-31): "); String d = in.nextLine(); if (d.trim().equals("")) { d = "0"; } if (Integer.parseInt(d) < 10) { d = "0" + d; } d += "-"; String dob = d + m + y; while (!DateValidator.isValid(dob)) { out.println("Invalid Date. Try Again:"); dob = enterDateOfBirth(); } return (dob); } private void displayAncestors() { out.print("\nDisplay Ancestors For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); FamilyMember ms = findRootNode(node, 0, 2, -1); FamilyMember fs = findRootNode(node, 1, 2, -1); out.println("\nPrint Ancestors"); out.println("\nMothers Side"); if(ms==null){ out.println("Member has no mother"); }else{ printDescendants(ms, node, ms.getGeneration()); } out.println("\nFathers Side"); if(fs==null){ out.println("Member has no father"); }else{ printDescendants(fs, node, fs.getGeneration()); } } else { out.println("Invalid Option!"); } } private void displayDescendants() { out.print("\nDisplay Descendants For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); out.println("\nPrint Descendants"); printDescendants(node, null, 0); } else { out.println("Invalid Option!"); } } private FamilyMember findRootNode(FamilyMember node, int parent, int numGenerations, int count) { FamilyMember root; count++; if (count < numGenerations) { if (parent == 0) { if(node.hasMother()){ node = node.getMother(); }else{ return node; } } else { if(node.hasFather()){ node = node.getFather(); }else{ return node; } } root = findRootNode(node, 1, numGenerations, count); return root; } return node; } private int findHighestLeafGeneration(FamilyMember node) { int gen = node.getGeneration(); for (int i = 0; i < node.getChildren().size(); i++) { int highestChild = findHighestLeafGeneration(node.getChild(i)); if (highestChild > gen) { gen = highestChild; } } return gen; } private void printDescendants(FamilyMember root, FamilyMember node, int gen) { out.print((root.getGeneration() + 1) + " " + root.getFullName()); out.print(" [" + root.getDob() + "] "); if (root.getPartner() != null) { out.print("+Partner: " + root.getPartner().getFullName() + " [" + root.getPartner().getDob() + "] "); } if (root == node) { out.print("*"); } out.println(); if (!root.getChildren().isEmpty() && root != node) { for (int i = 0; i < root.getChildren().size(); i++) { for (int j = 0; j < root.getChild(i).getGeneration() - gen; j++) { out.print(" "); } printDescendants(root.getChild(i), node, gen); } } else { return; } } //retrieve highest generation public int getRootGeneration() { int min = family.getFamilyMember(0).getGeneration(); for (int i = 0; i < family.getFamilyMembers().size(); i++) { min = Math.min(min, family.getFamilyMember(i).getGeneration()); } return Math.abs(min); } public void sortGenerations() { int amount = getRootGeneration(); for (FamilyMember member : family.getFamilyMembers()) { member.setGeneration(member.getGeneration() + amount); } } //test method - temporary private void initialise() { family.addMember("Bart", "Simpson", "Male", "18-03-1985"); family.getFamilyMember(0).setIndex(0); family.addMember("Homer", "Simpson", "Male", "24-09-1957"); family.getFamilyMember(1).setIndex(1); family.addMember("Marge", "Simpson", "Female", "20-07-1960"); family.getFamilyMember(2).setIndex(2); family.addMember("Lisa", "Simpson", "Female", "28-01-1991"); family.getFamilyMember(3).setIndex(3); family.addMember("Abe", "Simpson", "Male", "10-03-1920"); family.getFamilyMember(4).setIndex(4); family.addMember("Mona", "Simpson", "Female", "18-09-1921"); family.getFamilyMember(5).setIndex(5); //set relationships family.getFamilyMember(0).setMother(family.getFamilyMember(2)); family.getFamilyMember(0).setFather(family.getFamilyMember(1)); family.getFamilyMember(3).setMother(family.getFamilyMember(2)); family.getFamilyMember(3).setFather(family.getFamilyMember(1)); family.getFamilyMember(1).addChild(family.getFamilyMember(3)); family.getFamilyMember(1).addChild(family.getFamilyMember(0)); family.getFamilyMember(2).addChild(family.getFamilyMember(3)); family.getFamilyMember(2).addChild(family.getFamilyMember(0)); family.getFamilyMember(1).setPartner(family.getFamilyMember(2)); family.getFamilyMember(2).setPartner(family.getFamilyMember(1)); family.getFamilyMember(4).setPartner(family.getFamilyMember(5)); family.getFamilyMember(5).setPartner(family.getFamilyMember(4)); family.getFamilyMember(1).setMother(family.getFamilyMember(5)); family.getFamilyMember(1).setFather(family.getFamilyMember(4)); family.getFamilyMember(4).addChild(family.getFamilyMember(1)); family.getFamilyMember(5).addChild(family.getFamilyMember(1)); family.getFamilyMember(0).setGeneration(2); family.getFamilyMember(1).setGeneration(1); family.getFamilyMember(2).setGeneration(1); family.getFamilyMember(3).setGeneration(2); family.getFamilyMember(4).setGeneration(0); family.getFamilyMember(5).setGeneration(0); } }

I'm trying to calclulate the best way to delete a node in a family tree. First, a little description of how the app works.

My app makes the following assumption:

Any node can only have one partner. That means that any child a single node has, it will also be the partner nodes child too. Therefore, step relations, divorces etc aren't compensated for. A node always has two parents - A mother and father cannot be added seperately. If the user doesn't know the details - the nodes attributes are set to a default value.

Also any node can add parents, siblings, children to itself. Therefore in law relationships can be added.

EDIT: After studying Andreas' answer, I have come to realise that my code may need some re-working. I'm trying to add my source but it exceeds the limit of charracters...Any advice?

Here is the FamilyTree Class:

package familytree; import java.io.PrintStream; public class FamilyTree { private static final int DISPLAY_FAMILY_MEMBERS = 1; private static final int ADD_FAMILY_MEMBER = 2; private static final int REMOVE_FAMILY_MEMBER = 3; private static final int EDIT_FAMILY_MEMBER = 4; private static final int SAVE_FAMILY_TREE = 5; private static final int LOAD_FAMILY_TREE = 6; private static final int DISPLAY_ANCESTORS = 7; private static final int DISPLAY_DESCENDANTS = 8; private static final int QUIT = 9; private Input in; private Family family; private PrintStream out; public FamilyTree(Input in, PrintStream out) { this.in = in; this.out = out; family = new Family(); } public void start() { out.println("\nWelcome to the Family Tree Builder"); initialise(); while (true) { displayFamilyTreeMenu(); int command = getCommand(); if (quit(command)) { break; } executeOption(command); } } private int getCommand() { return getInteger("\nEnter command: "); } private int getInteger(String message) { while (true) { out.print(message); if (in.hasNextInt()) { int n = in.nextInt(); in.nextLine(); return n; } else { in.nextLine(); out.println("Your input was not understood. Please try again."); } } } //good private void displayFamilyTreeMenu() { out.println("\nFamily Tree Menu"); out.println(DISPLAY_FAMILY_MEMBERS + ". Display Family Members"); out.println(ADD_FAMILY_MEMBER + ". Add Family Member"); out.println(REMOVE_FAMILY_MEMBER + ". Remove Family Member"); out.println(EDIT_FAMILY_MEMBER + ". Edit Family Member"); out.println(SAVE_FAMILY_TREE + ". Save Family Tree"); out.println(LOAD_FAMILY_TREE + ". Load Family Tree"); out.println(DISPLAY_ANCESTORS + ". Display Ancestors"); out.println(DISPLAY_DESCENDANTS + ". Display Descendants"); out.println(QUIT + ". Quit"); } //good private boolean quit(int opt) { return (opt == QUIT) ? true : false; } //good private void executeOption(int choice) { switch (choice) { case DISPLAY_FAMILY_MEMBERS: displayFamilyMembers(); break; case ADD_FAMILY_MEMBER: addFamilyMember(); break; case REMOVE_FAMILY_MEMBER: removeMember(); break; case EDIT_FAMILY_MEMBER: editMember(); break; case SAVE_FAMILY_TREE: saveFamilyTree(); break; case LOAD_FAMILY_TREE: loadFamilyTree(); break; case DISPLAY_ANCESTORS: displayAncestors(); break; case DISPLAY_DESCENDANTS: displayDescendants(); break; default: out.println("Not a valid option! Try again."); break; } } private void removeMember() { displayFamilyMembers(); int choice = selectMember(); if (choice >= 0) { FamilyMember f = family.getFamilyMember(choice); if (f.getIndex() == 0) { out.println("Cannot delete yourself!"); return; } deleteMember(f); } } private void deleteMember(FamilyMember f) { //remove from tree family.removeMember(f); //remove all links to this person if (f.hasParents()) { f.getMother().removeChild(f); f.getFather().removeChild(f); } if(f.getPartner()!=null){ f.getPartner().setPartner(null); f.setPartner(null); } if (f.hasChildren()) { for (FamilyMember member : f.getChildren()) { if (f == member.getMother()) { member.setMother(null); } if (f == member.getFather()) { member.setFather(null); } if (f == member.getPartner()) { member.setPartner(null); } } } } private void saveFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileOutput output = new FileOutput(fileName); family.save(output); output.close(); saveRelationships(); } private void saveRelationships() { FileOutput output = new FileOutput("Relationships.txt"); family.saveRelationships(output); output.close(); } private void loadFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileInput input = new FileInput(fileName); family.load(input); input.close(); loadRelationships(); } private void loadRelationships() { FileInput input = new FileInput("Relationships.txt"); family.loadRelationships(input); input.close(); } //for selecting family member for editing adding nodes etc private void displayFamilyMembers() { out.println("\nDisplay Family Members"); int count = 0; for (FamilyMember member : family.getFamilyMembers()) { out.println(); if (count + 1 < 10) { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } else { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } count++; } } private int selectRelative() { out.println("\nSelect Relative"); out.println("1. Add Parents"); out.println("2. Add Child"); out.println("3. Add Partner"); out.println("4. Add Sibling"); //out.print("\nEnter Choice: "); //int choice = in.nextInt(); int choice = getInteger("\nEnter Choice: "); if (choice > 0 && choice < 5) { return choice; } return (-1); } private void addFamilyMember() { if (family.getFamilyMembers().isEmpty()) { out.println("No Members To Add To"); return; } int memberIndex = selectMember(); if (memberIndex >= 0) { FamilyMember member = family.getFamilyMember(memberIndex); int relative = selectRelative(); if (relative > 0) { out.println("\nAdd Member"); //if choice is valid switch (relative) { case 1: //adding parents FamilyMember mum, dad; if (!member.hasParents()) { out.println("Enter Mothers Details"); mum = addMember(relative, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(relative, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has parents."); } break; case 2: //adding child if (member.getPartner() == null) { FamilyMember partner; if (member.getGender().equals("Male")) { out.println("Enter Mothers Details"); partner = addMember(1, "Female"); } else { out.println("Enter Fathers Details"); partner = addMember(1, "Male"); } //create partner member.linkPartner(partner); partner.setGeneration(member.getGeneration()); out.println(); } out.println("Enter Childs Details"); FamilyMember child = addMember(relative, ""); child.linkParent(member); child.linkParent(member.getPartner()); child.setGeneration(member.getGeneration() + 1); sortGenerations(); break; case 3: //adding partner if (member.getPartner() == null) { out.println("Enter Partners Details"); FamilyMember partner = addMember(relative, ""); member.linkPartner(partner); partner.setGeneration(member.getGeneration()); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has a partner."); } break; case 4: //adding sibling if (member.getFather() == null) { out.println("Enter Mothers Details"); mum = addMember(1, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(1, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); out.println("\nEnter Siblings Details"); } else { out.println("Enter Siblings Details"); } FamilyMember sibling = addMember(relative, ""); //create mum and dad mum = member.getMother(); dad = member.getFather(); sibling.linkParent(mum); sibling.linkParent(dad); sibling.setGeneration(member.getGeneration()); break; } } else { out.println("Invalid Option!"); } } else { out.println("Invalid Option!"); } } private int selectMember() { displayFamilyMembers(); //out.print("\nSelect Member: "); //int choice = in.nextInt(); int choice = getInteger("\nSelect Member: "); if (choice > 0 && choice <= family.getFamilyMembers().size()) { return (choice - 1); } return -1; } private void editMember() { int choice = selectMember(); if (choice >= 0) { out.println("Select Detail To Edit: "); out.println("1. Name"); out.println("2. Gender"); out.println("3. Date of Birth"); //out.print("\nEnter Choice: "); //int opt = in.nextInt(); int opt = getInteger("\nEnter Choice: "); if (opt > 0 && opt < 4) { switch (opt) { case 1: //name out.print("Enter New First Name: "); String fName = in.nextLine(); out.print("Enter New Last Name: "); String lName = in.nextLine(); family.changeName(fName, lName, choice); break; case 2: //Gender FamilyMember f = family.getFamilyMember(choice); String gender = f.getGender(); if (f.getChildren().isEmpty()) { gender = selectGender(); family.changeGender(gender, choice); } else { //swap genders //swap mother father relationships for kids swapGenders(f, choice); } break; case 3: String dob = enterDateOfBirth(); family.changeDOB(dob, choice); } } else { out.println("Invalid Choice!"); } } } private FamilyMember addMember(int option, String gender) { out.print("Enter First Name: "); String fName = formatString(in.nextLine().trim()); out.print("Enter Last Name: "); String lName = formatString(in.nextLine().trim()); //String gender; if (option != 1) { //if not adding parents gender = selectGender(); } String dob = enterDateOfBirth(); FamilyMember f = family.getFamilyMember(family.addMember(fName, lName, gender, dob)); f.setIndex(family.getFamilyMembers().size() - 1); return (f); } private String selectGender() { String gender = null; out.println("Select Gender"); out.println("1. Male"); out.println("2. Female"); //out.print("Enter Choice: "); //int gOpt = in.nextInt(); int gOpt = getInteger("Enter Choice: "); if (gOpt == 1) { gender = "Male"; } else if (gOpt == 2) { gender = "Female"; } else { out.println("Invalid Choice"); } return gender; } private void swapGenders(FamilyMember f, int choice) { String gender; out.println("\nNOTE: Editing A Parent Nodes Gender Will Swap Parents Genders\n" + "And Swap Mother/Father Relationships For All Children."); out.println("\nContinue:"); out.println("1. Yes"); out.println("2. No"); //out.print("\nEnter Choice: "); //int select = in.nextInt(); int select = getInteger("\nEnter Choice: "); if (select > 0 && select < 3) { switch (select) { case 1: //swap relationships gender = selectGender(); //if selected gender is different if (!gender.equals(f.getGender())) { //swap String g = f.getGender(); family.changeGender(gender, choice); family.changeGender(g, f.getPartner().getIndex()); if (g.equals("Male")) { for (FamilyMember m : f.getChildren()) { m.setMother(f); m.setFather(f.getPartner()); } } else { for (FamilyMember m : f.getChildren()) { m.setFather(f); m.setMother(f.getPartner()); } } } break; case 2: break; } } else { out.println("Invalid Choice"); } } private String formatString(String s) { String firstLetter = s.substring(0, 1); String remainingLetters = s.substring(1, s.length()); s = firstLetter.toUpperCase() + remainingLetters.toLowerCase(); return s; } private String enterDateOfBirth() { out.print("Enter Year Of Birth (0 - 2011): "); String y = in.nextLine(); out.print("Enter Month Of Birth (1-12): "); String m = in.nextLine(); if (m.trim().equals("")) { m = "0"; } if (Integer.parseInt(m) < 10) { m = "0" + m; } m += "-"; out.print("Enter Date of Birth (1-31): "); String d = in.nextLine(); if (d.trim().equals("")) { d = "0"; } if (Integer.parseInt(d) < 10) { d = "0" + d; } d += "-"; String dob = d + m + y; while (!DateValidator.isValid(dob)) { out.println("Invalid Date. Try Again:"); dob = enterDateOfBirth(); } return (dob); } private void displayAncestors() { out.print("\nDisplay Ancestors For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); FamilyMember ms = findRootNode(node, 0, 2, -1); FamilyMember fs = findRootNode(node, 1, 2, -1); out.println("\nPrint Ancestors"); out.println("\nMothers Side"); if(ms==null){ out.println("Member has no mother"); }else{ printDescendants(ms, node, ms.getGeneration()); } out.println("\nFathers Side"); if(fs==null){ out.println("Member has no father"); }else{ printDescendants(fs, node, fs.getGeneration()); } } else { out.println("Invalid Option!"); } } private void displayDescendants() { out.print("\nDisplay Descendants For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); out.println("\nPrint Descendants"); printDescendants(node, null, 0); } else { out.println("Invalid Option!"); } } private FamilyMember findRootNode(FamilyMember node, int parent, int numGenerations, int count) { FamilyMember root; count++; if (count < numGenerations) { if (parent == 0) { if(node.hasMother()){ node = node.getMother(); }else{ return node; } } else { if(node.hasFather()){ node = node.getFather(); }else{ return node; } } root = findRootNode(node, 1, numGenerations, count); return root; } return node; } private int findHighestLeafGeneration(FamilyMember node) { int gen = node.getGeneration(); for (int i = 0; i < node.getChildren().size(); i++) { int highestChild = findHighestLeafGeneration(node.getChild(i)); if (highestChild > gen) { gen = highestChild; } } return gen; } private void printDescendants(FamilyMember root, FamilyMember node, int gen) { out.print((root.getGeneration() + 1) + " " + root.getFullName()); out.print(" [" + root.getDob() + "] "); if (root.getPartner() != null) { out.print("+Partner: " + root.getPartner().getFullName() + " [" + root.getPartner().getDob() + "] "); } if (root == node) { out.print("*"); } out.println(); if (!root.getChildren().isEmpty() && root != node) { for (int i = 0; i < root.getChildren().size(); i++) { for (int j = 0; j < root.getChild(i).getGeneration() - gen; j++) { out.print(" "); } printDescendants(root.getChild(i), node, gen); } } else { return; } } //retrieve highest generation public int getRootGeneration() { int min = family.getFamilyMember(0).getGeneration(); for (int i = 0; i < family.getFamilyMembers().size(); i++) { min = Math.min(min, family.getFamilyMember(i).getGeneration()); } return Math.abs(min); } public void sortGenerations() { int amount = getRootGeneration(); for (FamilyMember member : family.getFamilyMembers()) { member.setGeneration(member.getGeneration() + amount); } } //test method - temporary private void initialise() { family.addMember("Bart", "Simpson", "Male", "18-03-1985"); family.getFamilyMember(0).setIndex(0); family.addMember("Homer", "Simpson", "Male", "24-09-1957"); family.getFamilyMember(1).setIndex(1); family.addMember("Marge", "Simpson", "Female", "20-07-1960"); family.getFamilyMember(2).setIndex(2); family.addMember("Lisa", "Simpson", "Female", "28-01-1991"); family.getFamilyMember(3).setIndex(3); family.addMember("Abe", "Simpson", "Male", "10-03-1920"); family.getFamilyMember(4).setIndex(4); family.addMember("Mona", "Simpson", "Female", "18-09-1921"); family.getFamilyMember(5).setIndex(5); //set relationships family.getFamilyMember(0).setMother(family.getFamilyMember(2)); family.getFamilyMember(0).setFather(family.getFamilyMember(1)); family.getFamilyMember(3).setMother(family.getFamilyMember(2)); family.getFamilyMember(3).setFather(family.getFamilyMember(1)); family.getFamilyMember(1).addChild(family.getFamilyMember(3)); family.getFamilyMember(1).addChild(family.getFamilyMember(0)); family.getFamilyMember(2).addChild(family.getFamilyMember(3)); family.getFamilyMember(2).addChild(family.getFamilyMember(0)); family.getFamilyMember(1).setPartner(family.getFamilyMember(2)); family.getFamilyMember(2).setPartner(family.getFamilyMember(1)); family.getFamilyMember(4).setPartner(family.getFamilyMember(5)); family.getFamilyMember(5).setPartner(family.getFamilyMember(4)); family.getFamilyMember(1).setMother(family.getFamilyMember(5)); family.getFamilyMember(1).setFather(family.getFamilyMember(4)); family.getFamilyMember(4).addChild(family.getFamilyMember(1)); family.getFamilyMember(5).addChild(family.getFamilyMember(1)); family.getFamilyMember(0).setGeneration(2); family.getFamilyMember(1).setGeneration(1); family.getFamilyMember(2).setGeneration(1); family.getFamilyMember(3).setGeneration(2); family.getFamilyMember(4).setGeneration(0); family.getFamilyMember(5).setGeneration(0); } }

最满意答案

所有任务都需要同样的努力。 它总是这样：

public void deleteFamilyMember(FamilyMember member) { member.mother.children.remove(member); member.father.children.remove(member); member.partner.children.remove(member); for (FamilyMember child:children) { if (child.father == member) child.father = null; if (child.mother == member) child.mother = null; if (child.partner == member) child.partner = null; } // now all references to this member are eliminated, gc will do the rest. }

例：

Homer.mother = ?? Homer.father = ?? Homer.partner = Marge Homer.children = {Bart, Lisa, Maggie} Marge.mother = ?? Marge.father = ?? Marge.partner = Homer Marge.children = {Bart, Lisa, Maggie} Bart.mother = Marge Bart.father = Homer Bart.partner = null Bart.children = {} Lisa.mother = Marge Lisa.father = Homer Lisa.partner = null Lisa.children = {} Maggie.mother = Marge Maggie.father = Homer Maggie.partner = null Maggie.children = {}

为了将Bart从家族树中移除，我们应该将Bart的母亲和父亲属性设置为null并且需要从荷马和Marge的孩子名单中移除Bart。

要删除Marge，我们必须将她的伴侣的伙伴设置为null（ Homer.partner ）并访问所有孩子以清除他们的mother属性（这是上面代码的这个child.mother部分）

All tasks require the same effort. It will always go like this:

public void deleteFamilyMember(FamilyMember member) { member.mother.children.remove(member); member.father.children.remove(member); member.partner.children.remove(member); for (FamilyMember child:children) { if (child.father == member) child.father = null; if (child.mother == member) child.mother = null; if (child.partner == member) child.partner = null; } // now all references to this member are eliminated, gc will do the rest. }

Example:

Homer.mother = ?? Homer.father = ?? Homer.partner = Marge Homer.children = {Bart, Lisa, Maggie} Marge.mother = ?? Marge.father = ?? Marge.partner = Homer Marge.children = {Bart, Lisa, Maggie} Bart.mother = Marge Bart.father = Homer Bart.partner = null Bart.children = {} Lisa.mother = Marge Lisa.father = Homer Lisa.partner = null Lisa.children = {} Maggie.mother = Marge Maggie.father = Homer Maggie.partner = null Maggie.children = {}

To remove Bart from the familiy tree, we should set Bart's mother and father attribute to null and need to remove Bart from Homer's and Marge's list of children.

To remove Marge, we have to set her partner's partner to null (Homer.partner) and visit all children to clear their mother attribute (that's this child.mother part of the code above)

删除族树中的节点(Deleting a node in a family tree)

我正在尝试计算删除族树中节点的最佳方法。 首先，稍微描述应用程序的工作原理。

我的应用程序做出以下假设：

任何节点只能有一个伙伴。 这意味着单个节点拥有的任何子节点，它也将是伙伴节点子节点。 因此，阶梯关系，离婚等不予补偿。 节点总是有两个父母 - 母亲和父亲不能单独添加。 如果用户不知道详细信息 - 节点属性设置为默认值。

此外，任何节点都可以添加父母，兄弟姐妹，孩子。 因此在法律上可以增加关系。

编辑：在研究了安德烈亚斯的回答之后，我逐渐意识到我的代码可能需要一些重新工作。 我正在尝试添加我的源代码，但它超出了charracters的限制......有什么建议吗？

这是FamilyTree类：

package familytree; import java.io.PrintStream; public class FamilyTree { private static final int DISPLAY_FAMILY_MEMBERS = 1; private static final int ADD_FAMILY_MEMBER = 2; private static final int REMOVE_FAMILY_MEMBER = 3; private static final int EDIT_FAMILY_MEMBER = 4; private static final int SAVE_FAMILY_TREE = 5; private static final int LOAD_FAMILY_TREE = 6; private static final int DISPLAY_ANCESTORS = 7; private static final int DISPLAY_DESCENDANTS = 8; private static final int QUIT = 9; private Input in; private Family family; private PrintStream out; public FamilyTree(Input in, PrintStream out) { this.in = in; this.out = out; family = new Family(); } public void start() { out.println("\nWelcome to the Family Tree Builder"); initialise(); while (true) { displayFamilyTreeMenu(); int command = getCommand(); if (quit(command)) { break; } executeOption(command); } } private int getCommand() { return getInteger("\nEnter command: "); } private int getInteger(String message) { while (true) { out.print(message); if (in.hasNextInt()) { int n = in.nextInt(); in.nextLine(); return n; } else { in.nextLine(); out.println("Your input was not understood. Please try again."); } } } //good private void displayFamilyTreeMenu() { out.println("\nFamily Tree Menu"); out.println(DISPLAY_FAMILY_MEMBERS + ". Display Family Members"); out.println(ADD_FAMILY_MEMBER + ". Add Family Member"); out.println(REMOVE_FAMILY_MEMBER + ". Remove Family Member"); out.println(EDIT_FAMILY_MEMBER + ". Edit Family Member"); out.println(SAVE_FAMILY_TREE + ". Save Family Tree"); out.println(LOAD_FAMILY_TREE + ". Load Family Tree"); out.println(DISPLAY_ANCESTORS + ". Display Ancestors"); out.println(DISPLAY_DESCENDANTS + ". Display Descendants"); out.println(QUIT + ". Quit"); } //good private boolean quit(int opt) { return (opt == QUIT) ? true : false; } //good private void executeOption(int choice) { switch (choice) { case DISPLAY_FAMILY_MEMBERS: displayFamilyMembers(); break; case ADD_FAMILY_MEMBER: addFamilyMember(); break; case REMOVE_FAMILY_MEMBER: removeMember(); break; case EDIT_FAMILY_MEMBER: editMember(); break; case SAVE_FAMILY_TREE: saveFamilyTree(); break; case LOAD_FAMILY_TREE: loadFamilyTree(); break; case DISPLAY_ANCESTORS: displayAncestors(); break; case DISPLAY_DESCENDANTS: displayDescendants(); break; default: out.println("Not a valid option! Try again."); break; } } private void removeMember() { displayFamilyMembers(); int choice = selectMember(); if (choice >= 0) { FamilyMember f = family.getFamilyMember(choice); if (f.getIndex() == 0) { out.println("Cannot delete yourself!"); return; } deleteMember(f); } } private void deleteMember(FamilyMember f) { //remove from tree family.removeMember(f); //remove all links to this person if (f.hasParents()) { f.getMother().removeChild(f); f.getFather().removeChild(f); } if(f.getPartner()!=null){ f.getPartner().setPartner(null); f.setPartner(null); } if (f.hasChildren()) { for (FamilyMember member : f.getChildren()) { if (f == member.getMother()) { member.setMother(null); } if (f == member.getFather()) { member.setFather(null); } if (f == member.getPartner()) { member.setPartner(null); } } } } private void saveFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileOutput output = new FileOutput(fileName); family.save(output); output.close(); saveRelationships(); } private void saveRelationships() { FileOutput output = new FileOutput("Relationships.txt"); family.saveRelationships(output); output.close(); } private void loadFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileInput input = new FileInput(fileName); family.load(input); input.close(); loadRelationships(); } private void loadRelationships() { FileInput input = new FileInput("Relationships.txt"); family.loadRelationships(input); input.close(); } //for selecting family member for editing adding nodes etc private void displayFamilyMembers() { out.println("\nDisplay Family Members"); int count = 0; for (FamilyMember member : family.getFamilyMembers()) { out.println(); if (count + 1 < 10) { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } else { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } count++; } } private int selectRelative() { out.println("\nSelect Relative"); out.println("1. Add Parents"); out.println("2. Add Child"); out.println("3. Add Partner"); out.println("4. Add Sibling"); //out.print("\nEnter Choice: "); //int choice = in.nextInt(); int choice = getInteger("\nEnter Choice: "); if (choice > 0 && choice < 5) { return choice; } return (-1); } private void addFamilyMember() { if (family.getFamilyMembers().isEmpty()) { out.println("No Members To Add To"); return; } int memberIndex = selectMember(); if (memberIndex >= 0) { FamilyMember member = family.getFamilyMember(memberIndex); int relative = selectRelative(); if (relative > 0) { out.println("\nAdd Member"); //if choice is valid switch (relative) { case 1: //adding parents FamilyMember mum, dad; if (!member.hasParents()) { out.println("Enter Mothers Details"); mum = addMember(relative, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(relative, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has parents."); } break; case 2: //adding child if (member.getPartner() == null) { FamilyMember partner; if (member.getGender().equals("Male")) { out.println("Enter Mothers Details"); partner = addMember(1, "Female"); } else { out.println("Enter Fathers Details"); partner = addMember(1, "Male"); } //create partner member.linkPartner(partner); partner.setGeneration(member.getGeneration()); out.println(); } out.println("Enter Childs Details"); FamilyMember child = addMember(relative, ""); child.linkParent(member); child.linkParent(member.getPartner()); child.setGeneration(member.getGeneration() + 1); sortGenerations(); break; case 3: //adding partner if (member.getPartner() == null) { out.println("Enter Partners Details"); FamilyMember partner = addMember(relative, ""); member.linkPartner(partner); partner.setGeneration(member.getGeneration()); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has a partner."); } break; case 4: //adding sibling if (member.getFather() == null) { out.println("Enter Mothers Details"); mum = addMember(1, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(1, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); out.println("\nEnter Siblings Details"); } else { out.println("Enter Siblings Details"); } FamilyMember sibling = addMember(relative, ""); //create mum and dad mum = member.getMother(); dad = member.getFather(); sibling.linkParent(mum); sibling.linkParent(dad); sibling.setGeneration(member.getGeneration()); break; } } else { out.println("Invalid Option!"); } } else { out.println("Invalid Option!"); } } private int selectMember() { displayFamilyMembers(); //out.print("\nSelect Member: "); //int choice = in.nextInt(); int choice = getInteger("\nSelect Member: "); if (choice > 0 && choice <= family.getFamilyMembers().size()) { return (choice - 1); } return -1; } private void editMember() { int choice = selectMember(); if (choice >= 0) { out.println("Select Detail To Edit: "); out.println("1. Name"); out.println("2. Gender"); out.println("3. Date of Birth"); //out.print("\nEnter Choice: "); //int opt = in.nextInt(); int opt = getInteger("\nEnter Choice: "); if (opt > 0 && opt < 4) { switch (opt) { case 1: //name out.print("Enter New First Name: "); String fName = in.nextLine(); out.print("Enter New Last Name: "); String lName = in.nextLine(); family.changeName(fName, lName, choice); break; case 2: //Gender FamilyMember f = family.getFamilyMember(choice); String gender = f.getGender(); if (f.getChildren().isEmpty()) { gender = selectGender(); family.changeGender(gender, choice); } else { //swap genders //swap mother father relationships for kids swapGenders(f, choice); } break; case 3: String dob = enterDateOfBirth(); family.changeDOB(dob, choice); } } else { out.println("Invalid Choice!"); } } } private FamilyMember addMember(int option, String gender) { out.print("Enter First Name: "); String fName = formatString(in.nextLine().trim()); out.print("Enter Last Name: "); String lName = formatString(in.nextLine().trim()); //String gender; if (option != 1) { //if not adding parents gender = selectGender(); } String dob = enterDateOfBirth(); FamilyMember f = family.getFamilyMember(family.addMember(fName, lName, gender, dob)); f.setIndex(family.getFamilyMembers().size() - 1); return (f); } private String selectGender() { String gender = null; out.println("Select Gender"); out.println("1. Male"); out.println("2. Female"); //out.print("Enter Choice: "); //int gOpt = in.nextInt(); int gOpt = getInteger("Enter Choice: "); if (gOpt == 1) { gender = "Male"; } else if (gOpt == 2) { gender = "Female"; } else { out.println("Invalid Choice"); } return gender; } private void swapGenders(FamilyMember f, int choice) { String gender; out.println("\nNOTE: Editing A Parent Nodes Gender Will Swap Parents Genders\n" + "And Swap Mother/Father Relationships For All Children."); out.println("\nContinue:"); out.println("1. Yes"); out.println("2. No"); //out.print("\nEnter Choice: "); //int select = in.nextInt(); int select = getInteger("\nEnter Choice: "); if (select > 0 && select < 3) { switch (select) { case 1: //swap relationships gender = selectGender(); //if selected gender is different if (!gender.equals(f.getGender())) { //swap String g = f.getGender(); family.changeGender(gender, choice); family.changeGender(g, f.getPartner().getIndex()); if (g.equals("Male")) { for (FamilyMember m : f.getChildren()) { m.setMother(f); m.setFather(f.getPartner()); } } else { for (FamilyMember m : f.getChildren()) { m.setFather(f); m.setMother(f.getPartner()); } } } break; case 2: break; } } else { out.println("Invalid Choice"); } } private String formatString(String s) { String firstLetter = s.substring(0, 1); String remainingLetters = s.substring(1, s.length()); s = firstLetter.toUpperCase() + remainingLetters.toLowerCase(); return s; } private String enterDateOfBirth() { out.print("Enter Year Of Birth (0 - 2011): "); String y = in.nextLine(); out.print("Enter Month Of Birth (1-12): "); String m = in.nextLine(); if (m.trim().equals("")) { m = "0"; } if (Integer.parseInt(m) < 10) { m = "0" + m; } m += "-"; out.print("Enter Date of Birth (1-31): "); String d = in.nextLine(); if (d.trim().equals("")) { d = "0"; } if (Integer.parseInt(d) < 10) { d = "0" + d; } d += "-"; String dob = d + m + y; while (!DateValidator.isValid(dob)) { out.println("Invalid Date. Try Again:"); dob = enterDateOfBirth(); } return (dob); } private void displayAncestors() { out.print("\nDisplay Ancestors For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); FamilyMember ms = findRootNode(node, 0, 2, -1); FamilyMember fs = findRootNode(node, 1, 2, -1); out.println("\nPrint Ancestors"); out.println("\nMothers Side"); if(ms==null){ out.println("Member has no mother"); }else{ printDescendants(ms, node, ms.getGeneration()); } out.println("\nFathers Side"); if(fs==null){ out.println("Member has no father"); }else{ printDescendants(fs, node, fs.getGeneration()); } } else { out.println("Invalid Option!"); } } private void displayDescendants() { out.print("\nDisplay Descendants For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); out.println("\nPrint Descendants"); printDescendants(node, null, 0); } else { out.println("Invalid Option!"); } } private FamilyMember findRootNode(FamilyMember node, int parent, int numGenerations, int count) { FamilyMember root; count++; if (count < numGenerations) { if (parent == 0) { if(node.hasMother()){ node = node.getMother(); }else{ return node; } } else { if(node.hasFather()){ node = node.getFather(); }else{ return node; } } root = findRootNode(node, 1, numGenerations, count); return root; } return node; } private int findHighestLeafGeneration(FamilyMember node) { int gen = node.getGeneration(); for (int i = 0; i < node.getChildren().size(); i++) { int highestChild = findHighestLeafGeneration(node.getChild(i)); if (highestChild > gen) { gen = highestChild; } } return gen; } private void printDescendants(FamilyMember root, FamilyMember node, int gen) { out.print((root.getGeneration() + 1) + " " + root.getFullName()); out.print(" [" + root.getDob() + "] "); if (root.getPartner() != null) { out.print("+Partner: " + root.getPartner().getFullName() + " [" + root.getPartner().getDob() + "] "); } if (root == node) { out.print("*"); } out.println(); if (!root.getChildren().isEmpty() && root != node) { for (int i = 0; i < root.getChildren().size(); i++) { for (int j = 0; j < root.getChild(i).getGeneration() - gen; j++) { out.print(" "); } printDescendants(root.getChild(i), node, gen); } } else { return; } } //retrieve highest generation public int getRootGeneration() { int min = family.getFamilyMember(0).getGeneration(); for (int i = 0; i < family.getFamilyMembers().size(); i++) { min = Math.min(min, family.getFamilyMember(i).getGeneration()); } return Math.abs(min); } public void sortGenerations() { int amount = getRootGeneration(); for (FamilyMember member : family.getFamilyMembers()) { member.setGeneration(member.getGeneration() + amount); } } //test method - temporary private void initialise() { family.addMember("Bart", "Simpson", "Male", "18-03-1985"); family.getFamilyMember(0).setIndex(0); family.addMember("Homer", "Simpson", "Male", "24-09-1957"); family.getFamilyMember(1).setIndex(1); family.addMember("Marge", "Simpson", "Female", "20-07-1960"); family.getFamilyMember(2).setIndex(2); family.addMember("Lisa", "Simpson", "Female", "28-01-1991"); family.getFamilyMember(3).setIndex(3); family.addMember("Abe", "Simpson", "Male", "10-03-1920"); family.getFamilyMember(4).setIndex(4); family.addMember("Mona", "Simpson", "Female", "18-09-1921"); family.getFamilyMember(5).setIndex(5); //set relationships family.getFamilyMember(0).setMother(family.getFamilyMember(2)); family.getFamilyMember(0).setFather(family.getFamilyMember(1)); family.getFamilyMember(3).setMother(family.getFamilyMember(2)); family.getFamilyMember(3).setFather(family.getFamilyMember(1)); family.getFamilyMember(1).addChild(family.getFamilyMember(3)); family.getFamilyMember(1).addChild(family.getFamilyMember(0)); family.getFamilyMember(2).addChild(family.getFamilyMember(3)); family.getFamilyMember(2).addChild(family.getFamilyMember(0)); family.getFamilyMember(1).setPartner(family.getFamilyMember(2)); family.getFamilyMember(2).setPartner(family.getFamilyMember(1)); family.getFamilyMember(4).setPartner(family.getFamilyMember(5)); family.getFamilyMember(5).setPartner(family.getFamilyMember(4)); family.getFamilyMember(1).setMother(family.getFamilyMember(5)); family.getFamilyMember(1).setFather(family.getFamilyMember(4)); family.getFamilyMember(4).addChild(family.getFamilyMember(1)); family.getFamilyMember(5).addChild(family.getFamilyMember(1)); family.getFamilyMember(0).setGeneration(2); family.getFamilyMember(1).setGeneration(1); family.getFamilyMember(2).setGeneration(1); family.getFamilyMember(3).setGeneration(2); family.getFamilyMember(4).setGeneration(0); family.getFamilyMember(5).setGeneration(0); } }

I'm trying to calclulate the best way to delete a node in a family tree. First, a little description of how the app works.

My app makes the following assumption:

Any node can only have one partner. That means that any child a single node has, it will also be the partner nodes child too. Therefore, step relations, divorces etc aren't compensated for. A node always has two parents - A mother and father cannot be added seperately. If the user doesn't know the details - the nodes attributes are set to a default value.

Also any node can add parents, siblings, children to itself. Therefore in law relationships can be added.

EDIT: After studying Andreas' answer, I have come to realise that my code may need some re-working. I'm trying to add my source but it exceeds the limit of charracters...Any advice?

Here is the FamilyTree Class:

package familytree; import java.io.PrintStream; public class FamilyTree { private static final int DISPLAY_FAMILY_MEMBERS = 1; private static final int ADD_FAMILY_MEMBER = 2; private static final int REMOVE_FAMILY_MEMBER = 3; private static final int EDIT_FAMILY_MEMBER = 4; private static final int SAVE_FAMILY_TREE = 5; private static final int LOAD_FAMILY_TREE = 6; private static final int DISPLAY_ANCESTORS = 7; private static final int DISPLAY_DESCENDANTS = 8; private static final int QUIT = 9; private Input in; private Family family; private PrintStream out; public FamilyTree(Input in, PrintStream out) { this.in = in; this.out = out; family = new Family(); } public void start() { out.println("\nWelcome to the Family Tree Builder"); initialise(); while (true) { displayFamilyTreeMenu(); int command = getCommand(); if (quit(command)) { break; } executeOption(command); } } private int getCommand() { return getInteger("\nEnter command: "); } private int getInteger(String message) { while (true) { out.print(message); if (in.hasNextInt()) { int n = in.nextInt(); in.nextLine(); return n; } else { in.nextLine(); out.println("Your input was not understood. Please try again."); } } } //good private void displayFamilyTreeMenu() { out.println("\nFamily Tree Menu"); out.println(DISPLAY_FAMILY_MEMBERS + ". Display Family Members"); out.println(ADD_FAMILY_MEMBER + ". Add Family Member"); out.println(REMOVE_FAMILY_MEMBER + ". Remove Family Member"); out.println(EDIT_FAMILY_MEMBER + ". Edit Family Member"); out.println(SAVE_FAMILY_TREE + ". Save Family Tree"); out.println(LOAD_FAMILY_TREE + ". Load Family Tree"); out.println(DISPLAY_ANCESTORS + ". Display Ancestors"); out.println(DISPLAY_DESCENDANTS + ". Display Descendants"); out.println(QUIT + ". Quit"); } //good private boolean quit(int opt) { return (opt == QUIT) ? true : false; } //good private void executeOption(int choice) { switch (choice) { case DISPLAY_FAMILY_MEMBERS: displayFamilyMembers(); break; case ADD_FAMILY_MEMBER: addFamilyMember(); break; case REMOVE_FAMILY_MEMBER: removeMember(); break; case EDIT_FAMILY_MEMBER: editMember(); break; case SAVE_FAMILY_TREE: saveFamilyTree(); break; case LOAD_FAMILY_TREE: loadFamilyTree(); break; case DISPLAY_ANCESTORS: displayAncestors(); break; case DISPLAY_DESCENDANTS: displayDescendants(); break; default: out.println("Not a valid option! Try again."); break; } } private void removeMember() { displayFamilyMembers(); int choice = selectMember(); if (choice >= 0) { FamilyMember f = family.getFamilyMember(choice); if (f.getIndex() == 0) { out.println("Cannot delete yourself!"); return; } deleteMember(f); } } private void deleteMember(FamilyMember f) { //remove from tree family.removeMember(f); //remove all links to this person if (f.hasParents()) { f.getMother().removeChild(f); f.getFather().removeChild(f); } if(f.getPartner()!=null){ f.getPartner().setPartner(null); f.setPartner(null); } if (f.hasChildren()) { for (FamilyMember member : f.getChildren()) { if (f == member.getMother()) { member.setMother(null); } if (f == member.getFather()) { member.setFather(null); } if (f == member.getPartner()) { member.setPartner(null); } } } } private void saveFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileOutput output = new FileOutput(fileName); family.save(output); output.close(); saveRelationships(); } private void saveRelationships() { FileOutput output = new FileOutput("Relationships.txt"); family.saveRelationships(output); output.close(); } private void loadFamilyTree() { out.print("Enter file name: "); String fileName = in.nextLine(); FileInput input = new FileInput(fileName); family.load(input); input.close(); loadRelationships(); } private void loadRelationships() { FileInput input = new FileInput("Relationships.txt"); family.loadRelationships(input); input.close(); } //for selecting family member for editing adding nodes etc private void displayFamilyMembers() { out.println("\nDisplay Family Members"); int count = 0; for (FamilyMember member : family.getFamilyMembers()) { out.println(); if (count + 1 < 10) { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } else { out.println((count + 1) + ". " + member.getFirstName() + " " + member.getLastName()); out.println(" " + member.getGender()); out.println(" " + member.getDob()); out.println(" Generation: " + (member.getGeneration() + 1)); } count++; } } private int selectRelative() { out.println("\nSelect Relative"); out.println("1. Add Parents"); out.println("2. Add Child"); out.println("3. Add Partner"); out.println("4. Add Sibling"); //out.print("\nEnter Choice: "); //int choice = in.nextInt(); int choice = getInteger("\nEnter Choice: "); if (choice > 0 && choice < 5) { return choice; } return (-1); } private void addFamilyMember() { if (family.getFamilyMembers().isEmpty()) { out.println("No Members To Add To"); return; } int memberIndex = selectMember(); if (memberIndex >= 0) { FamilyMember member = family.getFamilyMember(memberIndex); int relative = selectRelative(); if (relative > 0) { out.println("\nAdd Member"); //if choice is valid switch (relative) { case 1: //adding parents FamilyMember mum, dad; if (!member.hasParents()) { out.println("Enter Mothers Details"); mum = addMember(relative, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(relative, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has parents."); } break; case 2: //adding child if (member.getPartner() == null) { FamilyMember partner; if (member.getGender().equals("Male")) { out.println("Enter Mothers Details"); partner = addMember(1, "Female"); } else { out.println("Enter Fathers Details"); partner = addMember(1, "Male"); } //create partner member.linkPartner(partner); partner.setGeneration(member.getGeneration()); out.println(); } out.println("Enter Childs Details"); FamilyMember child = addMember(relative, ""); child.linkParent(member); child.linkParent(member.getPartner()); child.setGeneration(member.getGeneration() + 1); sortGenerations(); break; case 3: //adding partner if (member.getPartner() == null) { out.println("Enter Partners Details"); FamilyMember partner = addMember(relative, ""); member.linkPartner(partner); partner.setGeneration(member.getGeneration()); } else { out.println(member.getFirstName() + " " + member.getLastName() + " already has a partner."); } break; case 4: //adding sibling if (member.getFather() == null) { out.println("Enter Mothers Details"); mum = addMember(1, "Female"); out.println("\nEnter Fathers Details"); dad = addMember(1, "Male"); member.linkParent(mum); member.linkParent(dad); mum.linkPartner(dad); mum.setGeneration(member.getGeneration() - 1); dad.setGeneration(member.getGeneration() - 1); sortGenerations(); out.println("\nEnter Siblings Details"); } else { out.println("Enter Siblings Details"); } FamilyMember sibling = addMember(relative, ""); //create mum and dad mum = member.getMother(); dad = member.getFather(); sibling.linkParent(mum); sibling.linkParent(dad); sibling.setGeneration(member.getGeneration()); break; } } else { out.println("Invalid Option!"); } } else { out.println("Invalid Option!"); } } private int selectMember() { displayFamilyMembers(); //out.print("\nSelect Member: "); //int choice = in.nextInt(); int choice = getInteger("\nSelect Member: "); if (choice > 0 && choice <= family.getFamilyMembers().size()) { return (choice - 1); } return -1; } private void editMember() { int choice = selectMember(); if (choice >= 0) { out.println("Select Detail To Edit: "); out.println("1. Name"); out.println("2. Gender"); out.println("3. Date of Birth"); //out.print("\nEnter Choice: "); //int opt = in.nextInt(); int opt = getInteger("\nEnter Choice: "); if (opt > 0 && opt < 4) { switch (opt) { case 1: //name out.print("Enter New First Name: "); String fName = in.nextLine(); out.print("Enter New Last Name: "); String lName = in.nextLine(); family.changeName(fName, lName, choice); break; case 2: //Gender FamilyMember f = family.getFamilyMember(choice); String gender = f.getGender(); if (f.getChildren().isEmpty()) { gender = selectGender(); family.changeGender(gender, choice); } else { //swap genders //swap mother father relationships for kids swapGenders(f, choice); } break; case 3: String dob = enterDateOfBirth(); family.changeDOB(dob, choice); } } else { out.println("Invalid Choice!"); } } } private FamilyMember addMember(int option, String gender) { out.print("Enter First Name: "); String fName = formatString(in.nextLine().trim()); out.print("Enter Last Name: "); String lName = formatString(in.nextLine().trim()); //String gender; if (option != 1) { //if not adding parents gender = selectGender(); } String dob = enterDateOfBirth(); FamilyMember f = family.getFamilyMember(family.addMember(fName, lName, gender, dob)); f.setIndex(family.getFamilyMembers().size() - 1); return (f); } private String selectGender() { String gender = null; out.println("Select Gender"); out.println("1. Male"); out.println("2. Female"); //out.print("Enter Choice: "); //int gOpt = in.nextInt(); int gOpt = getInteger("Enter Choice: "); if (gOpt == 1) { gender = "Male"; } else if (gOpt == 2) { gender = "Female"; } else { out.println("Invalid Choice"); } return gender; } private void swapGenders(FamilyMember f, int choice) { String gender; out.println("\nNOTE: Editing A Parent Nodes Gender Will Swap Parents Genders\n" + "And Swap Mother/Father Relationships For All Children."); out.println("\nContinue:"); out.println("1. Yes"); out.println("2. No"); //out.print("\nEnter Choice: "); //int select = in.nextInt(); int select = getInteger("\nEnter Choice: "); if (select > 0 && select < 3) { switch (select) { case 1: //swap relationships gender = selectGender(); //if selected gender is different if (!gender.equals(f.getGender())) { //swap String g = f.getGender(); family.changeGender(gender, choice); family.changeGender(g, f.getPartner().getIndex()); if (g.equals("Male")) { for (FamilyMember m : f.getChildren()) { m.setMother(f); m.setFather(f.getPartner()); } } else { for (FamilyMember m : f.getChildren()) { m.setFather(f); m.setMother(f.getPartner()); } } } break; case 2: break; } } else { out.println("Invalid Choice"); } } private String formatString(String s) { String firstLetter = s.substring(0, 1); String remainingLetters = s.substring(1, s.length()); s = firstLetter.toUpperCase() + remainingLetters.toLowerCase(); return s; } private String enterDateOfBirth() { out.print("Enter Year Of Birth (0 - 2011): "); String y = in.nextLine(); out.print("Enter Month Of Birth (1-12): "); String m = in.nextLine(); if (m.trim().equals("")) { m = "0"; } if (Integer.parseInt(m) < 10) { m = "0" + m; } m += "-"; out.print("Enter Date of Birth (1-31): "); String d = in.nextLine(); if (d.trim().equals("")) { d = "0"; } if (Integer.parseInt(d) < 10) { d = "0" + d; } d += "-"; String dob = d + m + y; while (!DateValidator.isValid(dob)) { out.println("Invalid Date. Try Again:"); dob = enterDateOfBirth(); } return (dob); } private void displayAncestors() { out.print("\nDisplay Ancestors For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); FamilyMember ms = findRootNode(node, 0, 2, -1); FamilyMember fs = findRootNode(node, 1, 2, -1); out.println("\nPrint Ancestors"); out.println("\nMothers Side"); if(ms==null){ out.println("Member has no mother"); }else{ printDescendants(ms, node, ms.getGeneration()); } out.println("\nFathers Side"); if(fs==null){ out.println("Member has no father"); }else{ printDescendants(fs, node, fs.getGeneration()); } } else { out.println("Invalid Option!"); } } private void displayDescendants() { out.print("\nDisplay Descendants For Which Member: "); int choice = selectMember(); if (choice >= 0) { FamilyMember node = family.getFamilyMember(choice); out.println("\nPrint Descendants"); printDescendants(node, null, 0); } else { out.println("Invalid Option!"); } } private FamilyMember findRootNode(FamilyMember node, int parent, int numGenerations, int count) { FamilyMember root; count++; if (count < numGenerations) { if (parent == 0) { if(node.hasMother()){ node = node.getMother(); }else{ return node; } } else { if(node.hasFather()){ node = node.getFather(); }else{ return node; } } root = findRootNode(node, 1, numGenerations, count); return root; } return node; } private int findHighestLeafGeneration(FamilyMember node) { int gen = node.getGeneration(); for (int i = 0; i < node.getChildren().size(); i++) { int highestChild = findHighestLeafGeneration(node.getChild(i)); if (highestChild > gen) { gen = highestChild; } } return gen; } private void printDescendants(FamilyMember root, FamilyMember node, int gen) { out.print((root.getGeneration() + 1) + " " + root.getFullName()); out.print(" [" + root.getDob() + "] "); if (root.getPartner() != null) { out.print("+Partner: " + root.getPartner().getFullName() + " [" + root.getPartner().getDob() + "] "); } if (root == node) { out.print("*"); } out.println(); if (!root.getChildren().isEmpty() && root != node) { for (int i = 0; i < root.getChildren().size(); i++) { for (int j = 0; j < root.getChild(i).getGeneration() - gen; j++) { out.print(" "); } printDescendants(root.getChild(i), node, gen); } } else { return; } } //retrieve highest generation public int getRootGeneration() { int min = family.getFamilyMember(0).getGeneration(); for (int i = 0; i < family.getFamilyMembers().size(); i++) { min = Math.min(min, family.getFamilyMember(i).getGeneration()); } return Math.abs(min); } public void sortGenerations() { int amount = getRootGeneration(); for (FamilyMember member : family.getFamilyMembers()) { member.setGeneration(member.getGeneration() + amount); } } //test method - temporary private void initialise() { family.addMember("Bart", "Simpson", "Male", "18-03-1985"); family.getFamilyMember(0).setIndex(0); family.addMember("Homer", "Simpson", "Male", "24-09-1957"); family.getFamilyMember(1).setIndex(1); family.addMember("Marge", "Simpson", "Female", "20-07-1960"); family.getFamilyMember(2).setIndex(2); family.addMember("Lisa", "Simpson", "Female", "28-01-1991"); family.getFamilyMember(3).setIndex(3); family.addMember("Abe", "Simpson", "Male", "10-03-1920"); family.getFamilyMember(4).setIndex(4); family.addMember("Mona", "Simpson", "Female", "18-09-1921"); family.getFamilyMember(5).setIndex(5); //set relationships family.getFamilyMember(0).setMother(family.getFamilyMember(2)); family.getFamilyMember(0).setFather(family.getFamilyMember(1)); family.getFamilyMember(3).setMother(family.getFamilyMember(2)); family.getFamilyMember(3).setFather(family.getFamilyMember(1)); family.getFamilyMember(1).addChild(family.getFamilyMember(3)); family.getFamilyMember(1).addChild(family.getFamilyMember(0)); family.getFamilyMember(2).addChild(family.getFamilyMember(3)); family.getFamilyMember(2).addChild(family.getFamilyMember(0)); family.getFamilyMember(1).setPartner(family.getFamilyMember(2)); family.getFamilyMember(2).setPartner(family.getFamilyMember(1)); family.getFamilyMember(4).setPartner(family.getFamilyMember(5)); family.getFamilyMember(5).setPartner(family.getFamilyMember(4)); family.getFamilyMember(1).setMother(family.getFamilyMember(5)); family.getFamilyMember(1).setFather(family.getFamilyMember(4)); family.getFamilyMember(4).addChild(family.getFamilyMember(1)); family.getFamilyMember(5).addChild(family.getFamilyMember(1)); family.getFamilyMember(0).setGeneration(2); family.getFamilyMember(1).setGeneration(1); family.getFamilyMember(2).setGeneration(1); family.getFamilyMember(3).setGeneration(2); family.getFamilyMember(4).setGeneration(0); family.getFamilyMember(5).setGeneration(0); } }

最满意答案

所有任务都需要同样的努力。 它总是这样：

public void deleteFamilyMember(FamilyMember member) { member.mother.children.remove(member); member.father.children.remove(member); member.partner.children.remove(member); for (FamilyMember child:children) { if (child.father == member) child.father = null; if (child.mother == member) child.mother = null; if (child.partner == member) child.partner = null; } // now all references to this member are eliminated, gc will do the rest. }

例：

Homer.mother = ?? Homer.father = ?? Homer.partner = Marge Homer.children = {Bart, Lisa, Maggie} Marge.mother = ?? Marge.father = ?? Marge.partner = Homer Marge.children = {Bart, Lisa, Maggie} Bart.mother = Marge Bart.father = Homer Bart.partner = null Bart.children = {} Lisa.mother = Marge Lisa.father = Homer Lisa.partner = null Lisa.children = {} Maggie.mother = Marge Maggie.father = Homer Maggie.partner = null Maggie.children = {}

为了将Bart从家族树中移除，我们应该将Bart的母亲和父亲属性设置为null并且需要从荷马和Marge的孩子名单中移除Bart。

要删除Marge，我们必须将她的伴侣的伙伴设置为null（ Homer.partner ）并访问所有孩子以清除他们的mother属性（这是上面代码的这个child.mother部分）

All tasks require the same effort. It will always go like this:

public void deleteFamilyMember(FamilyMember member) { member.mother.children.remove(member); member.father.children.remove(member); member.partner.children.remove(member); for (FamilyMember child:children) { if (child.father == member) child.father = null; if (child.mother == member) child.mother = null; if (child.partner == member) child.partner = null; } // now all references to this member are eliminated, gc will do the rest. }

Example:

Homer.mother = ?? Homer.father = ?? Homer.partner = Marge Homer.children = {Bart, Lisa, Maggie} Marge.mother = ?? Marge.father = ?? Marge.partner = Homer Marge.children = {Bart, Lisa, Maggie} Bart.mother = Marge Bart.father = Homer Bart.partner = null Bart.children = {} Lisa.mother = Marge Lisa.father = Homer Lisa.partner = null Lisa.children = {} Maggie.mother = Marge Maggie.father = Homer Maggie.partner = null Maggie.children = {}

To remove Bart from the familiy tree, we should set Bart's mother and father attribute to null and need to remove Bart from Homer's and Marge's list of children.

To remove Marge, we have to set her partner's partner to null (Homer.partner) and visit all children to clear their mother attribute (that's this child.mother part of the code above)