1. Introduction
A Binary Tree is a hierarchical data structure in which each node has at most two children, often referred to as the left and right child. It is a special case of a tree where each node has a maximum of two children. Binary trees are frequently used as a means for hierarchical data representation, including use cases like binary search trees, heap trees, syntax trees, and many more.
2. Implementation Steps
1. Define a Node class with attributes value, left, and right.
2. Initialize a BinaryTree class with a root node.
3. Implement the insert method to add nodes to the tree.
4. Implement a display method to print the tree in an in-order traversal.
5. Optionally, implement methods for pre-order, post-order, and level-order traversal.
3. Implementation in Ruby Programming
class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
end
class BinaryTree
def initialize
@root = nil
end
# Insert value into the tree
def insert(value)
@root = insert_recursive(@root, value)
end
# Display tree in in-order traversal
def display
display_recursive(@root)
end
private
def insert_recursive(node, value)
return Node.new(value) if node.nil?
if value < node.value
node.left = insert_recursive(node.left, value)
elsif value > node.value
node.right = insert_recursive(node.right, value)
end
node
end
def display_recursive(node)
return if node.nil?
display_recursive(node.left)
puts node.value
display_recursive(node.right)
end
end
# Client code
bt = BinaryTree.new
bt.insert(50)
bt.insert(30)
bt.insert(70)
bt.insert(20)
bt.insert(40)
bt.insert(60)
bt.insert(80)
puts "In-order traversal of binary tree:"
bt.display
Output:
In-order traversal of binary tree: 20 30 40 50 60 70 80
Explanation:
1. The Node class represents each element in the binary tree. Each node has a value, a left child, and a right child.
2. The BinaryTree initializes with a root node set to nil.
3. The insert method inserts a new value into the tree by invoking a recursive helper function insert_recursive. If the current node is empty, it places the new value there. If the value is less than the current node's value, it continues to the left child; if greater, it continues to the right child.
4. The display method prints the tree values in an in-order (left, root, right) sequence by invoking the recursive helper function display_recursive.
5. The private helper functions insert_recursive and display_recursive facilitate the recursive nature of binary tree operations.