motivation:
I initially remembered to build a binary tree because I needed to make a company structure chart. In the past, I used to draw a picture directly using image software. It looks great, but every time there is a change, you need to draw a new one. On the other hand, the display and layout of lines on web pages are quite limited. It is very difficult to type and position based on dynamically generated data, and it is also unsatisfactory in terms of aesthetics. After making various attempts, I decided to use XML+XSL for data calculation; use VML to beautify lines, and use JAVASCRIPT to locate objects.
Material:
XML volume structure tree diagram
There are 2 files: and
Effect:
Browse here
explain:
Binary Tree Ideas (1)
<html xmlns:v="urn:schemas-microsoft-com:vml">
<STYLE>
v\:* { BEHAVIOR: url(#default#VML) }
</STYLE>
<v:group name="group1" coordsize = "100,100">
…
</v:group>
The above are the basic formats of VML, so I won't explain them in detail.
XML is a tree structure, and we need to read each data to this
The XML data tree is traversed. Recursive operations are one of the advantages of XSL.
I've failed to perform traversal operations using other methods
Decided to use XSL.
<FlowRoot>
<vcTitle>Binary Tree-Structure Chart</vcTitle>
<Author>Sailflying</Author>
<Email>sailflying@</Email>
<FlowNode>
<iProcess>1</iProcess>
<vcCourse>First Node</vcCourse>
<iNextYes>
<FlowNode>
<iProcess>2</iProcess>
<vcCourse>Second Node</vcCourse>
<iNextYes>…</iNextYes>
<iNextNo>…</iNextNo>
</FlowNode>
</iNextYes>
<iNextNo>
<FlowNode>
<iProcess>3</iProcess>
<vcCourse>Third Node</vcCourse>
<iNextYes>…</iNextYes>
<iNextNo>…</iNextNo>
</FlowNode>
</iNextNo>
</FlowNode>
</FlowRoot>
Logically, it is very simple. There are two child nodes (2, 3) under the current node (1).
Just position node 2 and node 3 at the bottom left and bottom right of node 1.
Here I used green and red to connect the connection lines of the left and right nodes to facilitate display.
We mentioned the recursive function of XSL earlier, in order to see each detailed
To display the steps, you just need to imitate the following code and add an alert statement.
<xsl:template match="FlowNode">
…
<SCRIPT language="JavaScript1.2">
…
alert('Show step by step');
…
</SCRIPT>
…
</xsl:template>
After reading the slow motion above, can you understand my ideas?
Binary Tree Ideas (2)
My idea is very simple:
(1) Read the data of the current node and use VML to generate a new object.
Assign initial values to the object (such as name, id, style, etc.)
(2) Use script control to locate the current object
(3) Add an arrow and line between the current node and its father node.
(4) Continue to find the child node of the current node and keep the loop positioning until the end.
That is, all nodes have been traversed and a tree has been generated.
<xsl:template match="FlowNode">
…
<xsl:apply-templates />
…
</xsl:template>
<xsl:template match="iNextYes">
<xsl:apply-templates select="./FlowNode" />
</xsl:template>
<xsl:template match="iNextNo">
<xsl:apply-templates select="./FlowNode" />
</xsl:template>
The entire recursion process is completed by the above three modules (templates).
When the first template matches the template of each child node in the current node,
The next two templates are called; and the next two templates are being executed in detail
When the first template is called, this is equivalent to a recursive function.
grammar:
To match the templates of each child node in the current node in sequence, this element should be used
The basic form of ci <xsl:apply-templates />.
Otherwise, the matching node is determined by the value of the XPath expression in the select parameter.
As shown in <xsl:apply-templates select="./FlowNode" />
The functions of (1) and (2) are to return the string value of the expression given by the select parameter.
Their search criteria are the same, so the returned values are the same.
It’s just that the use occasions are different, their writing styles are also different.
（1） <xsl:value-of select="./iProcess/text()" />
（2） {./iProcess/text()}
Some variables are defined here, and the positioning of nodes is to call the calculation formula based on these variables.
root_left //The left margin of the root = all leaves allocated width (y*10) + all leaves width (y*50) + the base value of the left margin (10)
root_top //The upper margin of the root = the basic value of the upper margin (10)
objOval //The current object is an object
objOval_iProcess //Step value of the current object
objParentOval //The parent node of the current object is an object
objParentOval_iProcess //Step value of the current object parent node
objParent_name //The name of the current object parent node
Leaf_left //The number of leaves on the left among all child nodes of the current object
Leaf_right //The number of right leaves in all child nodes of the current object
Leaf_sum //The number of leaves in all child nodes of the current object
Leaf: means that the current node has no child nodes
The positioning formula of nodes:
(1) The current node is the root node
//The location of the root
=parseInt(root_left);
=parseInt(root_top);
//The function of the parseInt() function is to take integer values, if not, it is NAN
//The function of the isNaN() function is to determine whether parseInt gets an integer
(2) The current node is the left child node of the parent node
1) The judgment condition is: The name of the current object parent node ='iNextYes'
…
2) If the right cotyledon leaves exist, the formula is:
The left of the current node = the left of the parent node - the total width of the child leaves on the right of the current node - the width of the current node
3) If there is no right cotyledon leaf but the left cotyledon leaf, the formula is:
The left of the current node = the left of the parent node - the total width of the child leaves on the left of the current node
4) If the current node itself is a leaf, the formula is:
The left of the current node = the left of the parent node - the width of the current node
…
(3) The current node is the child node on the right of the parent node
1) The judgment condition is: The name of the current object parent node = 'iNextNo'
…
2) If there is a left-sided cotyledon leaf, the formula is:
The left of the current node = the left of the parent node + the total width of the child leaves on the left of the current node + the width of the current node
3) If there is no cotyledon on the left, but the cotyledon on the right, the formula is:
The left of the current node = the left of the parent node + the total width of the child leaves on the right of the current node
4) If the current node itself is a leaf, the formula is:
The left of the current node = the left of the parent node + the width of the current node
…
The formulas of (2) and (3) both get the left of the current node, and we also need to get the top of the current node
A very simple formula: the top of the current node = the top of the parent node + the offset (80)
Binary Tree Ideas (3)
Positioning ideas for connecting lines:
(1) Find the location of the current node and parent node
(2) Determine whether the current node is the left child node of the parent node or the right child node
(3) Draw lines
Some variables are defined here.
objOval //The current node is an object
objParentOval //The parent node of the current object is an object
objLine //The current line is an object
Line positioning formula:
from="x1,y1" to="x2,y2" is the way to locate lines in VML
If the current node is the left child node of the parent node, the formula is:
from = left + offset of parent node (15), top + offset of parent node (32)
to = left + offset of parent node (30), top - offset of parent node (2)
The current node is the right child node of the parent node, then the formula is:
from = left + offset of parent node (35), top + offset of parent node (32)
to = left + offset of parent node (20), top - offset of parent node (2)
That's all I can think of.
If you just make a company structure chart, it will be much simpler.
Below is Cy Young's ideas, and I just go deeper on his basis.
First, calculate the number of the lowest nodes and obtain the width.
Then the position of its upper node should be calculated based on the node's subordinate relationship and recursively.
Nodes at each level must be sorted by affiliation.
First, set the "basic value" = the node should be offset to the right
The left value of each node containing a child node is equal to half of the width of the node it owns plus the base value
Later on:
Recently, for some reason, the Internet has been bad. The time to disconnect is more than the time to be online.
So the code has not been simplified. In fact, there are many functions to improve, such as:
Need to add a right-click menu
The right-click menu contains new nodes, modify node names, change association relationships, etc.
You can right-click the right-click menu of this node on each node
explain:
1) It is a data file, I believe everyone will not have any problems.
2) It is a format file, there are several things to pay attention to.
(1) In the script:
（1） <xsl:value-of select="./iProcess/text()" /> ;
（2） {./iProcess/text()}
The functions of (1) and (2) are to return the string value of the expression given by the select parameter.
Their search criteria are the same, so the returned values are the same.
It’s just that the use occasions are different, their writing styles are also different.
<xsl:apply-templates select="team" order-by="blue_ID"/>
For example, we want to generate the following code
<div name = "parameter value">content</div>
Let's assume that the name is "name" and the parameter value is the value of the child node book below the current node in the XML data
The first way is to add the attribute name first and then the parameter value
<div>
<xsl:attribute name="name">
<xsl:value-of select="./book/text()"/> </xsl:attribute>
content
</div>
The second way to write it is to directly add attribute names and parameter values
<div name="{./book/text()}">Content</div>
For specific use, you can see the examples in the code I wrote.
XSL is in the official xmlns:xsl="http:///1999/XSL/Transform" standard
<xsl:value-of select="./book/text()"/>
The function is: just write out its text value, and
<xsl:value-of select="./book"/>
It displays its text value and the content of all its child nodes.
You can experiment and output a child node and a child node without it.
Check if the results are displayed are the same.
(2) Note:
IE5 does not support <tag att="{xpath}">
To use
<tag><xsl:attribute name="att"><xsl:value-of select="xpath"></xsl:attribute>
Use namespace
xmlns:xsl="http:///TR/WD-xsl"
<?xml version="1.0" encoding="gb2312" ?>
Another point:
In most XML textbooks, encoding="gb2312" is rarely added to the code shown in the code.
Therefore, when we use Chinese in XML, we will report an error because we did not write this statement.
postscript:
What we are talking about here is a way of thinking. If you learn from these things, it will naturally come in handy.