Page 214 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 12: Introduction to Trees

12.4 Summary Notes

Tree is a data structure which allows you to associate a parent-child relationship between
various pieces of data and thus allows us to arrange our records, data and files in a
hierarchical fashion.
A node is a structure which may contain a value, a condition, or represent a separate data
structure.
The top most element is called the “root”. The nodes with no children are called “Leaf”
nodes.
Any Tree whose nodes can have at the most two children is called a Binary tree or a tree
with order 2.

The binary tree creation follows a very simple principle — for the new element to be
added, compare it with the current element in the tree.
When a binary tree is represented by arrays three separate arrays are required. One array
stores the data fields of the trees.
Binary trees can be represented by links, where each node contains the address of the left
child and the right child.

The process of systematically visiting all the nodes in a tree and performing some
computation at each node in the tree is called a tree traversal.

A Threaded Binary Tree is a binary tree in which every node that does not have a right
child has a THREAD (in actual sense, a link) to its INORDER successor.

12.5 Keywords

Binary Tree: Any Tree whose nodes can have at the most two children is called a Binary tree or
a tree with order 2.
Internal Node: An internal node or inner node is any node of a tree that has child nodes and is
thus not a leaf node.
Leaf Nodes: Nodes that do not have any children are called leaf nodes.
Node: A node is a structure which may contain a value, a condition, or represent a separate data
structure.
Root Node: The topmost node in a tree is called the root node.
Threaded Binary Tree: A Threaded Binary Tree is a binary tree in which every node that does not
have a right child has a THREAD to its INORDER successor.
Tree Traversal: The process of systematically visiting all the nodes in a tree and performing
some computation at each node in the tree is called a tree traversal.

Tree: Tree is a data structure which allows you to associate a parent-child relationship between
various pieces of data.

12.6 Review Questions

1. Explain the concept of trees with example.

2. Discuss the terminologies related to trees.

LOVELY PROFESSIONAL UNIVERSITY 207