数据结构第六章选做题：

公司雇员
设计一个程序维护公司的人事关系情况。程序一开始，需要首先任命一名 CEO，之后任意一
个雇员可以雇佣和被解雇。也就是说，任意一名雇员可以雇佣自己的下属，公司中的任意一
名雇员（包括 CEO）也都可以被解雇。公司的层次化结构可以用树来表达。某一层次的雇员
其级别低于上一层次的雇员，同一层次的雇员从左至右级别降低。
当有雇员离职或者被解雇的时候，如果他没有任何下属，则直接被解雇就可以了。如果他有
下属，则他的第一个级别最高的下属将提拔为他的继任者。之后，他的继任者原来的位置则
按同样原则填补上来。
根据上述原则，请写出程序能够动态显示这个公司的员工情况。
输入：第一行输入为 CEO 的名字。接下来的输入可以是下面任意一个命令。
•[existing member] hires [new member]
•fire [existing member]
•print

思路：

*换值大法yyds*
	按照题目要求的删除方式来说，换值最方便了，只需要和孩纸节点换换值，
孩纸节点在接着和孩纸节点换换值，其他的高度值啊，兄弟节点啊，
都不用变，多么实在。（不会换指针法的自我安慰）


	憋了一个小时没整出来，怎么像树那样标准的换指针，想着我的5.1假期，
想着我还要追的剧，还要追的番，还要玩的游戏。就开始想偷懒，不换指针了，
嘻嘻，还不错，重申一遍，***换值大法***yyds。

代码：

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Hire {
    private HashMap<String, Integer> map = new HashMap<>();//name -> val
    private String[] name;//val -> name 如果这个人后来被删了，就用“”代替
    private TreeSiblingAndChildren tree;//保存节点树
    public Hire(String fileName) throws IOException {
        List<String> lines = Files.readAllLines(Path.of(fileName));
        name = new String[lines.size()];//数组大小可以稍微开大一些，无影响
        map.put(lines.get(0),0);
        name[0] = lines.get(0);
        int val = 1;
        tree = new TreeSiblingAndChildren(new int[]{0}, new int[]{0});
        for (int i = 1; i < lines.size(); i++){
            String[] a = lines.get(i).split(" ");
            if (a.length == 1){
                Queue<TreeSiblingAndChildren.Node> queue = new LinkedList<>();
                queue.add(tree.getRoot());
                while (!queue.isEmpty()){
                    var node = queue.poll();
                    while (node != null){
                        System.out.println("+".repeat(node.getHeight()-1) + name[node.getVal()]);
                        if (node.getChildSq() != null)
                            queue.add(node.getChildSq());
                        node = node.getSibling();
                    }
                }
                System.out.println("-".repeat(20));
            }
            else if (a.length == 2){
                int p = map.get(a[1]);
                tree.delete(p);
                name[p] = "";
                map.remove(a[1]);
            }
            else if (a.length == 3){
                int p = map.get(a[0]);
                map.put(a[2],val);
                name[val] = a[2];
                tree.add(p,val++);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String fileName = "C:\\Users\\21991\\IdeaProjects\\写会题\\src\\hire.txt";
        Hire hire = new Hire(fileName);
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class TreeSiblingAndChildren {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public TreeSiblingAndChildren(int[] values, int[] d){
        if (values == null) return;
        int i = 0, k = 0;   //i 用来依次访问各节点值， k用来访问节点的度数；
        root = new Node(values[i++]);
        Queue<Node> queue = new LinkedList<>(); //用队列来保证访问次序与层序访问是一样的
        queue.add(root);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            if (d[k] == 0){     //该店度数为零，无子节点
                k++;
                continue;
            }
            Node child = new Node(values[i++]);     //先确定子表头指针
            node.ChildSq = child;
            queue.add(child);
            for (int j = 1; j < d[k]; j++){     //建立子链表的兄弟链表
                Node nextChild = new Node(values[i++]);
                queue.add(nextChild);
                child.Sibling = nextChild;
                child = nextChild;
            }
            k++;
        }
        height();
    }
    private void height(){
        height(root,0);
    }
    private void height(Node node, int preHeight){
        if (node == null)   return;
        Node n = node;
        while (n != null){
            n.height = preHeight + 1;
            height(n.ChildSq,n.height);
            n = n.Sibling;
        }
    }
    public void delete(int v){
        Node n = new Node(0);
        n.ChildSq = root;
        //用一个队列来保存有孩子的节点，待会可以遍历它
        //检查的过程为横向遍历
        Queue<Node> queue = new LinkedList<>();
        queue.add(n);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            Node ch = cur.ChildSq;
            while (ch != null){
                if (ch.ChildSq != null) queue.add(ch);
                if (ch.val == v){
                    Node pre = cur.ChildSq;//找到它的前驱兄弟节点
                    if (pre == ch){
                        cur.ChildSq = del(cur.ChildSq);
                        return;
                    }
                    while (pre.Sibling != ch)
                        pre = pre.Sibling;
                    pre.Sibling = del(ch);
                    return;
                }
                ch = ch.Sibling;
            }
        }

    }
    //删除节点，换指针的话，太麻烦了吧，憋不住开来，所以只好换值了
    //如果该节点有孩纸节点，就拿孩纸节点的值来用，然后再删孩纸节点
    //只有该节点没有孩纸节点的时候，返回节点的兄弟节点
    //这样的话，连高度值都不用变，棒
    private Node del(Node node){
        if (node == null)   return null;
        if (node.ChildSq == null)   return node.Sibling;
        node.val = node.ChildSq.val;
        node.ChildSq = del(node.ChildSq);
        return node;
    }

    //找到父节点，然后在它的子节点尾加上新节点
    //依旧层次遍历
    public void add(int parents, int child){
        Node node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            while (cur != null){
                if (cur.val == parents){
                    Node son = new Node(child);
                    son.height = cur.height + 1;
                    if (cur.ChildSq == null)    cur.ChildSq = son;
                    else {
                        Node childSq = cur.ChildSq;
                        while (childSq.Sibling !=  null)
                            childSq = childSq.Sibling;
                        childSq.Sibling  = son;
                    }
                }
                if (cur.ChildSq != null)
                    queue.add(cur.ChildSq);
                cur = cur.Sibling;
            }
        }
    }
    @Override
    public String toString() {
        StringBuffer strings = new StringBuffer();
        Node node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            while (cur != null){
                if (cur.ChildSq != null)
                    queue.add(cur.ChildSq);
                strings.append("值 " + cur.val +" 高度" +cur.height + "\t");
                cur = cur.Sibling;
            }
        }
        return strings.toString();
    }
    public class Node{
        private int val;
        private Node ChildSq;
        private Node Sibling;
        private int height;
        public Node(int v){
            val = v;
        }

        public int getHeight() {
            return height;
        }

        public Node getChildSq() {
            return ChildSq;
        }

        public Node getSibling() {
            return Sibling;
        }

        public int getVal() {
            return val;
        }
    }

    public static void main(String[] args) {
        int[] values = {1,2,3,4,5,6,7};
        int[] d = {3,2,0,1,0,0,0};
        TreeSiblingAndChildren tree  = new TreeSiblingAndChildren(values,d);
        System.out.println("树的结构");
        System.out.println(tree);
    }
}

测试文件：
HYP
HYP hires ERT
HYP hires ASD
ERT hires BNM
ERT hires JKL
BNM hires IOP
BNM hires CVB
BNM hires GHJ
print
HYP hires QAZ
fire ERT
print
fire JKL
fire HYP
print