Page 217 - DCAP407_DATA_STRUCTURE

Data Structure

Write a C program to represent the linked list representation of binary tree into
sequential representation.

11.4 Summary
• A binary tree is a finite set of data elements and each node contains a maximum of two branches.
• A tree is known as a complete binary tree if each of its level, except the last level, is completely
filled with child nodes.
• A binary tree is called a strictly binary tree when the non-terminal nodes have exactly two child
nodes forming left and the right sub-trees.
• In an extended binary tree, the nodes possessing only one child node can be extended with one
more child node.
• The binary tree can be represented as array as well as linked list.

• In a threaded binary tree, the pointers are represented as threads such that the threads point to the
node in the binary tree for any operations.
11.5 Keywords

Leaf Nodes: The nodes without any successors.
Node Predecessor: Node representing the parent node.
Node Successor: Node representing the child node.
Threads: The pointer linking the other nodes in the tree.
11.6 Self Assessment

1. State whether the following statements are true or false:
(a) The strictly binary tree can have any number of children.
(b) In a binary tree, at level 1, there must be only one node known as root node.
(c) In an array representation, the size of tree is restricted according to the memory allocation.
(d) In sequential representation, the level of the nodes starts with level one that contains the root
node.
2. Fill in the blanks:
(a) The …………………… binary tree helps in mapping the nodes easily.
(b) The data in …………………… representation is stored without any help of pointers.
(c) In the threaded binary tree, the NULL links are replaced by pointers known as ……………

3. Select a suitable choice for every question:
(a) In which representation the memory allocation is restricted to the size of the tree?
(i) Sequential (ii) Linked list
(b) Which among the following technique is used to allocate memory to a node using linked list?
(i) Dynamic allocation (ii) Sequential allocation

210 LOVELY PROFESSIONAL UNIVERSITY