First, the background and significance of the research
In the field of Web application development, JavaScript tree controls based on Ajax technology have been widely used to present hierarchical data items on Html pages.
At present, common JavaScript frameworks and component libraries in the market contain their own tree controls, such as jQuery, Ext JS, etc., as well as some independent tree controls, such as dhtmlxTree, etc., these tree controls perfectly solve the display problem of hierarchical data. Display can not be separated from data, tree controls mainly use Ajax technology to obtain data sources from the server, data source formats mainly include JSON, XML, and these hierarchical data are generally stored in the database.
The “infinite tree structure”, as the name implies, has no restrictions on levels. Its data is usually derived from the infinite level data in the database. The storage table of this data usually includes the two fields ID and parentId to represent the hierarchical relationship between the data.
Now the problem is how to establish a relationship between tree controls and hierarchical data, since the data source is a string in the form of JSON or XML to organize hierarchical data, and the hierarchical data is stored in the tables of the database. In other words, How to convert the hierarchical data in the database into a string in JSON or XML format of the corresponding hierarchical structure, which is returned to the client’s JavaScript tree control? That’s the key technical problem we have to solve.
This article will take the well-known Ext JS framework on the market as an example to describe how to implement the infinite tree structure, which is also applicable to other similar JavaScript tree controls.
The Ext JS framework is one of the outstanding frameworks in rich client development. Among Ext’s UI controls, the tree control is undoubtedly one of the most commonly used controls to implement tree-structured views. TreeNode is used to implement the static tree structure, while AsyncTreeNode is used to implement the dynamic asynchronous loading of the tree structure. The latter is most commonly used. It dynamically generates the tree structure nodes by receiving the DATA in JSON format returned by the server.
There are two ways of thinking about dynamic spanning trees:
- One is to generate all tree nodes at once.
- The other is to load the nodes of the tree level by level (using Ajax, each time a node is clicked, the next level of the node is queried).
For a tree node with a large amount of data, step by step loading is a more appropriate choice, but for a tree node with a small amount of data, generating all nodes at one time should be the most reasonable scheme. In practical application development, there is generally no scenario with particularly large data volume, so generating all tree nodes at one time is the key technical point of our research, which is also the key technical problem to be solved in this paper.
In this paper, the application system based on Ext JS, for example, tell how to infinite levels of hierarchical data in the database of disposable generated in the interface all tree nodes (for example, in the interface in tree way one-time showing all branches of Banks), at the same time for each level of nodes sorted by a certain attributes and rules, show the orderly tree structure.
Solving the problem of constructing an infinite tree structure at one time can expand more application scenarios. For example, TreeGrid can generate a tree table at one time, complete pagination of the tree table, and complete sorting of the table columns. Or you can use the ideas in this article to extend other, more complex application scenarios.
Let’s take a look at two legends for an intuitive understanding:
FIG. 1. Tree structure of bank branches
FIG. 2, tree structure table
Second, detailed design scheme
Let’s start with two code snippets:
File 1, branchtree.html (Ext tree control page)
Ext.onReady(
function(){
var tree = new Ext.tree.TreePanel({
height: 300.width: 400.animate:true.enableDD:true.containerScroll: true.rootVisible: false.frame: true.// getbranch. do requests that the server return a multilevel tree JSON string
loader: new Ext.tree.TreeLoader({dataUrl:'getBranch.do'}),
root : new Ext.tree.AsyncTreeNode({id:'0'.text:'Root'})}); tree.expandAll(); });Copy the codeFile 2, branchTreeson.jsp (receives the getBranbranch. Do request and returns a multi-level tree JSON string)
The < %// Read the hierarchical data of the bank branch
List result = DataAccess.getBankInfoList();
// Convert hierarchical data into multi-fork tree objects (the implementation of this data structure is described in more detail below)Node root = ExtTreeHelper.createExtTree(result); %> [<%=root.toString()%> <!-- returns the response data as JSON, from which ext.tree.treeloader will generate a tree structure -->]Copy the codeThe above two program files are necessary to generate an infinite tree structure at one time. The most critical part is how to generate an infinite tree structure JSON string, which is returned to the client Ext tree control. For the bank branch, return a JSON string similar to the following:
{
id: '100000'.text: Langfang Bank Head Office.children: [{id: '110000'.text: 'Langfang Branch'.children: [{id: '113000'.text: Langfang Bank Development Zone Sub-branch.leaf: true
},
{
id: '112000'.text: Langfang Bank Jiefang Road Sub-branch.children: [{id: '112200'.text: Langfang Bank 3rd Street Branch.leaf: true
},
{
id: '112100'.text: Guangyang Road Branch of Langfang Bank.leaf: true}]}, {id: '111000'.text: Langfang Bank Jinguangdao Branch.leaf: true}]}]}Copy the codeYou also need to sort the nodes at each level of the tree by some attribute, such as branch number, to show an ordered tree structure.
The problem can now be summarized as:
1. Convert the hierarchical data in the database into a string in JSON format with a multi-level tree structure
2. Sort nodes at each level of the tree by some attribute (such as branch number)
Here’s how to solve the problem:
In the data structure course, we all learned about trees. The infinite tree structure can be abstracted into a multi-fork tree structure, that is, a tree structure with multiple sub-nodes under each node. First, we need to convert the hierarchical data in the database into an object tree with multi-fork tree structure, that is, to construct a multi-fork tree.
With the data structure, we also need to implement the corresponding algorithm. We need to implement two algorithms:
1. Horizontal sorting algorithm of sibling nodes, sorting all direct child nodes subordinate to the same parent node according to a node attribute and rule, keeping sibling nodes in horizontal order;
2. Sequence traversal algorithm first, recursively print infinite level JSON string.
It can be summarized into three steps:
1. Construct disordered multi-fork tree structure
2. Implement the horizontal sorting method of sibling nodes
3. Implement the sequential traversal method and print out the JSON string
As shown in the figure:
Three, source code implementation (Java version)
To realize such a tree, we need to design two classes: MultipleTree and Node. You also need a comparator class (NodeIDComparator) to sort; For demonstration purposes, we also need to construct some fake hierarchical data, so we also need to build a fake data class (VirtualDataGenerator). After copying the following code, we can run the test directly:
package test;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Collections;
/** ** multi-fork tree */
public class MultipleTree {
public static void main(String[] args) {
// Read the list of hierarchical data result sets
List dataList = VirtualDataGenerator.getVirtualResult();
// Node list (mapping table for temporary storage node objects)
HashMap nodeList = new HashMap();
/ / the root node
Node root = null;
// Store the result set into the mapping table (we will use the mapping table to construct the multi-fork tree later)
for (Iterator it = dataList.iterator(); it.hasNext();) {
Map dataRecord = (Map) it.next();
Node node = new Node();
node.id = (String) dataRecord.get("id");
node.text = (String) dataRecord.get("text");
node.parentId = (String) dataRecord.get("parentId");
nodeList.put(node.id, node);
}
// Construct an unordered multi-fork tree
Set entrySet = nodeList.entrySet();
for (Iterator it = entrySet.iterator(); it.hasNext();) {
Node node = (Node) ((Map.Entry) it.next()).getValue();
if (node.parentId == null || node.parentId.equals("")) {
root = node;
} else{ ((Node) nodeList.get(node.parentId)).addChild(node); }}// Outputs an unordered tree structure JSON string
System.out.println(root);
// Sort the tree horizontally
root.sortChildren();
// Outputs the ordered tree structure of the JSON string
System.out.println(root);
// The program output is as follows:
//
/ / unordered tree structure (formatted as a result, can use JSON formatting tool to view, such as http://jsonviewer.stack.hu/ online viewer) :
// {
// id : '100000',
// text: 'langfang head office ',
// children : [
/ / {
// id : '110000',
// text: 'langfang branch ',
// children : [
/ / {
// id : '113000',
// text: 'langfang Bank Development Zone Sub-branch ',
// leaf : true
/ /},
/ / {
// id : '111000',
// text: 'langfang Bank Jinguangdao Branch ',
// leaf : true
/ /},
/ / {
// id : '112000',
// text: 'langfang bank Jiefang Road Branch ',
// children : [
/ / {
// id : '112200',
// text: 'langfang bank 3 main Street branch ',
// leaf : true
/ /},
/ / {
// id : '112100',
// text: 'langfang Bank guangyang Road Branch ',
// leaf : true
/ /}
/ /]
/ /}
/ /]
/ /}
/ /]
/ /}
// Ordered tree structure (formatted result) :
// {
// id : '100000',
// text: 'langfang head office ',
// children : [
/ / {
// id : '110000',
// text: 'langfang branch ',
// children : [
/ / {
// id : '111000',
// text: 'langfang Bank Jinguangdao Branch ',
// leaf : true
/ /},
/ / {
// id : '112000',
// text: 'langfang bank Jiefang Road Branch ',
// children : [
/ / {
// id : '112100',
// text: 'langfang Bank guangyang Road Branch ',
// leaf : true
/ /},
/ / {
// id : '112200',
// text: 'langfang bank 3 main Street branch ',
// leaf : true
/ /}
/ /]
/ /},
/ / {
// id : '113000',
// text: 'langfang Bank Development Zone Sub-branch ',
// leaf : true
/ /}
/ /]
/ /}
/ /]
/ /}}}/** * Node class */
class Node {
/** * Node id */
public String id;
/** * Node content */
public String text;
/** * Parent node number */
public String parentId;
/** * Child node list */
private List children = new ArrayList();
// Add the child node
public void addChild(Node node) {
children.add(node);
}
// Sequence traversal, concatenate JSON string
public String toString(a) {
String result = "{" + "id : '" + id + "'" + ", text : '" + text + "'";
if(children.size() ! =0) {
result += ", children : [";
for (int i = 0; i < children.size(); i++) {
result += ((Node) children.get(i)).toString() + ",";
}
result = result.substring(0, result.length() - 1);
result += "]";
} else {
result += ", leaf : true";
}
return result + "}";
}
// The sibling nodes are horizontally sorted
public void sortChildren(a) {
if(children.size() ! =0) {
// Sort the nodes of this layer (you can pass different comparators according to different sort attributes, in this case, pass ID comparator)
Collections.sort(children, new NodeIDComparator());
// Sort the nodes at the next level from each node
for (int i = 0; i < children.size(); i++) { ((Node) children.get(i)).sortChildren(); }}}}/** * node comparator */
class NodeIDComparator implements Comparator {
// Compare by node number
public int compare(Object o1, Object o2) {
int j1 = Integer.parseInt(((Node) o1).id);
int j2 = Integer.parseInt(((Node) o2).id);
return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1)); }}/** * Construct virtual hierarchical data */
class VirtualDataGenerator {
// Construct an unordered list of result sets. In practice, the data should be retrieved from the database;
public static List getVirtualResult(a) {
List dataList = new ArrayList();
HashMap dataRecord1 = new HashMap();
dataRecord1.put("id"."112000");
dataRecord1.put("text".Jiefang Road Branch of Langfang Bank);
dataRecord1.put("parentId"."110000");
HashMap dataRecord2 = new HashMap();
dataRecord2.put("id"."112200");
dataRecord2.put("text"."Langfang Bank Sanjie Branch");
dataRecord2.put("parentId"."112000");
HashMap dataRecord3 = new HashMap();
dataRecord3.put("id"."112100");
dataRecord3.put("text".Guangyang Road Branch of Langfang Bank);
dataRecord3.put("parentId"."112000");
HashMap dataRecord4 = new HashMap();
dataRecord4.put("id"."113000");
dataRecord4.put("text".Langfang Bank Development Zone Branch);
dataRecord4.put("parentId"."110000");
HashMap dataRecord5 = new HashMap();
dataRecord5.put("id"."100000");
dataRecord5.put("text".Langfang Bank Head Office);
dataRecord5.put("parentId"."");
HashMap dataRecord6 = new HashMap();
dataRecord6.put("id"."110000");
dataRecord6.put("text".Langfang Branch);
dataRecord6.put("parentId"."100000");
HashMap dataRecord7 = new HashMap();
dataRecord7.put("id"."111000");
dataRecord7.put("text".Langfang Bank Jinguangdao Branch);
dataRecord7.put("parentId"."110000");
dataList.add(dataRecord1);
dataList.add(dataRecord2);
dataList.add(dataRecord3);
dataList.add(dataRecord4);
dataList.add(dataRecord5);
dataList.add(dataRecord6);
dataList.add(dataRecord7);
returndataList; }}Copy the codeOk, with the above code, you can achieve horizontal sorting and sequential traversal of the sibling nodes of the multi-tree, and achieve the purpose of converting hierarchical data into an ordered infinite tree structure JSON string.
In a real project, you could incorporate the code above, or extend it:
1. Sort a hierarchy (for example, sort only the nodes of the first tier, or sort only all the children of a parent node)
2. When traversing the output tree structure, judgment conditions can be added to filter out some nodes
3. Implement the node deletion function
4. Add a reference to the parent node in the node class to calculate the level of a node
5. The same effect can be achieved by using this algorithm in database application system that does not support hierarchical query
Iv. Thinking and summarizing
This article focuses on how to construct an ordered infinite tree structure OF JSON strings, generating the tree structure at one time, rather than using Ajax to repeatedly send requests to the server and load tree nodes level by level.
If you can construct an infinite level JSON string, you can construct an infinite level XML string along the same lines, or a hierarchical UL-Li combination (using UL-Li to show tree structures), or a hierarchical TABLE (using TABLE to show tree structures).
As follows:
(1) XML hierarchy
<nodeGroup id="100000" name=Langfang Bank Head Office>
<nodeGroup id="110000" name=Langfang Branch>
<node id="113000" name=Langfang Bank Development Zone Branch>
</node>
<node id="111000" name=Langfang Bank Jinguangdao Branch>
</node>
<nodeGroup id="112000" name=Jiefang Road Branch of Langfang Bank>
<node id="112200" name="Langfang Bank Sanjie Branch">
</node>
<node id="112100" name=Guangyang Road Branch of Langfang Bank>
</node>
</nodeGroup>
</nodeGroup>
</nodeGroup>
Copy the code(2) UL-LI hierarchy
<ul>
<li>Langfang Bank Head Office</li>
<ul>
<li>Langfang branch</li>
<ul>
<li>Langfang Bank Development Zone Branch</li>
<li>Langfang Bank Jiefang Road Branch</li>
<ul>
<li>Langfang Bank Sanjie Branch</li>
<li>Langfang Bank Guang Yang Road Branch</li>
</ul>
<li>Langfang Bank Jinguangdao Branch</li>
</ul>
</ul>
</ul>
Copy the code(3) TABLE hierarchy
<table>
<tr><td>Langfang Bank Head Office</td></tr>
<tr><td> Langfang branch</td></tr>
<tr><td> Langfang Bank Development Zone Branch</td></tr>
<tr><td> Langfang Bank Jiefang Road Branch</td></tr>
<tr><td> Langfang Bank Sanjie Branch</td></tr>
<tr><td> Langfang Bank Guang Yang Road Branch</td></tr>
<tr><td> Langfang Bank Jinguangdao Branch</td></tr>
</table>
Copy the codeAlso useful for TreeGrid tree tables:
1. Construct a tree table at one time to achieve hierarchical display of data
2, by replacing the comparator, to achieve the full sort of different table columns (full sort refers to the sort of data on all pages, rather than just the data of the previous page; The sorting rules are similar to those in Oracle database, that is, brother nodes are horizontally sorted.
3. Complete pagination of the tree table (only a fixed number of first-layer nodes is taken during each pagination, and then the toString method is called to show the hierarchical data of the complete number of entries, that is, the number of entries on each page is not fixed, but it must be a complete tree structure)