Java实现多叉树的遍历结点个数与插入结点

骑猪看日落 2022-02-19 00:15 251阅读 0赞

## 使用Java简单实现多叉树的遍历结点个数与插入结点 ##

#### 多叉树结点定义 ####

class Node {
        public int id;
        public List<Node> sonList;
        public int getId() {
            return id;
        }
    
        public Node(int id,List<Node> sonList) {
            this.id = id;
            this.sonList = sonList;
        }
        
        public void setId(int id) {
            this.id = id;
        }
    
        public List<Node> getSonList() {
            return sonList;
        }
    }

#### 多叉树的示例输入 ####

// 第一行为多叉树结点个数
    // 接下来有n-1行，每行有两个正整数x,y，表示在x和y结点之间存在一条边(1<=x<=y<=n)。默认y为x的根结点，结点1为多叉树的树根。
    6
    2 1
    3 2
    4 3
    5 2
    6 1

#### 代码： ####

###### 求以深度为2的结点为根结点的树，包含多少个结点，依次输出结点个数。 ######

###### 如图所示，即求结点2和6下有多少个子结点。 ######

![如图所示][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]

###### 主程序 ######

public static int nodenum = 0; // 结点个数
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = Integer.parseInt(in.nextLine())-1;
        int[][] tree = new int[count][2];
        for(int i=0;i<count;i++){
            String temp = in.nextLine();
            String[] ss = temp.trim().split(" ");
            tree[i][0] = Integer.parseInt(ss[0]);
            tree[i][1] = Integer.parseInt(ss[1]);
        }
    
        Node entry = new Node(1, new ArrayList<Node>());
    
        for(int i=0;i<count;i++){
            insert(entry, tree[i][1], new Node(tree[i][0], new ArrayList<Node>()));
        }
    
        List<Node> subtree = entry.sonList;
        int[] num = new int[entry.sonList.size()]; // 存放子结点个数
    
        for(int i=0;i<entry.sonList.size);i++){
            nodenum = 0;
            queryAll(entry.sonList.get(i));
            num[i] = nodenum;
        }
        for(int t:num)
        	System.out.println(t);
    }

###### 插入新结点 ######

public static void insert(Node changeNode, int fatherId, Node newNode) {
        if (fatherId==changeNode.getId()) {
            changeNode.getSonList().add(newNode);
            return;
        }
    
        List<Node> sonList = changeNode.getSonList();
        if (sonList == null || sonList.isEmpty()) 
            return;
        else 
            for (int i = 0; i < sonList.size(); i++) 
                insert(sonList.get(i), fatherId, newNode);
    }

###### 遍历结点个数 ######

public static void queryAll(Node changeNode){
        List<Node> sonList = changeNode.getSonList();
    
        if (sonList==null||sonList.isEmpty())
            return;
    
        for (int i = 0; i <sonList.size() ; i++) {
            nodenum += 1;
            queryAll(sonList.get(i));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220219/52804012090b453983dc5e4ed42bcc16.png