Same fringe: Difference between revisions

The package is generic, which allows Data to be essentially of any type.

 

type Data is private;

package Bin_Trees is

end record;

 

 

The implementation is straightforward.

 

 

package body Bin_Trees is

end Tree;

 

 

Next, we specify and implement package that defines a task type for tree traversal. This allows us to run any number of tree traversals in parallel, even on the same tree.

 

with procedure Process_Data(Item: Data);

with function Stop return Boolean;

-- except when Stop becomes true; in this case, the task terminates

end Inorder_Task;

 

task body Inorder_Task is

procedure Inorder(Tree: Tree_Type) is

Finish;

end Inorder_Task;

 

When comparing two trees T1 and T2, we will define two tasks, a "Producer.Inorder_Task" and a "Consumer.Inorder_Task". The producer will write data items to a buffer, the consumer will read items from the buffer and compare them with its own data items. Both tasks will terminate when the consumer finds a data item different from the one written by the producer, or when either task has written its last item and the other one has items left.

A third auxiliary task just waits until the consumer has finished and the result of the fringe comparison can be read.

 

 

procedure Main is

Ada.Text_IO.New_Line;

end loop;

 

Note that we do not call Destroy_Tree to reclaim the dynamic memory. In our case, this is not needed since the memory will be reclaimed at the end of Main, anyway.

DIFF( 4, 1 ); DIFF( 4, 2 ); same( 4, 3 ); same( 4, 4 ); DIFF( 4, 5 );

DIFF( 5, 1 ); DIFF( 5, 2 ); DIFF( 5, 3 ); DIFF( 5, 4 ); same( 5, 5 ); </pre>

=={{header|Bracmat}}==

=

. ( next

, (((a.b).c).x.y.z)

)

Output:

<pre>x,x

, (((a.b).c).x.y.z)

equal</pre>

=={{header|C}}==

With rudimentary coroutine support based on ucontext. I don't know if it will compile on anything other than GCC.

#include <stdlib.h>

#include <ucontext.h>

 

return 0;

 

=={{header|Clojure}}==

''children'' returns the children of a branch node; ''content'' returns the content of a branch node.

A fringe value is either the content of a branch node without children, or a non-branch node.

(letfn [(walk [node]

(lazy-seq

(mapcat walk (children node)))

(list node))))]

For this problem, binary trees are represented as vectors, whose nodes are either [''content'' ''left'' ''right''] or just ''content''.

(println (vfringe-seq [10 1 2])) ; (1 2)

Then we can use a general sequence-equality function:

(cond

(and (empty? s1) (empty? s2)) true

(not= (empty? s1) (empty? s2)) false

(= (first s1) (first s2)) (recur (rest s1) (rest s2))

 

=={{header|D}}==

===Short Version===

A short recursive solution that is not lazy (and lacks the const/immutable/pure/nothrow):

T data;

Node* L, R;

auto t3 = new N(1, new N(2, new N(3, new N(40), new N(51))));

writeln(sameFringe(t1, t3));

{{out}}

<pre>true

===Strong Lazy Version===

This version is quite long because it tries to be reliable. The code contains contracts, unit tests, annotations, and so on.

import std.algorithm: equal;

 

private Stack!BT stack;

 

assert(stack.empty || isLeaf(stack.head));

}

stack.push(t);

if (!isLeaf(t)) {

}

}

writeln("sameFringe(t1, t2): ", sameFringe(t1, t2));

writeln("sameFringe(t1, t3): ", sameFringe(t1, t3));

{{out}}

<pre>fringe(t1): [40, 50]

sameFringe(t1, t2): true

sameFringe(t1, t3): false</pre>

 

=={{header|Go}}==

 

import "fmt"

&node{int: 13}}

fmt.Println(sameFringe(t1, t2)) // prints true.

 

=={{header|Haskell}}==

 

To get the fringe, we can simply use the solution for [[Flatten a list#Haskell|Flatten a list]], slightly modified for a binary tree instead of a general tree:

 

fringe :: Tree a -> [a]

fringe (Node n1 n2) = fringe n1 ++ fringe n2

 

sameFringe t1 t2 = fringe t1 == fringe t2

 

main = do

<pre>True

True

The following solution works in both languages:

 

aTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]

bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]

procedure preorder(L)

if \L then suspend L | preorder(L[2|3])

 

Output:

=={{header|J}}==

 

 

Note that the time/space optimizations here can change with the language implementation, but current implementations make no effort to treat trees efficiently.

Anyways, here's a recursive routine to convert a flat list into a binary tree:

 

 

And, here are two differently structured trees which represent the same underlying data:

 

 

And, here's our original operation in action (<code>1 {:: ubp</code> is a subtree of ubp which omits a leaf node):

 

1

bp sameFringe 1 {:: ubp

 

=={{header|Java}}==

 

'''Code:'''

 

class SameFringe

}

}

 

'''Output:'''

areLeavesSame(1, 2)? true

areLeavesSame(2, 3)? false</pre>

 

=={{header|OCaml}}==

 

let rec next = function

let check a b =

print_endline (if samefringe a b then "same" else "different") in

Output:

<pre>same

The tree iterator is pretty simple: we use array references with index 0 as the left subtree and index 1 holding the right subtree. So as we go down the tree towards the first leaf, we push each right subtree that we will consider later onto the rtree stack. Eventually, we'll hit a leaf and return it. The next time we go into the iterator, we simply pull off the last deferred subtree and continue the process.

 

#!/usr/bin/perl

use strict;

}

}

{{out}}

<pre>

tree[2] vs tree[3]: Different</pre>

 

 

 

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

This uses coroutines to traverse the trees, so it works only in the 64-bit version.

(co Rt

(recur (Tree)

(NIL (= Node1 Node2)) ) )

(co "rt1")

Test:

-> NIL

: (for N (5 4 6 3 7 1 2) (idx '*Tree2 N T))

 

: (cmpTrees *Tree1 *Tree2)

 

=={{header|Python}}==

from itertools import zip_longest as izip_longest # Python 3.x

except:

assert not same_fringe(a, x)

assert not same_fringe(a, y)

{{out}}

There is no output, which signifies success.

=={{header|Racket}}==

 

 

#lang racket

(let loop ([tree tree])

(define (same-fringe? tree1 tree2)

 

=={{header|REXX}}==

===Version 1 using father node ===

 

* Same Fringe

* 1 A A

i=mknode('I',t); Call attrite i,f,t

End

Output:

<pre>

 

===Version 2 without using father node ===

* Same Fringe

= 1 A A

i=mknode('I',t); Call attrite i,f,t

End

Output is the same as for Version 1

 

===version 1.1===

 

 

A difference is: H ¬= δ

</pre>

 

{{works with|Tcl|8.6}}

{{tcllib|struct::tree}}

package require struct::tree

 

rename $c2 {}

}

Demonstrating:

struct::tree t1 deserialize {

root {} {}

 

# Print the boolean result of doing the comparison

{{out}}

<pre>

c != cc

0

</pre>