Module: TreeLab

Defined in:
lib/treelab.rb

Defined Under Namespace

Classes: BinarySearchTree, BinaryTree, Node

Constant Summary collapse

@@tree =

Version 1.2 (27/09/2012)

Changelog
    1.    Created Binary Search Tree class

Version 1.1    (08/08/2012)
Changelog
    1.    Changed node.leftChild to node.left, and node.rightChild to node.right
    2.    Merged preorder_traversal(*speed), inorder_traversal(*speed), postorder_traversal(*speed) into traversal(tree, option, *speed), where valid options are preorder, inorder, and postorder
    3.    Display text at end of traversal to indicate visit order: "Visited 9, 6, 5, 4"
    4.    Display order number during traversal
    5.    Tree animation now freezes at last frame

Version  1.0    (06/08/2012)
Changelog
    1.    Created Binary Tree, Node classes to represent a binary tree and a tree node
    2.    Created view_tree to visualize the tree and preorder_traversal, inorder_traversal, postorder_traversal to animate the traversal of a tree

nil
@@visited = 
nil
@@sleep = 
0.5

Instance Method Summary collapse

Instance Method Details

#traversal(tree, option, *speed) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/treelab.rb', line 43

def traversal(tree, option, *speed)
    view_tree(tree)
    if (!speed[0])
        @@sleep = 0.5
    else
        @@sleep = speed[0]
    end
    
    Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 10)

    @@visited = Array.new
    
    root = @@tree.root
    sleep(1)
    case option
    when :preorder
        preorder_traverse(root)
    when :inorder
        inorder_traverse(root)
    when :postorder
        postorder_traverse(root)
    else
        return "Invalid option. Valid options include :preorder, :inorder, :postorder"
    end
    sleep(1)
    
    text = "Visited: "
    
    @@visited.each_with_index {
        |val, index| 
        text = text + val.to_s
        if index != @@visited.length-1
            text = text + ", "
        end
    }
    return text
end

#tree ⇒ Object 



39
40
41
 
# File 'lib/treelab.rb', line 39

def tree
    @@tree
end

#view_tree(tree) ⇒ Object 



24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/treelab.rb', line 24

def view_tree(tree)
    @@tree = tree
    raise "Value must be a BinaryTree!" if !(tree.class == TreeLab::BinaryTree || tree.class == TreeLab::BinarySearchTree)
    # Initializes the canvas and font type
    Canvas.init(30+(2**tree.heightOfTree)*30, 50*tree.heightOfTree+50, "TreeLab")
    Canvas::Font.new('bucketfont', :family => 'Helvetica', :size => 10)

    # calls recursive method to draw the tree using post-order traversal
    if tree.root == nil
        return true
    end
    preOrder(tree.root, ((2**tree.heightOfTree)*30)/2, 30, ((2**tree.heightOfTree)*30)/2)
    return true
end