poltadam.blogg.se - Binary tree java tutorial

#Binary tree java tutorial pdf#

Storing information that we want to search quickly.

#Binary tree java tutorial pdf#

File systems on a computer and PDF use tree structures. Storing information that naturally occurs in a hierarchy. Trees form some of the most basic organization of computers. The hierarchical structure gives a tree unique properties for storing, manipulating, and accessing data. The height of a tree is the height of its root node.ĭegree: The degree of a node refers to the number of sub-trees.

Think of this as how many steps there are between your node and the tree’s endpoint. Height: The height of a node is the number of edges in the longest path from a node to a leaf node. Think of this as how many steps there are between your node and the tree’s starting point. The root of that tree can be any node from the bigger tree.ĭepth: The depth of a node is the number of edges between that node and the root. Subtree: A subtree is a smaller tree held within a larger tree. Think of this as an endpoint of your tree. Leaf: A leaf has a parent node but has no outgoing link to a child node. Parent: The parent node has an outgoing link connecting it to one or more child nodes. If two children nodes share the same parent, they are called siblings. Think of this as a starting point of your tree.Ĭhildren: The child of a tree is a node with one incoming link from a node above it (i.e. Root: The root of a tree is a node that has no incoming link (i.e. What are the different components of a tree? Trees are similar to graphs, but a cycle cannot exist in a tree. A node contains data of any type, but all the nodes must be of the same data type. Else, insert element as right child of current root.Trees are a collection of nodes (vertices), and they are linked with edges (pointers), representing the hierarchical connections between the nodes. If the data of the root node is greater, and if a right subtree exists, then repeat step 2 with root = root of right subtree.Else, insert element as left child of current root. If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree.This is an important property of a BST.Ĭonsider the insertion of $$data = 20$$ in the BST.Ĭompare data of the root node and element to be inserted. The in-order traversal of a BST gives a sorted ordering of the data elements that are present in the BST. After right subtree of this node is completely processed, entire traversal of the BST is complete.Right subtree of this node gets processed in a similar way as described until step 10.Now, node with $$data = 10$$ is processed.'inorder(6)' is then completed.īoth the left and right subtrees of node with $$data = 5$$ have been completely processed. The notation has been used for brevity.Īgain, the node with $$data = 6$$ has no left subtree, Therefore, it can be processed and it also has no right subtree. 'inorder(6)' is only equivalent to saying inorder(pointer to node with $$data = 6$$). Hence, the right subtree gets processed now.

Right subtree of this node with $$data = 5$$ is non-empty.

Left subtree of node with $$data = 5$$ is completely processed.

inorder(1) gets completed and this function call is popped from the call stack.

Node with $$data = 1$$ does not have a right subtree.

Node with $$data = 1$$ does not have a left subtree.

Again, the node has a left subtree, so 'inorder( )' is called with $$root = 1$$.

Since the node has a left subtree, 'inorder( )' is called with root equal to node with $$data = 5$$.

The 'inorder( )' procedure is called with root equal to node with $$data = 10$$.

Inorder(root->right) //Go to right subtreeĬonsider the in-order traversal of a sample BST

First process left subtree (before processing root node).

Postorder(root->right) //Go to right sub tree Postorder(root->left) //Go to left sub tree In this traversal technique the traversal order is left-right-root. Preorder(root->right) //Go to right subtree Preorder(root->left) //Go to left subtree Printf("%d ",root->data) //Printf root->data

First, traverse left subtree completely.

In this traversal technique the traversal order is root-left-right i.e. There are mainly three types of tree traversals. The tree is known as a Binary Search Tree or BST. When recursive, all subtrees satisfy the left and right subtree ordering. Similarly, the root node with $$data = 19$$ also satisfies this ordering.

Data in the right subtree is: $$$$Īlso, considering the root node with $$data = 5$$, its children also satisfy the specified ordering.

1, consider the root node with data = 10. The data of all the nodes in the right subtree of the root node should be $$\gt$$ the data of the root. For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be $$\le$$ the data of the root.