UNIT-4 TREE
UNIT-4 and 5 TREES
Tree represents the nodes connected by edges. We will discuss binary tree or binary
search tree specifically.
Binary Tree is a special datastructure used for data storage purposes. A binary tree
has a special condition that each node can have a maximum of two children. A binary
tree has the benefits of both an ordered array and a linked list as search is as quick as
in a sorted array and insertion or deletion operation are as fast as in linked list.
Important Terms
Following are the important terms with respect to tree.
Path − Path refers to the sequence of nodes along the edges of a tree.
Root − The node at the top of the tree is called root. There is only one root per
tree and one path from the root node to any node.
Parent − Any node except the root node has one edge upward to a node called
parent.
Child − The node below a given node connected by its edge downward is called
its child node.
Leaf − The node which does not have any child node is called the leaf node.
Subtree − Subtree represents the descendants of a node.
BY- SONAM TOMAR
,UNIT-4 TREE
Visiting − Visiting refers to checking the value of a node when control is on the
node.
Traversing − Traversing means passing through nodes in a specific order.
Levels − Level of a node represents the generation of a node. If the root node is
at level 0, then its next child node is at level 1, its grandchild is at level 2, and so
on.
keys − Key represents a value of a node based on which a search operation is
to be carried out for a node.
Binary Search Tree Representation
Binary Search tree exhibits a special behavior. A node's left child must have a value
less than its parent's value and the node's right child must have a value greater than its
parent value.
We're going to implement tree using node object and connecting them through
references.
Tree Node
The code to write a tree node would be similar to what is given below. It has a data part
and references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
In a tree, all nodes share common construct.
BST Basic Operations
The basic operations that can be performed on a binary search tree data structure, are
the following −
BY- SONAM TOMAR
, UNIT-4 TREE
Insert − Inserts an element in a tree/create a tree.
Search − Searches an element in a tree.
Preorder Traversal − Traverses a tree in a pre-order manner.
Inorder Traversal − Traverses a tree in an in-order manner.
Postorder Traversal − Traverses a tree in a post-order manner.
Algebraic Expression using Binary Tree Consider any algebraic expression E involving only
binary operations, such as E = (a – b) / ((c * d) + e) E can be represented by means of the
binary tree T as shown below. That is, each variable, or constant in E appears as an “internal”
node in T whose left and right subtrees correspond to the operands of the operation. For
example: a) In the expression E, the operands of + are c * d and e. b) In the tree T, the
subtrees of the node + correspond to the expression c * d and e
Representing Binary Trees in Memory Let T be a binary tree. There are two ways of representing T in
memory. The first and usual way is called the link representation of T and is analogous to the way
linked lists are represented in memory. The second way, which uses a single array, called the
sequential representation of T. The main requirement of any representation of T is that one should
have direct access to the root R of T and, given any node N of T, one should have direct access to the
children of N. Linked Representation of Binary Trees Consider a binary tree T. Unless otherwise stated
or implied, T will be maintained in memory by means of a linked representation which uses three
parallel arrays, INFO, LEFT and RIGHT, and a pointer variable ROOT as follows. First of all, each node N
of T will correspond to a location K such that:
1) INFO [K] contains the data at the node N.
2) LEFT [K] contains the location of the left child of node N.
3) RIGHT [K] contains the location of the right child of node N.
Furthermore, ROOT will contain the location of the root R of T. If any subtree is empty, then the
corresponding pointer will contain the null value; if the tree T itself is empty, then ROOT will contain
the null value.
Insert Operation
The very first insertion creates the tree. Afterwards, whenever an element is to be
inserted, first locate its proper location. Start searching from the root node, then if the
data is less than the key value, search for the empty location in the left subtree and
insert the data. Otherwise, search for the empty location in the right subtree and insert
the data.
BY- SONAM TOMAR
UNIT-4 and 5 TREES
Tree represents the nodes connected by edges. We will discuss binary tree or binary
search tree specifically.
Binary Tree is a special datastructure used for data storage purposes. A binary tree
has a special condition that each node can have a maximum of two children. A binary
tree has the benefits of both an ordered array and a linked list as search is as quick as
in a sorted array and insertion or deletion operation are as fast as in linked list.
Important Terms
Following are the important terms with respect to tree.
Path − Path refers to the sequence of nodes along the edges of a tree.
Root − The node at the top of the tree is called root. There is only one root per
tree and one path from the root node to any node.
Parent − Any node except the root node has one edge upward to a node called
parent.
Child − The node below a given node connected by its edge downward is called
its child node.
Leaf − The node which does not have any child node is called the leaf node.
Subtree − Subtree represents the descendants of a node.
BY- SONAM TOMAR
,UNIT-4 TREE
Visiting − Visiting refers to checking the value of a node when control is on the
node.
Traversing − Traversing means passing through nodes in a specific order.
Levels − Level of a node represents the generation of a node. If the root node is
at level 0, then its next child node is at level 1, its grandchild is at level 2, and so
on.
keys − Key represents a value of a node based on which a search operation is
to be carried out for a node.
Binary Search Tree Representation
Binary Search tree exhibits a special behavior. A node's left child must have a value
less than its parent's value and the node's right child must have a value greater than its
parent value.
We're going to implement tree using node object and connecting them through
references.
Tree Node
The code to write a tree node would be similar to what is given below. It has a data part
and references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
In a tree, all nodes share common construct.
BST Basic Operations
The basic operations that can be performed on a binary search tree data structure, are
the following −
BY- SONAM TOMAR
, UNIT-4 TREE
Insert − Inserts an element in a tree/create a tree.
Search − Searches an element in a tree.
Preorder Traversal − Traverses a tree in a pre-order manner.
Inorder Traversal − Traverses a tree in an in-order manner.
Postorder Traversal − Traverses a tree in a post-order manner.
Algebraic Expression using Binary Tree Consider any algebraic expression E involving only
binary operations, such as E = (a – b) / ((c * d) + e) E can be represented by means of the
binary tree T as shown below. That is, each variable, or constant in E appears as an “internal”
node in T whose left and right subtrees correspond to the operands of the operation. For
example: a) In the expression E, the operands of + are c * d and e. b) In the tree T, the
subtrees of the node + correspond to the expression c * d and e
Representing Binary Trees in Memory Let T be a binary tree. There are two ways of representing T in
memory. The first and usual way is called the link representation of T and is analogous to the way
linked lists are represented in memory. The second way, which uses a single array, called the
sequential representation of T. The main requirement of any representation of T is that one should
have direct access to the root R of T and, given any node N of T, one should have direct access to the
children of N. Linked Representation of Binary Trees Consider a binary tree T. Unless otherwise stated
or implied, T will be maintained in memory by means of a linked representation which uses three
parallel arrays, INFO, LEFT and RIGHT, and a pointer variable ROOT as follows. First of all, each node N
of T will correspond to a location K such that:
1) INFO [K] contains the data at the node N.
2) LEFT [K] contains the location of the left child of node N.
3) RIGHT [K] contains the location of the right child of node N.
Furthermore, ROOT will contain the location of the root R of T. If any subtree is empty, then the
corresponding pointer will contain the null value; if the tree T itself is empty, then ROOT will contain
the null value.
Insert Operation
The very first insertion creates the tree. Afterwards, whenever an element is to be
inserted, first locate its proper location. Start searching from the root node, then if the
data is less than the key value, search for the empty location in the left subtree and
insert the data. Otherwise, search for the empty location in the right subtree and insert
the data.
BY- SONAM TOMAR
