在网站开发中经常遇到级联数据的展示，比如选择城市的时候弹出的省市县选择界面。很多前端制作人员习惯于从JSON中而不是从数据库中获取省市县数据。那么在选择了省市县中的某一个城市 ，存储到数据库中需要存储所选城市的代码。所以需要一个能将JSON数据（一般存储在javascript脚本中)结构全部导入到数据库中的功能。

       JSON的特点是支持层级结构、支持数组表示的对象 。下面的示例介绍如何将JSON的省市县数据保存到数据库中，实现原理非常简单，就是利用JSON的java工具包API，将层次结构的JSON对象数组通过递归的方式首选转换为Java对象数组，然后保存到数据库中。

      实现步骤是：

    （一）首先定义一个JsonItem实体类：

package org.openjweb.core.entity;

public class JsonItem
{
 private String sub_id;
 private String sub_name;
 private JsonItem[] items;
 
 public JsonItem[] getItems() {
  return items;
 }
 public void setItems(JsonItem[] items) {
  this.items = items;
 }
 public String getSub_id() {
  return sub_id;
 }
 public void setSub_id(String sub_id) {
  this.sub_id = sub_id;
 }
 public String getSub_name() {
  return sub_name;
 }
 public void setSub_name(String sub_name) {
  this.sub_name = sub_name;
 }
 
}

（二）定义一个工具类，在工具类中读取Json数据文件，并进行递归调用 ：

 public static String importJson(String fullFileName,String jsonType,String encoding,HttpServletRequest request) throws Exception
 {
  //Json转换为实体类参考:http://www.cnblogs.com/hoojo/archive/2011/04/21/2023805.html
  String sReturn = "";
  String jsonData = "";
  try
  {
   jsonData = FileUtil.getTextFileContent(fullFileName, encoding);
  }
  catch(Exception ex)
  {
   sReturn ="读Json文件失败!";
  }
  
  //获取rootId
  //logger.info("");
  jsonData = jsonData.replace("\"items\":\"\"", ""); //去掉空的 items
  String parentId = jsonData.substring(jsonData.indexOf("\"id\":")+5);
  parentId = parentId.substring(0,parentId.indexOf(",")).trim();
  parentId = parentId.replace("\"", "");
  logger.info("root id=="+parentId);
  String parentName = jsonData.substring(jsonData.indexOf("\"name\":")+7);
  parentName = parentName.substring(0,parentName.indexOf(",")).trim();
  parentName = parentName.replace("\"", "");
  logger.info("root Name=="+parentName);
  String rootData = jsonData.substring(jsonData.indexOf("\"items\":")+8,jsonData.lastIndexOf("}"));
  rootData = jsonData.substring(jsonData.indexOf("[")+1,jsonData.lastIndexOf("]"));
  //不同json的id,name表示不一样，统一换成sub_id,subname以便与JsonItem的类属性匹配
        //  替换后方便统一处理
  rootData = rootData.replace("city_id", "sub_id");
  rootData = rootData.replace("sub_city", "sub_name");
  rootData = rootData.replace("city", "sub_name");
  
  rootData = rootData.replace("sub_txt", "sub_name");
  
  rootData = rootData.replace("sub_industry", "sub_name");
  rootData = rootData.replace("industry_id", "sub_id");
  rootData = rootData.replace("industry", "sub_name");
  
  rootData = rootData.replace("sub_profession", "sub_name");
  rootData = rootData.replace("profession_id", "sub_id");
  rootData = rootData.replace("profession", "sub_name");
  
  
  
  //将rootData转换为array
  rootData =  "[" + rootData + "]";
  try
  {
   FileUtil.str2file(rootData, "d:/jsonData.txt", "utf-8");//存储到磁盘检查字符串转换是否正确
  }
  catch(Exception ex)
  {
   
  }
  JSONArray jsonArray = JSONArray.fromObject(rootData);
  Object[] os = jsonArray.toArray();
  JsonItem[] items = (JsonItem[]) JSONArray.toArray(jsonArray, JsonItem.class);
        
        saveJsonEnt(jsonType,parentId,parentName,"-1",new Long(1));
       
  dealJson(items,parentId,jsonType,new Long(1));
        return sReturn ;
 }
 
 private static void saveJsonEnt (String jsonType,String jsonId,String jsonName,String parentId,Long levelId) throws Exception
 {
  logger.info(jsonType+"/"+jsonId+"/"+jsonName+"/"+parentId+"/"+String.valueOf(levelId));
  CommJsonData ent = new CommJsonData();
  ent.setJsonType(jsonType);
  ent.setJsonCode(jsonId);
  ent.setJsonName(jsonName);
  ent.setRowId(StringUtil.getUUID());
  ent.setParentCode(parentId);
  ent.setLevelId(levelId);
  IDBSupportService service = (IDBSupportService)ServiceLocator.getBean("IDBSupportService3");
  service.saveOrUpdate(ent);
  
 }
 
  private static String dealJson(JsonItem[] jsonItem,String parentId,String jsonType,Long level)
 {
  String sReturn = "";
  if(jsonItem!=null&&jsonItem.length>0)
  {
   for(int i=0;i<jsonItem.length;i++)
   {
    JsonItem ent = jsonItem[i];
    //System.out.println(ent.getSub_id());
    //System.out.println(ent.getSub_name());
       try
       {
        saveJsonEnt(jsonType,ent.getSub_id(),ent.getSub_name(),parentId,level+1);
       }
       catch(Exception ex)
       {
        ex.printStackTrace();
       }
    if(ent.getItems()!=null)
    {
     //System.out.println("子项数:"+ent.getItems().length);
     dealJson(ent.getItems(),ent.getSub_id(),jsonType,level+1);
    }
    else
    {
     //System.out.println("没有子项!");
    }
   }
  }
  //此函数
  return sReturn ;
  
 
 } 

示例数据（部分）：

{
  "name": "全国",
  "id": "0000000000",
  "description": "崇德易城市数据",
  "modified": "2012年08月",
  "copyright": "http://www.chongdeyi.com/",
  "items": [
  {
   "city": "北京市",
   "city_id": "1001000000",
   "items": [
   {
    "sub_city":"东城区",
    "sub_id":"2001001000"
   },
   {
    "sub_city":"西城区",
    "sub_id":"2001002000"
   },
   {
    "sub_city":"朝阳区",
    "sub_id":"2001006000"
   },
   {
    "sub_city":"丰台区",
    "sub_id":"2001007000"
   },
   {
    "sub_city":"石景山区",
    "sub_id":"2001008000"
   },
   {
    "sub_city":"海淀区",
    "sub_id":"2001009000"
   },
   {
    "sub_city":"门头沟区",
    "sub_id":"2001010000"
   },
   {
    "sub_city":"房山区",
    "sub_id":"2001011000"
   },
   {
    "sub_city":"通州区",
    "sub_id":"2001012000"
   },
   {
    "sub_city":"顺义区",
    "sub_id":"2001013000"
   },
   {
    "sub_city":"昌平区",
    "sub_id":"2001014000"
   },
   {
    "sub_city":"大兴区",
    "sub_id":"2001015000"
   },
   {
    "sub_city":"怀柔区",
    "sub_id":"2001016000"
   },
   {
    "sub_city":"平谷区",
    "sub_id":"2001017000"
   },
   {
    "sub_city":"延庆县",
    "sub_id":"2001018000"
   },
   {
    "sub_city":"密云县",
    "sub_id":"2001019000"
   }]
  },{
   "city": "天津市",
   "city_id": "1002000000",
   "items": [
   {
    "sub_city":"和平区",
    "sub_id":"2002001000"
   },

。。。

树的定义：n（n>=0）个节点的有限集。

1. n=0时称为空树。
2. n!=0时为非空树，有且仅有一个特定的节点——根；n>1时，其它节点可以分为m（m>0）个互不相交的有限集T1~Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

树的一些基本术语：

1. 树的结点：由一个数据元素和若干个指向其子树的分支组成。
2. 结点的度：结点所拥有的子树的个数（即分支数）称为该结点的度。
3. 叶子结点：度为0的结点称为叶子结点，或者称为终端结点。
4. 分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点由叶子结点和分支结点组成。
5. 孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子；这个结点称为它孩子结点的双亲；具有同一个双亲的孩子结点互称为兄弟。
6. 路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（i为1~k，不等于k的值），就把n1,n2,…,nk称为一条由n1至nk的路径。路径长度是指路径上经过的边的数量，所以这条路径的长度是k-1。
7. 祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
8. 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。
9. 树的深度（高度）：树中所有结点中的最大层数称为树的深度。
10. 树的度：树中各结点中度的最大值称为该树的度。
11. 有序树、无序树：如果一棵树中结点的各子树从左到右都是有次序的，不能交换的，称这棵树为有序树；反之为无序树。
12. 森林：ｍ（ｍ＞＝０）棵互不相交的树的集合。
13. 同构：对于两棵树，若通过对各结点适当重命名，就可以使这两棵树完全相等（结点对应相等，结点关系也相等），称这两棵树同构。
14. 层序编号：将书中结点按照从上层到下层、同层从左到右的次序依次给它们编号１开始的自然数。

线性结构和树结构的比较：

树的存储结构：
双亲表示法：
（用一组连续空间来存储树的结点）
在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
结点的结构如下：

下面演示一下双亲表示法：约定根结点的指针域设为-1；

这个方法通过结点只要花O(1)的时间就可以访问到此结点双亲结点，但是要找到其孩子结点却需要遍历整棵树。需要改进；
改进版一：增加最左孩子（长子）结点指针域；如下：

改进版二：增加右兄弟结点指针域；如下：

可以根据需求来进行改进，灵活的设计存储结构。

多重链表表示法：
（用多重链表来实现）
每个结点有多个指针，其中每个指针指向一棵子树的根结点，这种方法叫多重链表表示法。
方案一：
指针域的个数等于树的度；结构如下：

举例上图的树的度为3，所以指针域的个数为3，方法的实现如下：

解释：对于树中各结点的度相差很大时，是很浪费空间的；如果各结点的度相差很小时，空间是被充分利用的。
根据按需分配空间的想法，于是我们有了第二组方案。
方案二：
每个结点指针域的个数等于该结点的度，通过设置一个位置来存储结点指针域的个数；结构如下：

于是乎上述图可以画出该方案的实现：

解释：该方法客服了空间上的浪费，但是由于链表的结构不同以及需要维护结点的度的数值，因此在运算上就是在时间上有所消耗。

孩子表示法：
利用数组来存放数组的结点，利用单链表来存放结点的孩子结点。
演示上述图例结构如下：

解释：
表头数组的的结构；data是数据域，存储结点的数据信息；firstchild是头指针，存储该结点的孩子链表的头指针。
孩子链表的结构：child是数据域，存储某个结点在表头数组中的下标；next是指针域，用来存储指向某结点的下一个孩子结点的指针。

改进版：孩子双亲表示法：
在表头数组中增加一个parent域，用来保存指向双亲结点的指针。

孩子兄弟表示法：
结构如下：

解释：data是数据域；firstchild为指针域，存储该结点的长子的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址。
这样上述图中所述树的实现如下：

如果想找到双亲，可以增加一个双亲指针。

后续继续讲解二叉树。