[go: up one dir, main page]
Scribd
Upload
43 views3 pages

DS Definition - Chapter 8

Trees are hierarchical data structures that store data hierarchically with nodes connected by edges. A tree has a root node with zero or more subtrees, where each subtree is also a tree. There are different types of trees including binary trees where each node has at most two children, binary search trees where nodes are ordered by key values, and heaps which are complete binary trees where a node's children have larger or smaller keys. Tree traversal involves visiting each node exactly once using techniques like depth-first search (inorder, preorder, postorder) and breadth-first search (level order).

Uploaded by

Naing Oo
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
43 views3 pages

DS Definition - Chapter 8

Trees are hierarchical data structures that store data hierarchically with nodes connected by edges. A tree has a root node with zero or more subtrees, where each subtree is also a tree. There are different types of trees including binary trees where each node has at most two children, binary search trees where nodes are ordered by key values, and heaps which are complete binary trees where a node's children have larger or smaller keys. Tree traversal involves visiting each node exactly once using techniques like depth-first search (inorder, preorder, postorder) and breadth-first search (level order).

Uploaded by

Naing Oo
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
You are on page 1/ 3

CHAPTER 8

1. Tree
➢ Trees are very flexible, versatile and powerful non-linear data structure that can be
used to represent data items possessing a hierarchical relationship among the nodes of
the tree.
➢ A Tree may be defined as a non-empty finite set of nodes, such that,
o There is a specially designated node called the root,
o The remaining nodes are partitioned into zero or more disjoint trees T1, T2 …Tn
are called the subtrees of the root R.

2. Terminology of Tree
➢ Node (or vertex): A node stands for the item of information with the branches to other
items.
➢ Root: A node without any parent is called root node.
➢ Parent node: Also called Predecessor or Ancestor.
➢ Child node: Also called Successor or Descendant.
➢ Siblings: The children (or the nodes) of the same parent are said to be siblings.
➢ The degree of a node: The number of subtrees (or children) of a node is called its degree.
➢ The degree of tree: The degree of a tree is the maximum degree of the nodes in the tree.
➢ Internal node (or non-terminal node): The node with at least one child is called internal
nodes.
➢ External nodes (or leaf node): The nodes that have degree zero are called external node
or leaf or terminal nodes.
➢ Level: The level of a node is defined as follows:
i) The root of the tree is at level one.
ii) If a node is at level L, then its children are at level L + 1.
➢ Height (or depth): The height or depth of a tree is defined to be the maximum level of
any node in the tree.
➢ Forest: A forest is a set of zero or more disjoint trees. The removal of the root node
from a tree result in a forest.
➢ Edge: The line from a node N in the tree to a successor is called an edge.
➢ Path and path length: A sequence of consecutive edges from the source node to the
destination node is called a path. The number of edges in a path is path length.
➢ Internal path length: The sum of the levels of all the internal nodes in the tree is called
internal path length.
➢ External path length: The sum of the levels of all the external nodes in the tree is called
external path length.
➢ Branch: A path ending in a leaf node is called a branch.

3. Binary Tree and Types?


➢ A binary tree is a finite set of nodes, which is either empty or consists of a root and
two disjoint binary trees called left subtree and the right subtree.
➢ A binary tree is a special case of an ordered k-array tree, where k is 2.
➢ Common Types of Binary Trees are as follows:
1. Strictly Binary Tree 6. Binary Expression Tree
2. Extended Binary Tree 7. Balanced Binary Tree
3. Complete Binary Tree 8. Threaded Binary Tree
4. Full Binary Tree 9. Binary Search Trees
5. Skewed Binary Tree

4. Binary Tree Traversal and Explain?


➢ Tree traversal is the operation of visiting each node in the tree exactly once. There
are mainly two traversals are:
➢ Depth First Search (DFS)
In depth first search, starting from the root of the binary tree, there are three main
traversal that can be performed.
1. Inorder
2. Preorder
3. Postorder
➢ Breadth First Search (BFS)
In breadth first search, binary trees can also be traversed in level-order, where every
node are visited on a level before the next level.
5. Heap and Types?
➢ Heap is a binary tree that must satisfy the following properties.
o The binary tree essentially complete that means the tree completely filled all
levels, the last level may be partially filled from left to right, and some
rightmost leaves may be missing.
o All keys in the tree, other than the root node, are greater/smaller than or equal
to the key in the parent node.
➢ There are two types of the heap:
i) Max Heap
ii) Min Heap

6. Binary Search Tree


➢ A Binary search tree (BST) is an ordered binary tree, which is either empty or each
node in the tree contains a key and
i) All keys in the left subtree are less than the keys in the root node,
ii) All keys in the right subtree are greater than the keys in the root node,
iii) The left and right subtrees are also binary search tree.

You might also like