Tree traversal: Difference between revisions
(add Ruby) |
(Ada) |
||
Line 17: | Line 17: | ||
postorder: 7 4 5 2 8 9 6 3 1 |
postorder: 7 4 5 2 8 9 6 3 1 |
||
level-order: 1 2 3 4 5 6 7 8 9 |
level-order: 1 2 3 4 5 6 7 8 9 |
||
=={{header|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> |
|||
=={{header|C}}== |
=={{header|C}}== |
Revision as of 01:50, 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>
Java
<lang java5>import java.util.LinkedList; public class TreeTraverse {
private static class Node{ public Node left; public Node right; public int data; public Node(int data){ this.data = data; }
public Node getLeft() { return left; }
public void setLeft(Node left) { this.left = left; }
public Node getRight() { return right; }
public void setRight(Node 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) { LinkedList<Node> nodequeue = new LinkedList<Node>(); nodequeue.addLast(n); while (!nodequeue.isEmpty()) { Node next = nodequeue.removeFirst(); System.out.print(next.data); if (next.getLeft() != null) { nodequeue.addLast(next.getLeft()); } if (next.getRight() != null) { nodequeue.addLast(next.getRight()); } } } public static void main(String[] args){ Node one = new Node(1); Node two = new Node(2); Node three = new Node(3); Node four = new Node(4); Node five = new Node(5); Node six = new Node(6); Node seven = new Node(7); Node eight = new Node(8); Node nine = new Node(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); }
}</lang> Output:
124753689 742518693 745289631 123456789
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(&block) 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