java - 删除家谱中的节点

Question

我正在尝试计算删除家谱中节点的最佳方法。首先，简单介绍一下该应用的工作原理。

我的应用做出以下假设:

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

此外，任何节点都可以向自身添加父节点、兄弟节点、子节点。因此可以添加法律关系。

编辑:在研究了 Andreas 的回答后，我开始意识到我的代码可能需要重新编写。我正在尝试添加我的来源，但它超出了字符数限制...有什么建议吗？

这是 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);
    }
}

Answer 1

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

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 并且需要从 Homer 和Marge 的 child 名单。

要删除 Marge，我们必须将她搭档的搭档设置为空 (Homer.partner) 并访问所有 child 以清除他们的 mother 属性(就是这个 child.mother 上面的部分代码)