Tree traversal: Difference between revisions
m (→{{header|Ada}}: formatting) |
(Forth) |
||
Line 275: | Line 275: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|Forth}}== |
|||
<lang forth> |
|||
\ binary tree (dictionary) |
|||
: node ( l r data -- node ) here >r , , , r> ; |
|||
: leaf ( data -- node ) 0 0 rot node ; |
|||
: >data ( node -- ) @ ; |
|||
: >right ( node -- ) cell+ @ ; |
|||
: >left ( node -- ) cell+ cell+ @ ; |
|||
: preorder ( xt tree -- ) |
|||
dup 0= if 2drop exit then |
|||
2dup >data swap execute |
|||
2dup >left recurse |
|||
>right recurse ; |
|||
: inorder ( xt tree -- ) |
|||
dup 0= if 2drop exit then |
|||
2dup >left recurse |
|||
2dup >data swap execute |
|||
>right recurse ; |
|||
: postorder ( xt tree -- ) |
|||
dup 0= if 2drop exit then |
|||
2dup >left recurse |
|||
2dup >right recurse |
|||
>data swap execute ; |
|||
: max-depth ( tree -- n ) |
|||
dup 0= if exit then |
|||
dup >left recurse |
|||
swap >right recurse max 1+ ; |
|||
defer depthaction |
|||
: depthorder ( depth tree -- ) |
|||
dup 0= if 2drop exit then |
|||
over 0= |
|||
if >data depthaction drop |
|||
else over 1- over >left recurse |
|||
swap 1- swap >right recurse |
|||
then ; |
|||
: levelorder ( xt tree -- ) |
|||
swap is depthaction |
|||
dup max-depth 0 ?do |
|||
i over depthorder |
|||
loop drop ; |
|||
7 leaf 0 4 node |
|||
5 leaf 2 node |
|||
8 leaf 9 leaf 6 node |
|||
0 3 node 1 node value tree |
|||
cr ' . tree preorder \ 1 2 4 7 5 3 6 8 9 |
|||
cr ' . tree inorder \ 7 4 2 5 1 8 6 9 3 |
|||
cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1 |
|||
cr tree max-depth . \ 4 |
|||
cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9 |
|||
</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 17:47, 9 July 2009
You are encouraged to solve this task according to the task description, using any language you may know.
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
Ada
<lang Ada>with Ada.Text_Io; use Ada.Text_Io; with Ada.Unchecked_Deallocation; with Ada.Containers.Doubly_Linked_Lists;
procedure Tree_Traversal is
type Node; type Node_Access is access Node; type Node is record Left : Node_Access := null; Right : Node_Access := null; Data : Integer; end record; procedure Destroy_Tree(N : in out Node_Access) is procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access); begin if N.Left /= null then Destroy_Tree(N.Left); end if; if N.Right /= null then Destroy_Tree(N.Right); end if; Free(N); end Destroy_Tree; function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is Temp : Node_Access := new Node; begin Temp.Data := Value; Temp.Left := Left; Temp.Right := Right; return Temp; end Tree; procedure Preorder(N : Node_Access) is begin Put(Integer'Image(N.Data)); if N.Left /= null then Preorder(N.Left); end if; if N.Right /= null then Preorder(N.Right); end if; end Preorder; procedure Inorder(N : Node_Access) is begin if N.Left /= null then Inorder(N.Left); end if; Put(Integer'Image(N.Data)); if N.Right /= null then Inorder(N.Right); end if; end Inorder; procedure Postorder(N : Node_Access) is begin if N.Left /= null then Postorder(N.Left); end if; if N.Right /= null then Postorder(N.Right); end if; Put(Integer'Image(N.Data)); end Postorder; procedure Levelorder(N : Node_Access) is package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access); use Queues; Node_Queue : List; Next : Node_Access; begin Node_Queue.Append(N); while not Is_Empty(Node_Queue) loop Next := First_Element(Node_Queue); Delete_First(Node_Queue); Put(Integer'Image(Next.Data)); if Next.Left /= null then Node_Queue.Append(Next.Left); end if; if Next.Right /= null then Node_Queue.Append(Next.Right); end if; end loop; end Levelorder; N : Node_Access;
begin
N := Tree(1, Tree(2, Tree(4, Tree(7, null, null), null), Tree(5, null, null)), Tree(3, Tree(6, Tree(8, null, null), Tree(9, null, null)), null)); Put("preorder: "); Preorder(N); New_Line; Put("inorder: "); Inorder(N); New_Line; Put("postorder: "); Postorder(N); New_Line; Put("level order: "); Levelorder(N); New_Line; Destroy_Tree(N);
end Tree_traversal;</lang>
C
<lang c>#include <stdlib.h>
- include <stdio.h>
typedef struct node_s {
int value; struct node_s* left; struct node_s* right;
} *node;
node tree(int v, node l, node r) {
node n = malloc(sizeof(struct node_s)); n->value = v; n->left = l; n->right = r; return n;
}
void destroy_tree(node n) {
if (n->left) destroy_tree(n->left); if (n->right) destroy_tree(n->right); free(n);
}
void preorder(node n, void (*f)(int)) {
f(n->value); if (n->left) preorder(n->left, f); if (n->right) preorder(n->right, f);
}
void inorder(node n, void (*f)(int)) {
if (n->left) inorder(n->left, f); f(n->value); if (n->right) inorder(n->right, f);
}
void postorder(node n, void (*f)(int)) {
if (n->left) postorder(n->left, f); if (n->right) postorder(n->right, f); f(n->value);
}
/* helper queue for levelorder */ typedef struct qnode_s {
struct qnode_s* next; node value;
} *qnode;
typedef struct { qnode begin, end; } queue;
void enqueue(queue* q, node n) {
qnode node = malloc(sizeof(struct qnode_s)); node->value = n; node->next = 0; if (q->end) q->end->next = node; else q->begin = node; q->end = node;
}
node dequeue(queue* q) {
node tmp = q->begin->value; qnode second = q->begin->next; free(q->begin); q->begin = second; if (!q->begin) q->end = 0; return tmp;
}
int queue_empty(queue* q) {
return !q->begin;
}
void levelorder(node n, void(*f)(int)) {
queue nodequeue = {}; enqueue(&nodequeue, n); while (!queue_empty(&nodequeue)) { node next = dequeue(&nodequeue); f(next->value); if (next->left) enqueue(&nodequeue, next->left); if (next->right) enqueue(&nodequeue, next->right); }
}
void print(int n) {
printf("%d ", n);
}
int main() {
node n = tree(1, tree(2, tree(4, tree(7, 0, 0), 0), tree(5, 0, 0)), tree(3, tree(6, tree(8, 0, 0), tree(9, 0, 0)), 0));
printf("preorder: "); preorder(n, print); printf("\n");
printf("inorder: "); inorder(n, print); printf("\n");
printf("postorder: "); postorder(n, print); printf("\n");
printf("level-order: "); levelorder(n, print); printf("\n");
destroy_tree(n);
return 0;
}</lang>
Forth
<lang forth> \ binary tree (dictionary)
- node ( l r data -- node ) here >r , , , r> ;
- leaf ( data -- node ) 0 0 rot node ;
- >data ( node -- ) @ ;
- >right ( node -- ) cell+ @ ;
- >left ( node -- ) cell+ cell+ @ ;
- preorder ( xt tree -- )
dup 0= if 2drop exit then 2dup >data swap execute 2dup >left recurse >right recurse ;
- inorder ( xt tree -- )
dup 0= if 2drop exit then 2dup >left recurse 2dup >data swap execute >right recurse ;
- postorder ( xt tree -- )
dup 0= if 2drop exit then 2dup >left recurse 2dup >right recurse >data swap execute ;
- max-depth ( tree -- n )
dup 0= if exit then dup >left recurse swap >right recurse max 1+ ;
defer depthaction
- depthorder ( depth tree -- )
dup 0= if 2drop exit then over 0= if >data depthaction drop else over 1- over >left recurse swap 1- swap >right recurse then ;
- levelorder ( xt tree -- )
swap is depthaction dup max-depth 0 ?do i over depthorder loop drop ;
7 leaf 0 4 node
5 leaf 2 node
8 leaf 9 leaf 6 node
0 3 node 1 node value tree
cr ' . tree preorder \ 1 2 4 7 5 3 6 8 9 cr ' . tree inorder \ 7 4 2 5 1 8 6 9 3 cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1 cr tree max-depth . \ 4 cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9 </lang>
Java
<lang java5>import java.util.Queue; import java.util.LinkedList; public class TreeTraverse {
private static class Node<T>{ public Node<T> left; public Node<T> right; public T data; public Node(T data){ this.data = data; }
public Node<T> getLeft() { return left; }
public void setLeft(Node<T> left) { this.left = left; }
public Node<T> getRight() { return right; }
public void setRight(Node<T> right) { this.right = right; } }
public static void preorder(Node<?> n){ System.out.print(n.data + " "); if(n.getLeft()!= null){ preorder(n.getLeft()); } if(n.getRight()!= null){ preorder(n.getRight()); } } public static void inorder(Node<?> n){ if(n.getLeft()!= null){ inorder(n.getLeft()); } System.out.print(n.data + " "); if(n.getRight()!= null){ inorder(n.getRight()); } } public static void postorder(Node<?> n){ if(n.getLeft()!= null){ postorder(n.getLeft()); } if(n.getRight()!= null){ postorder(n.getRight()); } System.out.print(n.data + " "); } public static void levelorder(Node<?> n) { Queue<Node<?>> nodequeue = new LinkedList<Node<?>>(); nodequeue.add(n); while (!nodequeue.isEmpty()) { Node<?> next = nodequeue.remove(); System.out.print(next.data + " "); if (next.getLeft() != null) { nodequeue.add(next.getLeft()); } if (next.getRight() != null) { nodequeue.add(next.getRight()); } } } public static void main(String[] args){ Node<Integer> one = new Node<Integer>(1); Node<Integer> two = new Node<Integer>(2); Node<Integer> three = new Node<Integer>(3); Node<Integer> four = new Node<Integer>(4); Node<Integer> five = new Node<Integer>(5); Node<Integer> six = new Node<Integer>(6); Node<Integer> seven = new Node<Integer>(7); Node<Integer> eight = new Node<Integer>(8); Node<Integer> nine = new Node<Integer>(9); one.setLeft(two); one.setRight(three); two.setLeft(four); two.setRight(five); three.setLeft(six); four.setLeft(seven); six.setLeft(eight); six.setRight(nine); preorder(one); System.out.println(); inorder(one); System.out.println(); postorder(one); System.out.println(); levelorder(one); System.out.println(); }
}</lang> Output:
1 2 4 7 5 3 6 8 9 7 4 2 5 1 8 6 9 3 7 4 5 2 8 9 6 3 1 1 2 3 4 5 6 7 8 9
Ruby
<lang ruby>class BinaryTreeNode
def initialize(value, left=nil, right=nil) @value = value @left = left @right = right end attr_reader :value, :left, :right
def each_preorder(&block) yield self left.each_preorder(&block) if left right.each_preorder(&block) if right end
def each_inorder(&block) left.each_inorder(&block) if left yield self right.each_inorder(&block) if right end
def each_postorder(&block) left.each_postorder(&block) if left right.each_postorder(&block) if right yield self end
def each_levelorder queue = [self] until queue.empty? node = queue.shift yield node queue << node.left if node.left queue << node.right if node.right end end
end
root = BinaryTreeNode.new(1,
BinaryTreeNode.new(2, BinaryTreeNode.new(4, BinaryTreeNode.new(7) ), BinaryTreeNode.new(5) ), BinaryTreeNode.new(3, BinaryTreeNode.new(6, BinaryTreeNode.new(8), BinaryTreeNode.new(9) ) ) )
print "preorder: " root.each_preorder {|node| print "#{node.value} "} puts print "inorder: " root.each_inorder {|node| print "#{node.value} "} puts print "postorder: " root.each_postorder {|node| print "#{node.value} "} puts print "levelorder: " root.each_levelorder {|node| print "#{node.value} "} puts</lang> Output:
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 levelorder: 1 2 3 4 5 6 7 8 9
Tcl
<lang tcl>oo::class create tree {
# Basic tree data structure stuff... variable val l r constructor {value {left {}} {right {}}} {
set val $value set l $left set r $right
} method value {} {return $val} method left {} {return $l} method right {} {return $r} destructor {
if {$l ne ""} {$l destroy} if {$r ne ""} {$r destroy}
}
# Traversal methods method preorder {varName script {level 0}} {
upvar [incr level] $varName var set var $val uplevel $level $script if {$l ne ""} {$l preorder $varName $script $level} if {$r ne ""} {$r preorder $varName $script $level}
} method inorder {varName script {level 0}} {
upvar [incr level] $varName var if {$l ne ""} {$l inorder $varName $script $level} set var $val uplevel $level $script if {$r ne ""} {$r inorder $varName $script $level}
} method postorder {varName script {level 0}} {
upvar [incr level] $varName var if {$l ne ""} {$l postorder $varName $script $level} if {$r ne ""} {$r postorder $varName $script $level} set var $val uplevel $level $script
} method levelorder {varName script} {
upvar 1 $varName var set nodes [list [self]]; # A queue of nodes to process while {[llength $nodes] > 0} { set nodes [lassign $nodes n] set var [$n value] uplevel 1 $script if {[$n left] ne ""} {lappend nodes [$n left]} if {[$n right] ne ""} {lappend nodes [$n right]} }
}
}</lang>
Note that in Tcl it is conventional to handle performing something “for each element” by evaluating a script in the caller's scope for each node after setting a caller-nominated variable to the value for that iteration. Doing this transparently while recursing requires the use of a varying ‘level’ parameter to upvar
and uplevel
, but makes for compact and clear code.
Demo code to satisfy the official challenge instance: <lang tcl># Helpers to make construction and listing of a whole tree simpler proc Tree nested {
lassign $nested v l r if {$l ne ""} {set l [Tree $l]} if {$r ne ""} {set r [Tree $r]} tree new $v $l $r
} proc Listify {tree order} {
set list {} $tree $order v {
lappend list $v
} return $list
}
- Make a tree, print it a few ways, and destroy the tree
set t [Tree {1 {2 {4 7} 5} {3 {6 8 9}}}] puts "preorder: [Listify $t preorder]" puts "inorder: [Listify $t inorder]" puts "postorder: [Listify $t postorder]" puts "level-order: [Listify $t levelorder]" $t destroy</lang> Output:
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