Scribd
Upload
28 views3 pages

Trees

A tree is a nonlinear data structure that represents hierarchical relationships, with a root node having no parents and various nodes connected by edges. Key concepts include leaf nodes, siblings, ancestors, descendants, levels, depth, and height. A binary tree is a specific type of tree where each node has up to two children, with variations such as strict, full, and complete binary trees.

Uploaded by

Deborah Sanchez
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views3 pages

Trees

A tree is a nonlinear data structure that represents hierarchical relationships, with a root node having no parents and various nodes connected by edges. Key concepts include leaf nodes, siblings, ancestors, descendants, levels, depth, and height. A binary tree is a specific type of tree where each node has up to two children, with variations such as strict, full, and complete binary trees.

Uploaded by

Deborah Sanchez
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Trees

A tree is a data structure is similar to a linked list but instead of each node pointing
simply to the next node in a linear fashion, each node points to a number of nodes.
Tree is an example of a nonlinear data structure. A tree structure is a way of
representing the hierarchical nature of a structure in a graphical form.

The root of a tree is the node with no parents. There can be at most one root node in
a tree (node A in the above example).

• An edge refers to the link from parent to child (all links in the figure).
• A node with no children is called leaf node (E,J,K,H and I).
• Children of same parent are called siblings (B,C,D are siblings of A, and E,F
are the siblings of B).
• A node p is an ancestor of node q if there exists a path from root to q and p
appears on the path. The node q is called a descendant of p.
• The set of all nodes at a given depth is called the level of the tree (B, C and D
are the same level). The root node is at level zero.
• The depth of a node is the length of the path from the root to the node (depth
of G is 2, A – C – G).
• The height of a node is the length of the path from that node to the deepest
node. The height of a tree is the length of the path from the root to the deepest
node in the tree. A (rooted) tree with only one node (the root) has a height of
zero. In the previous example, the height of B is 2 (B – F – J).
Binary Trees

A tree is called binary tree if each node has zero child, one child or two children.
Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a
root and two disjoint binary trees, called the left and right subtrees of the root.

Types of Binary Trees


Strict Binary Tree: A binary tree is called strict binary tree if each node has exactly
two children or no children.

Full Binary Tree: A binary tree is called full binary tree if each node has exactly two
children and all leaf nodes are at the same level.
Complete Binary Tree: A complete binary tree is a binary tree in which all the levels
are completely filled except possibly the lowest one, which is filled from the left.

You might also like