Tree traversal: Difference between revisions
(Ada) |
(→{{header|Java}}: generified, etc) |
||
Line 281: | Line 281: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
<lang java5>import java.util. |
<lang java5>import java.util.Queue; |
||
import java.util.LinkedList; |
|||
public class TreeTraverse { |
public class TreeTraverse { |
||
private static class Node{ |
private static class Node<T>{ |
||
public Node left; |
public Node<T> left; |
||
public Node right; |
public Node<T> right; |
||
public |
public T data; |
||
public Node( |
public Node(T data){ |
||
this.data = data; |
this.data = data; |
||
} |
} |
||
public Node getLeft() { |
public Node<T> getLeft() { |
||
return left; |
return left; |
||
} |
} |
||
public void setLeft(Node left) { |
public void setLeft(Node<T> left) { |
||
this.left = left; |
this.left = left; |
||
} |
} |
||
public Node getRight() { |
public Node<T> getRight() { |
||
return right; |
return right; |
||
} |
} |
||
public void setRight(Node right) { |
public void setRight(Node<T> right) { |
||
this.right = right; |
this.right = right; |
||
} |
} |
||
} |
} |
||
public static void preorder(Node n){ |
public static void preorder(Node<?> n){ |
||
System.out.print(n.data); |
System.out.print(n.data + " "); |
||
if(n.getLeft()!= null){ |
if(n.getLeft()!= null){ |
||
preorder(n.getLeft()); |
preorder(n.getLeft()); |
||
Line 319: | Line 320: | ||
} |
} |
||
public static void inorder(Node n){ |
public static void inorder(Node<?> n){ |
||
if(n.getLeft()!= null){ |
if(n.getLeft()!= null){ |
||
inorder(n.getLeft()); |
inorder(n.getLeft()); |
||
} |
} |
||
System.out.print(n.data); |
System.out.print(n.data + " "); |
||
if(n.getRight()!= null){ |
if(n.getRight()!= null){ |
||
inorder(n.getRight()); |
inorder(n.getRight()); |
||
Line 329: | Line 330: | ||
} |
} |
||
public static void postorder(Node n){ |
public static void postorder(Node<?> n){ |
||
if(n.getLeft()!= null){ |
if(n.getLeft()!= null){ |
||
postorder(n.getLeft()); |
postorder(n.getLeft()); |
||
Line 336: | Line 337: | ||
postorder(n.getRight()); |
postorder(n.getRight()); |
||
} |
} |
||
System.out.print(n.data); |
System.out.print(n.data + " "); |
||
} |
} |
||
public static void levelorder(Node n) { |
public static void levelorder(Node<?> n) { |
||
Queue<Node<?>> nodequeue = new LinkedList<Node<?>>(); |
|||
nodequeue. |
nodequeue.add(n); |
||
while (!nodequeue.isEmpty()) { |
while (!nodequeue.isEmpty()) { |
||
Node next = nodequeue. |
Node<?> next = nodequeue.remove(); |
||
System.out.print(next.data); |
System.out.print(next.data + " "); |
||
if (next.getLeft() != null) { |
if (next.getLeft() != null) { |
||
nodequeue. |
nodequeue.add(next.getLeft()); |
||
} |
} |
||
if (next.getRight() != null) { |
if (next.getRight() != null) { |
||
nodequeue. |
nodequeue.add(next.getRight()); |
||
} |
} |
||
} |
} |
||
Line 355: | Line 356: | ||
public static void main(String[] args){ |
public static void main(String[] args){ |
||
Node one = new Node(1); |
Node<Integer> one = new Node<Integer>(1); |
||
Node two = new Node(2); |
Node<Integer> two = new Node<Integer>(2); |
||
Node three = new Node(3); |
Node<Integer> three = new Node<Integer>(3); |
||
Node four = new Node(4); |
Node<Integer> four = new Node<Integer>(4); |
||
Node five = new Node(5); |
Node<Integer> five = new Node<Integer>(5); |
||
Node six = new Node(6); |
Node<Integer> six = new Node<Integer>(6); |
||
Node seven = new Node(7); |
Node<Integer> seven = new Node<Integer>(7); |
||
Node eight = new Node(8); |
Node<Integer> eight = new Node<Integer>(8); |
||
Node nine = new Node(9); |
Node<Integer> nine = new Node<Integer>(9); |
||
one.setLeft(two); |
one.setLeft(two); |
||
one.setRight(three); |
one.setRight(three); |
||
Line 380: | Line 381: | ||
System.out.println(); |
System.out.println(); |
||
levelorder(one); |
levelorder(one); |
||
System.out.println(); |
|||
} |
} |
||
}</lang> |
}</lang> |
||
Output: |
Output: |
||
<pre> |
<pre>1 2 4 7 5 3 6 8 9 |
||
7 4 2 5 1 8 6 9 3 |
|||
742518693 |
|||
7 4 5 2 8 9 6 3 1 |
|||
745289631 |
|||
1 2 3 4 5 6 7 8 9 </pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
Revision as of 05:07, 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.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(&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