2018-09-19 用hashmap实现树形结构

上一篇文章中我们采用了最基本java代码来实现了一个多叉树结构，并作了一个简单的菜单功能（https://www.jianshu.com/p/7ad8ac588692）
而树形的父子关系我们完全可以采用map的结构来存储，可以用父节点当作value，子节点当作key。
每个父节点可以有多个子节点，相当于map中一个value值可以有多个key和其对应。
每个子节点只能有一个父节点，相当于map中一个key对应一个value值。

用map来实现多叉树代码如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class MyHashMapTree {

    private HashMap<String, String> map = new HashMap<String, String>();

    public void add(String father, String data) {
        map.put(data, father);
    }
    
    public String getFather(String data) {
        return map.get(data);
    }
    
    public List<String> getChildren(String father) {
        List<String> ret = new ArrayList<String>();
        // 遍历map
        Set<Map.Entry<String, String>> set = map.entrySet();
        for (Entry<String, String> entry : set) {
            if (entry.getValue().equals(father)) {
                ret.add(entry.getKey());
            }
        }
        return ret;
    }
    
    public static void main(String[] args) {
        MyHashMapTree a = new MyHashMapTree();
        a.add("世界", "亚洲");
        a.add("世界", "美洲");
        a.add("世界", "欧洲");
        a.add("亚洲", "中国");
        a.add("美洲", "美国");
        a.add("亚洲", "日本");
        a.add("中国", "河北");
        a.add("中国", "河南");
        a.add("中国", "广东");
        a.add("中国", "浙江");
        
        System.out.println(a.getFather("美国"));
        System.out.println("---------------");
        System.out.println(a.getChildren("中国"));
    }
}

通过上边代码发现，使用Map创建的tree时，获取父节点，获取子节点都很方便，代码更加的简洁。

下边，使用该tree来创建一个菜单

import java.util.List;
import java.util.Scanner;

public class MyHashMapMenu {
    MyHashMapTree tree = new MyHashMapTree();
    public void add(String father, String data) {
        tree.add(father, data);
    }
    
    public void run(String x) {
        
        Scanner scan = new Scanner(System.in);
        while (true) {
            List<String> childrens = tree.getChildren(x);
            if (childrens == null || childrens.isEmpty()) {
                System.out.println("你选择了:"+x);
            }
            
            System.out.println("------------");
            System.out.println("- " + x);
            for (int i = 0; i < childrens.size(); i++) {
                System.out.println("  " +i + "," + childrens.get(i));
            }
            System.out.println("  u,返回上一级");
            System.out.println("------------");
            System.out.println("请选择:");
            
            String s = scan.nextLine();
            if ("u".equals(s)) {
                String x1 = tree.getFather(x);
                if (x1 != null) {
                    x = x1;
                    continue;
                } else {
                    System.out.println("已经到最顶层");
                }
            } else {
                try {
                    x = childrens.get(Integer.valueOf(s));
                } catch(Exception e) {
                    System.out.println("请重新选择:");
                }
            }
        }
        //run(childrens.get(Integer.valueOf(s)));递归也可以,循环也可以
    }
    
    public static void main(String[] args) {
        MyMenu a = new MyMenu();
        a.add("世界", "亚洲");
        a.add("世界", "美洲");
        a.add("世界", "欧洲");
        a.add("亚洲", "中国");
        a.add("美洲", "美国");
        a.add("亚洲", "日本");
        a.add("中国", "河北");
        a.add("中国", "河南");
        a.add("中国", "广东");
        a.add("中国", "浙江");
        
        a.run("世界");
    }
}

运行，可以通过输入来操作菜单

------------
- 世界
  0,亚洲
  1,美洲
  2,欧洲
  u,返回上一级
------------
请选择:
1
------------
- 美洲
  0,美国
  u,返回上一级
------------
请选择:
0
你选择了:美国
------------
- 美国
  u,返回上一级
------------
请选择:
u
------------
- 美洲
  0,美国
  u,返回上一级
------------
请选择:
u
------------
- 世界
  0,亚洲
  1,美洲
  2,欧洲
  u,返回上一级
------------
请选择:
0
------------
- 亚洲
  0,中国
  1,日本
  u,返回上一级
------------
请选择:
0
------------
- 中国
  0,河北
  1,河南
  2,广东
  3,浙江
  u,返回上一级
------------
请选择:
1
你选择了:河南
------------
- 河南
  u,返回上一级
------------
请选择: