Until now, we have dealt with linear structures such as arrays, linked lists, stacks, and queues. A tree is a nonlinear data structure where members may have multiple successors.
Trees are data structures that are made up of nodes.
We must define several terms before getting into the actual implementations of trees. If A is a root node, then A has no ancestors. If A is not a root node, then the parent of A and all ancestors of A's parent are ancestors of A. descendants - Let B be an arbitrary node of a tree. If B is a leaf, then B has no descendants. If B is not a leaf, then each child of B and all descendants of each child of B are descendants of B. subtree - an arbitrary node in the tree and all descendants of that node.