Inorder traversal of binary tree using stack in vb.net
Vb program for Inorder traversal of binary tree using stack. Here problem description and explanation.
' Include namespace system
Imports System
' Vb.net program for
' Inorder traversal without recursion
' Using stack
' Binary Tree node
Public Class TreeNode
Public data As Integer
Public left As TreeNode
Public right As TreeNode
' Make a tree node
Public Sub New(ByVal data As Integer)
' Set node data
Me.data = data
Me.left = Nothing
Me.right = Nothing
End Sub
End Class
Public Class StackNode
Public element As TreeNode
Public [next] As StackNode
Public Sub New(ByVal element As TreeNode)
Me.element = element
Me.next = Nothing
End Sub
End Class' Stack Class
Public Class MyStack
Public top As StackNode
Public size As Integer
Public Sub New()
Me.top = Nothing
Me.size = 0
End Sub
' Add new element into stack
Public Sub push(ByVal element As TreeNode)
' Create new node
Dim node As StackNode = New StackNode(element)
node.[next] = Me.top
' new node is new top
Me.top = node
' Increase the size
Me.size += 1
End Sub
' Remove top element of the stack
Public Sub pop()
if (Me.top IsNot Nothing) Then
' next node is new top
Me.top = Me.top.[next]
' Reduce size
Me.size -= 1
End If
End Sub
' Returns the status of empty or non empty stacks
Public Function isEmpty() As Boolean
if (Me.size > 0 AndAlso Me.top IsNot Nothing) Then
Return False
Else
Return True
End IF
End Function
' Return top element of stack
Public Function peek() As TreeNode
if (Me.isEmpty()) Then
Return Nothing
End If
Return Me.top.element
End Function
End Class
public Class BinaryTree
Public root As TreeNode
Public Sub New()
' Set initial tree root to null
Me.root = Nothing
End Sub
' Display Inorder view of binary tree
Public Sub inorder()
if (Me.root IsNot Nothing) Then
' Make new stack
Dim s As MyStack = New MyStack()
Dim node As TreeNode = Me.root
' Display tree element
while (Not s.isEmpty() OrElse node IsNot Nothing)
if (node IsNot Nothing) Then
' Add current node
s.push(node)
' Visit to left subtree
node = node.left
Else
' When node is null
' Get stack top element
node = s.peek()
' Display node value
Console.Write(" " + node.data.ToString())
' Remove top element of the stack
s.pop()
' Visit to left subtree of current node
node = node.right
End IF
End While
Else
Console.Write("Empty Linked List" & vbLf )
End IF
End Sub
Public Shared Sub Main(ByVal args As String())
' Create new tree
Dim tree As BinaryTree = New BinaryTree()
' Construct Binary Tree
' -----------------------
' 15
' / \
' 24 54
' / / \
' 35 62 13
' Add tree nodes
tree.root = New TreeNode(15)
tree.root.left = New TreeNode(24)
tree.root.right = New TreeNode(54)
tree.root.right.right = New TreeNode(13)
tree.root.right.left = New TreeNode(62)
tree.root.left.left = New TreeNode(35)
' Display result
tree.inorder()
End Sub
End Class
Output
35 24 15 62 54 13
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment