Anonymous user
Tree datastructures: Difference between revisions
→{{header|Julia}}
Line 720:
original == restored: true
</pre>
=={{header|Nim}}==
<lang Nim>import strformat, strutils
####################################################################################################
# Nested representation of trees.
# The tree is simply the first node.
type
NNode*[T] = ref object
value*: T
children*: seq[NNode[T]]
proc newNNode*[T](value: T; children: varargs[NNode[T]]): NNode[T] =
## Create a node.
NNode[T](value: value, children: @children)
proc add*[T](node: NNode[T]; children: varargs[NNode[T]]) =
## Add a list of chlidren to a node.
node.children.add children
proc `$`*[T](node: NNode[T]; depth = 0): string =
## Return a string representation of a tree/node.
result = repeat(' ', 2 * depth) & $node.value & '\n'
for child in node.children:
result.add `$`(child, depth + 1)
####################################################################################################
# Indented representation of trees.
# The tree is described as the list of the nodes.
type
INode*[T] = object
value*: T
level*: Natural
ITree*[T] = seq[INode[T]]
proc initINode*[T](value: T; level: Natural): INode[T] =
## Return a new node.
INode[T](value: value, level: level)
proc initItree*[T](value: T): ITree[T] =
## Return a new tree initialized with the first node (root node).
result = @[initINode(value, 0)]
proc add*[T](tree: var ITree[T]; nodes: varargs[INode[T]]) =
## Add a list of nodes to the tree.
for node in nodes:
if node.level - tree[^1].level > 1:
raise newException(ValueError, &"wrong level {node.level} in node {node.value}.")
tree.add node
proc `$`*[T](tree: ITree[T]): string =
## Return a string representation of a tree.
for node in tree:
result.add $node.level & ' ' & $node.value & '\n'
####################################################################################################
# Conversion between nested form and indented form.
proc toIndented*[T](node: NNode[T]): Itree[T] =
## Convert a tree in nested form to a tree in indented form.
proc addNode[T](tree: var Itree[T]; node: NNode[T]; level: Natural) =
## Add a node to the tree at the given level.
tree.add initINode(node.value, level)
for child in node.children:
tree.addNode(child, level + 1)
result.addNode(node, 0)
proc toNested*[T](tree: Itree[T]): NNode[T] =
## Convert a tree in indented form to a tree in nested form.
var stack: seq[NNode[T]] # Note that stack.len is equal to the current level.
var nnode = newNNode(tree[0].value) # Root.
for i in 1..tree.high:
let inode = tree[i]
if inode.level > stack.len:
# Child.
stack.add nnode
elif inode.level == stack.len:
# Sibling.
stack[^1].children.add nnode
else:
# Branch terminated.
while inode.level < stack.len:
stack[^1].children.add nnode
nnode = stack.pop()
stack[^1].children.add nnode
nnode = newNNode(inode.value)
# Empty the stack.
while stack.len > 0:
stack[^1].children.add nnode
nnode = stack.pop()
result = nnode
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
echo "Displaying tree built using nested structure:"
let nestedTree = newNNode("RosettaCode")
let rocks = newNNode("rocks")
rocks.add newNNode("code"), newNNode("comparison"), newNNode("wiki")
let mocks = newNNode("mocks", newNNode("trolling"))
nestedTree.add rocks, mocks
echo nestedTree
echo "Displaying tree converted to indented structure:"
let indentedTree = nestedTree.toIndented
echo indentedTree
echo "Displaying tree converted back to nested structure:"
echo indentedTree.toNested
echo "Are they equal? ", if $nestedTree == $indentedTree.toNested: "yes" else: "no"</lang>
{{out}}
<pre>Displaying tree built using nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
Displaying tree converted to indented structure:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
Displaying tree converted back to nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
Are they equal? yes</pre>
=={{header|Perl}}==
| |||