Tree: Non-Linear Data Structure in which data is organized in a hierarchical manner. It is very fast for information retrieval and searching operations.
Important Terminology of a Binary Tree.
Node: Each element in a tree is called a node.
Edges: Lines connecting two nodes, it is also known as branches.
Parent Node: The immediate predecessor of a node (node that comes just before a node).
Child Node: The immediate successors of a node (node that comes just next in line).
Root Node: The node that doesn't have any parent node.
Leaf Node: The node that doesn't have any child node. The node other than the leaf node is known as a non-leaf or terminal node.
Level: Distance of that node from the root.
Edges: Lines connecting two nodes, it is also known as branches.
Parent Node: The immediate predecessor of a node (node that comes just before a node).
Child Node: The immediate successors of a node (node that comes just next in line).
Root Node: The node that doesn't have any parent node.
Leaf Node: The node that doesn't have any child node. The node other than the leaf node is known as a non-leaf or terminal node.
Level: Distance of that node from the root.
Height: Total number of level, depth of the tree, Level+1=Height
Siblings: All nodes having the same parent. All siblings are at the same level but it is not necessary that nodes at the same level are siblings.
Path: It is a way to reach a node from any other node. In a tree, there is only one path possible between any two nodes. Path length = Number of Edges on the path.
Degree: The number of children or subtrees connected to a node.
Forest: The subtrees we get after removing the root of the main tree is collectively called as Forest (also known as a set of disjoint trees).
Strictly Binary Tree: Each node in the tree is either a leaf node or has exactly two children. There is no node with one child.
Extended Binary tree: Each Empty subtree is replaced by a special node then the resulting tree is extended binary tree or 2-tree.
Full Binary tree: All the levels have the maximum number of nodes.
**If the number of any node is k, then the number of the left child is 2k, the number of right children is 2k+1, and the number of its parent is k/2.
Complete Binary Tree: All the levels have the maximum number of nodes except possibly the last node.
Important Properties of a Binary Tree.
P1. The maximum number of nodes possible on any level i is 2^i where i>=0.
P2. The maximum number of nodes possible in a binary tree of height h is 2^h-1.
P3. The minimum number of nodes possible in a binary tree of height h is equal to h. A tree with a minimum number of nodes is called skew trees.
P4. If a binary tree contains n nodes, then its maximum height possible is n and the minimum height possible is log2(n+1).
P5. In a non-empty binary tree, if n is the total number of nodes and e is the total number of edges, then e = n-1.
P6. In a non-empty binary tree, if n is the number of nodes with no child and m is the number of nodes with 2 children, then n = m+1.
Traversal in Binary Tree
1. Breadth-First Traversal (Level Order Traversal)
2. Depth First Traversal
A. Preorder Traversal (Root, Left, Right)
B. Inorder Traversal (Left, Root, Right)
C. Postorder Traversal (Left, Right, Root)
ليست هناك تعليقات
إرسال تعليق