Tree Structure

1 Usages of Tree Structure

Tree structure is one of basic data structure which presents one type of nonlinear logic.

Tree structure can describe relationships in hierarchy and membership accurately.

2 Features of Tree Structure

2.1 Concepts

Information can be organized as a tree:

1. "Node" stores a piece of information.
2. "Children Nodes": In lower level and belong to the node. Also called "Branches".
3. One node can have multiple children.
4. "Parent Node": In higher level and owns the node.
5. One node can have only one "Parent".
6. "Descendant Nodes": All lower nodes extended recursively from children.
7. "Ancestral Nodes": All higher nodes extended recursively from parent.
8. "Sibling Nodes": Nodes which have same parent node.
9. "Root Node": In top level and be ancestry of all other nodes.
10. "Leaf Nodes": Have not children.
11. "Hierarchy Number": The chain of sequence numbers from root to the node.
12. "Node Name": String to describe the node.
13. "Chain Name": The chain of node names from root to the node.
14. "Steady Node Name": During the tree is being watched or handled, node name is not changed.
15. "Static Tree": During the tree is being watched or handled, tree structure is not changed, that is no node is deleted, added, or moved.
16. "Dynamic Tree": During the tree is being watched or handled, tree structure is changed, that is some nodes are deleted, added, or moved.

2.2 Identify and Locate Nodes

To locate specific node in the tree correctly:

• An unique identify should be assigned to each node. That is, identifies of all nodes are different.
• The identify of node should be steady. That is, it should not change during the tree is being watched or handled.

2.3 Ordered Tree

"Ordered Tree" has following features:

• The order of each node's children are steady. That is, the sequence numbers of children are always same for each query when children are not changed.
• Hierarchy number can identify each node uniquely.
• Hierarchy number of same node may change in dynamic tree.

So hierarchy number can be used to locate a node only for static ordered tree.

2.4 Tree with Unique Chain Names

"Tree with unique Chain Names" has following features:

• Names of each node's children are not duplicated.
• Names of different nodes' children can be duplicated.
• Chain names can identify each node uniquely.
• When nodes' names are steady, chain names do not change in dynamic tree.

So chain names can be used to locate nodes for dynamic or static tree when it is "unique chain names".

3 Implement Tree Structure

In MyBox, attributes of tree node include: ID, Title(Node Name), Order_number, Modify_Time, ID of parent node.
And each type of trees has its special data fields.

3.1 ID of Node

ID of node is generated and increased automactically, and used to identify and locate each node uniquely. It is absolutely steady attribute:

• Generated by database automactically and never updated once the value is set.
• IDs of all nodes are different.
• Does not change when tree structure is changed.
• Does not change when other attributes of node are changed.

IDs of nodes have following disadvantages:

• Unfit for person to remember and recognize nodes, and unfit for operations of interfaces.
• Tightly coupled with application environment, and may cause conflicts and incompatibilities when import data.

3.2 Title of Node

Title of node is string to describe node:

• Should not be null.
• Titles of children can be duplicated.
• Does not change when tree structure is changed.
• Does not change when other attributes of node are changed.

Because titles of children can be duplicated, if treat node title as node name, then chain name may not be unique and can not locate node correctly with it.

Titles of nodes have following advantages:

• Fit for person to remember and recognize nodes, and fit for operations of interfaces.
• Do not coupled with application environment, and fit to import data.

3.3 Value of Node

Value of node is stored as large text of length 2G.

In MyBox, objects handled by following functions are stored and managed in tree:

3.4 Order Number of Node

Order number of node is for sorting sibling nodes, which have same parent node. It can be negative or with decimal point.

MyBox provides function to trim order numbers: reassign order numbers of sibling nodes as values increased in step value 1.

3.5 Tags of Node

• Tags are extra attributes assigned to node, and customized by user.
• Purpose of tags is to categorize, query, and locate nodes with keywords.
• One node can have multiple tags.
• One tag can belong to multiple nodes.

4 Manage Tree Structure

4.1 Define Tags

User can define different sets of tags for each type of trees.

4.2 Examples

MyBox provides examples for functions in tree.
Click menu item "Examples" to import example data of the function.

Examples' tree view of of each function tree can be viewed in MyBox documents list.

4.3 Export

Select one node, and export its tree with this node as root:

• Format can be chosen: Tree XML, Tree JSON, Tree Html, List JSON, List XML, List CSV, List Html, Html frameset.
• Options to export node's id, hierarchy number, modified time, order number, parent id, tags, and data.
• Style of exported html can be set.
• MyBox uses iterators and stacks to write records while reading rows, so the amount of exported data is not limited by memory usage

4.4 Import

Tree information can be imported in batch:

• Select multiple files which hold tree information as source.
• Exported files should be XML in special formats, which are same as Tree XML exported by MyBox.
• When import nodes, "id", "parentid", "update_time" are generated automatically, rather than picked from files.
• When node of same title under same parent exists, options: "Change attributes", "Create child of duplicated name", and "Skip".
• Example is provided.

Tree XML can be used to locate tree nodes in a file:

• Tree XML can store tree structure accurately.
• MyBox uses SAX and stacks to parse Tree XML, so the amount of imported data is not limited by memory usage

Can not locate node by ID when import nodes, because ID is an attribute which couples application environment tightly:

• After node is exported, it can not keep pace with the application environment.
• When node is imported, its ID may be missed or conflicted in the imported environment.
• The hierarchy of imported nodes can not be defined by their IDs because the IDs may be incompatible with the imported environment.

4.5 Add/Delete/Modify Nodes

Select one or multiple nodes, and:

• Add child node.
• "Delete the node and its descendant", "Delete the node's descendant".
• Copy nodes:
  • Choices: "Only copy node", "Copy node's descendant", "Copy node and its descendant", "Copy node and its children", and "Copy node's children"
  • Select the target node to copy into.
  • Target node should not be source node nor its descendant.
• Move nodes:
  • Select the target node to move into.
  • Target node should not be source node nor its descendant.
• Edit Node:
  • Change title and order_number.
  • Select node's parent。
  • Modify values of data fields.
• Selected node can be executed directly if the data is executable.

4.6 View Nodes

Select one node:

• View node's information in popped window.
• Copy node's title into system clipboard.
• Fold node, or node and its descendant.
• Unfold node, or node and its descendant.

4.7 Menu

• Click buttons in interface to view menus.
• Right click the tree to pop the menu.
• Actions can be chosen for double clicking and right clicking against the tree.