Page 117 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes q = new(tnode);

q->data = p->data;
q->lchild = copytree(p->lchild);
q->rchild = copytree(p->rchild);
return(q);
}
}
}
d

5.6 Summary

z A tree is a set of one or more nodes T such that there is a specially designated node called
root, and remaining nodes are partitioned into disjoint set of nodes.
z The degree of a node of a tree is the number of sub-trees having this node as a root, or it is a
number of decedents of a node. If degree is zero then it is called terminal node or leaf node
of a tree.

z Degree of a tree is defined as the maximum of degree of the nodes of the tree.
z A tree non of whose nodes has more than N children is known as N-ary tree. In other
words, an N-ary tree is a tree whose degree is at the most N. Binary tree is a special type of
tree having degree 2.
z A binary tree of depth k can have maximum 2k-1 number of nodes. If a binary tree has
fewer than 2k-1 nodes, it is not a full binary tree.

5.7 Keywords

Degree of a tree: The highest degree of a node appearing in the tree.
Inorder: A tree traversing method in which the tree is traversed in the order of left-tree, node and
then right-tree.
Level of a node: The number of nodes that must be traversed to reach the node from the root.
Node: A data structure that holds information and links to other nodes.
Postorder: A tree traversing method in which the tree is traversed in the order of left-tree, right-
tree and then node.
Preorder: A tree traversing method in which the tree is traversed in the order of node, left-tree
and then right-tree.

Root node: The node in a tree which does not have a parent node.
Tree: A two-dimensional data structure comprising of nodes where one node is the root and rest
of the nodes form two disjoint sets each of which is a tree.

112 LOVELY PROFESSIONAL UNIVERSITY