Skip to content

Instantly share code, notes, and snippets.

@kenwebb

kenwebb/xholonWorkbook.xml

Last active August 29, 2015 13:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kenwebb/9548290 to your computer and use it in GitHub Desktop.
Save kenwebb/9548290 to your computer and use it in GitHub Desktop.
Download ZIP
Rosetta Code - Tree traversal
Raw
xholonWorkbook.xml
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Fri Mar 14 2014 12:23:36 GMT-0400 (EDT)-->
<XholonWorkbook>
<Notes><![CDATA[
Xholon
------
Title: Rosetta Code - Tree traversal
Description:
Url: http://www.primordion.com/Xholon/gwt/wb/editwb.html?app=9548290&src=gist
InternalName: 9548290
Keywords:
My Notes
--------
Rosetta Code and Wikipedia both have pages on `Tree traversal`.
According to Wikipedia:
In computer science, tree traversal (also known as tree search)
refers to the process of visiting (examining and/or updating)
each node in a tree data structure, exactly once, in a systematic way.
Such traversals are classified by the order in which the nodes are visited.
The following algorithms are described for a binary tree,
but they may be generalized to other trees as well.
Here's the Rosetta Code task description, that I'll be using in this XholonWorkbook.
Implement a binary tree where each node carries an integer,
and implement preoder, inorder, postorder and level-order traversal.
Use those traversals to output the following tree:
1
/ \
/ \
/ \
2 3
/ \ /
4 5 6
/ / \
7 8 9
The correct output should look like this:
preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
postorder: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9
In the pure binary trees discussed on the Wikipedia and Rosetta Code pages,
each node has zero, one, or two child nodes.
The two possible child nodes are called the `left child node` and the `right child node`.
Tree structures are a fundamental part of Xholon.
Each Xholon app defines a composite structure hierarchy (CSH),
as a binary tree that contains nodes.
Each node references an optional `firstChild` and an optional `nextSibling`,
so each node references zero, one, or two other nodes.
The names `firstChild` and `nextSibling` are taken from the XML and HTML specifications.
To easily convert the example binary trees in the Wikipedia and Rosetta Code pages,
the tree diagrams must be rotated about 45 degrees counter clockwise.
Then it's pretty straight forward to manually construct the equivalent Xholon structure,
using the equivalences:
binary tree Xholon, XML, HTML
---------------- -----------------
left child node --> firstChild
right child node --> nextSibling
So in the Rosetta Code example, the following nodes are siblings of each other:
1 3
2 5
6 9
and the following nodes have a parent firstChild relationship:
1 2
2 4
4 7
3 6
6 8
The natural Xholon order, the top-to-bottom order in the classic (clsc) Xholon GUI, is pre-order.
This is also the order that nodes are defined in the Composite Structure Hierarchy XML.
If I run this workbook, and use the built-in Xholon `<TreeTraversal/>` script on the RosettaCode-tree,
I get the following results, which agree with the results on the rosettacode page:
`pre-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36
`1`:node_37 `2`:node_38 `4`:node_39 `7`:node_40 `5`:node_41 `3`:node_42 `6`:node_43 `8`:node_44 `9`:node_45
`in-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36
`7`:node_40 `4`:node_39 `2`:node_38 `5`:node_41 `1`:node_37 `8`:node_44 `6`:node_43 `9`:node_45 `3`:node_42
`post-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36
`7`:node_40 `4`:node_39 `5`:node_41 `2`:node_38 `8`:node_44 `9`:node_45 `6`:node_43 `3`:node_42 `1`:node_37
http://rosettacode.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/File:Sorted_binary_tree_preorder.svg
]]></Notes>
<_-.XholonClass>
<TreeTraversalSystem/>
<BinaryTreeRoot/>
<Node/>
</_-.XholonClass>
<xholonClassDetails>
</xholonClassDetails>
<TreeTraversalSystem>
<!-- Rosetta Code example -->
<BinaryTreeRoot roleName="rosettacode Tree traversal">
<Node roleName="1">
<Node roleName="2">
<Node roleName="4">
<Node roleName="7"/>
</Node>
</Node>
<Node roleName="5"/>
</Node>
<Node roleName="3">
<Node roleName="6">
<Node roleName="8"/>
</Node>
<Node roleName="9"/>
</Node>
<!--
Test the built-in Xholon tree traversal methods.
Please note:
default order is "pre-order"
"level-order" is not yet implemented
an invalid order such as "help" provides simple help information
-->
<!--
<TreeTraversal/>
<TreeTraversal order="pre-order"/>
<TreeTraversal order="in-order"/>
<TreeTraversal order="post-order"/>
<TreeTraversal order="level-order"/>
<TreeTraversal order="help"/>
-->
</BinaryTreeRoot>
<!-- Wikipedia example -->
<BinaryTreeRoot roleName="wikipedia Tree traversal">
<Node roleName="F">
<Node roleName="B">
<Node roleName="A"/>
</Node>
<Node roleName="D">
<Node roleName="C"/>
</Node>
<Node roleName="E"/>
</Node>
<Node roleName="G"/>
<Node roleName="I">
<Node roleName="H"/>
</Node>
<!--<TreeTraversal order="pre-order"/>-->
</BinaryTreeRoot>
</TreeTraversalSystem>
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:cc="http://creativecommons.org/ns#"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns="http://www.w3.org/2000/svg"
xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
version="1.1"
width="336.25092"
height="286.6962"
id="svg3953">
<!-- adapted from http://en.wikipedia.org/wiki/File:Sorted_binary_tree_preorder.svg -->
<defs
id="defs3955">
<marker
refX="0"
refY="0"
orient="auto"
id="SquareL"
style="overflow:visible">
<path
d="M -5,-5 -5,5 5,5 5,-5 -5,-5 z"
transform="scale(0.8,0.8)"
id="path4940"
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" />
</marker>
<marker
refX="0"
refY="0"
orient="auto"
id="DistanceStart"
style="overflow:visible">
<g
id="g2300">
<path
d="M 0,0 2,0"
id="path2306"
style="fill:none;stroke:#ffffff;stroke-width:1.14999998;stroke-linecap:square" />
<path
d="M 0,0 13,4 9,0 13,-4 0,0 z"
id="path2302"
style="fill:#000000;fill-rule:evenodd;stroke:none" />
<path
d="M 0,-4 0,40"
id="path2304"
style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:square" />
</g>
</marker>
<marker
refX="0"
refY="0"
orient="auto"
id="DotL"
style="overflow:visible">
<path
d="m -2.5,-1 c 0,2.76 -2.24,5 -5,5 -2.76,0 -5,-2.24 -5,-5 0,-2.76 2.24,-5 5,-5 2.76,0 5,2.24 5,5 z"
transform="matrix(0.8,0,0,0.8,5.92,0.8)"
id="path4931"
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none;marker-end:none" />
</marker>
<marker
refX="0"
refY="0"
orient="auto"
id="Arrow2Lend"
style="overflow:visible">
<path
d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z"
transform="matrix(-1.1,0,0,-1.1,-1.1,0)"
id="path4890"
style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" />
</marker>
<marker
refX="0"
refY="0"
orient="auto"
id="Arrow1Lstart"
style="overflow:visible">
<path
d="M 0,0 5,-5 -12.5,0 5,5 0,0 z"
transform="matrix(0.8,0,0,0.8,10,0)"
id="path4869"
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" />
</marker>
<inkscape:path-effect
effect="spiro"
id="path-effect2940" />
<inkscape:path-effect
effect="skeletal"
id="path-effect2942" />
</defs>
<metadata
id="metadata3958">
<rdf:RDF>
<cc:Work
rdf:about="">
<dc:format>image/svg+xml</dc:format>
<dc:type
rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
<dc:title></dc:title>
</cc:Work>
</rdf:RDF>
</metadata>
<g
transform="translate(-240.44597,-48.982663)"
id="layer1">
<g
transform="matrix(1.0888617,-0.62345404,0.62345404,1.0888617,166.31803,135.83755)"
id="graph0"
style="font-size:14px;font-family:Times-Roman">
<title
id="title5">sorted_binary_tree</title>
<g
id="node1">
<title
id="title8">C</title>
<ellipse
cx="60"
cy="185"
rx="18"
ry="18"
id="ellipse10"
style="fill:#ffffff;stroke:#000000" />
<text
x="60"
y="190"
id="text12"
style="text-anchor:middle">C</text>
</g>
<g
id="node2">
<title
id="title15">E</title>
<ellipse
cx="132"
cy="185"
rx="18"
ry="18"
id="ellipse17"
style="fill:#ffffff;stroke:#000000" />
<text
x="132"
y="190"
id="text19"
style="text-anchor:middle">E</text>
</g>
<g
id="node3">
<title
id="title22">H</title>
<ellipse
cx="204"
cy="185"
rx="17"
ry="18"
id="ellipse24"
style="fill:#ffffff;stroke:#000000" />
<text
x="204"
y="190"
id="text26"
style="text-anchor:middle">H</text>
</g>
<g
id="node4">
<title
id="title29">A</title>
<ellipse
cx="24"
cy="131"
rx="17"
ry="18"
id="ellipse31"
style="fill:#ffffff;stroke:#000000" />
<text
x="24"
y="136"
id="text33"
style="text-anchor:middle">A</text>
</g>
<g
id="node5">
<title
id="title36">D</title>
<ellipse
cx="96"
cy="131"
rx="17"
ry="18"
id="ellipse38"
style="fill:#ffffff;stroke:#000000" />
<text
x="96"
y="136"
id="text40"
style="text-anchor:middle">D</text>
</g>
<g
id="edge6">
<title
id="title43">D-&gt;C</title>
<path
d="m 86,147 c -3,4 -7,9 -10,14"
id="path45"
style="fill:none;stroke:#000000" />
<polygon
points="78,164 78,164 70,170 73,160 "
id="polygon47"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="edge8">
<title
id="title50">D-&gt;E</title>
<path
d="m 106,147 c 3,4 7,9 10,14"
id="path52"
style="fill:none;stroke:#000000" />
<polygon
points="119,160 119,160 122,170 114,164 "
id="polygon54"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="node6">
<title
id="title57">I</title>
<ellipse
cx="240"
cy="131"
rx="18"
ry="18"
id="ellipse59"
style="fill:#ffffff;stroke:#000000" />
<text
x="240"
y="136"
id="text61"
style="text-anchor:middle">I</text>
</g>
<g
id="edge12">
<title
id="title64">I-&gt;H</title>
<path
d="m 230,146 c -3,5 -6,10 -10,15"
id="path66"
style="fill:none;stroke:#000000" />
<polygon
points="223,163 223,163 214,169 217,159 "
id="polygon68"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="node7">
<title
id="title71">B</title>
<ellipse
cx="60"
cy="77"
rx="18"
ry="18"
id="ellipse73"
style="fill:#ffffff;stroke:#000000" />
<text
x="60"
y="82"
id="text75"
style="text-anchor:middle">B</text>
</g>
<g
id="edge3">
<title
id="title78">B-&gt;A</title>
<path
d="m 50,92 c -3,5 -6,10 -10,15"
id="path80"
style="fill:none;stroke:#000000" />
<polygon
points="43,109 43,109 34,115 37,105 "
id="polygon82"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="edge5">
<title
id="title85">B-&gt;D</title>
<path
d="m 70,92 c 3,5 6,10 10,15"
id="path87"
style="fill:none;stroke:#000000" />
<polygon
points="83,105 83,105 86,115 77,109 "
id="polygon89"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="node8">
<title
id="title92">G</title>
<ellipse
cx="204"
cy="77"
rx="17"
ry="18"
id="ellipse94"
style="fill:#ffffff;stroke:#000000" />
<text
x="204"
y="82"
id="text96"
style="text-anchor:middle">G</text>
</g>
<g
id="edge11">
<title
id="title99">G-&gt;I</title>
<path
d="m 214,93 c 3,4 7,9 10,14"
id="path101"
style="fill:none;stroke:#000000" />
<polygon
points="227,106 227,106 230,116 222,110 "
id="polygon103"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="node9">
<title
id="title106">F</title>
<ellipse
cx="132"
cy="23"
rx="18"
ry="18"
id="ellipse108"
style="fill:#ffffff;stroke:#000000" />
<text
x="132"
y="28"
id="text110"
style="text-anchor:middle">F</text>
</g>
<g
id="edge2">
<title
id="title113">F-&gt;B</title>
<path
d="M 117,34 C 106,42 94,51 83,60"
id="path115"
style="fill:none;stroke:#000000" />
<polygon
points="85,63 85,63 75,66 81,57 "
id="polygon117"
style="fill:#000000;stroke:#000000" />
</g>
<g
id="edge10">
<title
id="title120">F-&gt;G</title>
<path
d="m 147,34 c 11,8 23,17 34,26"
id="path122"
style="fill:none;stroke:#000000" />
<polygon
points="183,57 183,57 189,66 179,63 "
id="polygon124"
style="fill:#000000;stroke:#000000" />
</g>
</g>
</g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
</XholonWorkbook>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment