Tree (Data Structure & Discrete Mathematics)

Tree (Data Structure & Discrete Mathematics)

• 1.
  Title Layout • Subtitle
• 2.
  Course: CSE131 (DiscreteMathematics) Course Teacher: Ms. Shadaab Kawnain Bashir (SKB) Section: P Group: A Depertment: CSE(43 Batch) Group Members: 01. Md. Ashaf Uddaula (161-15-7473) 02. Alamin Hossain (161-15-7483) 03. Md. Khasrur Rahman (161-15-7214) 04. Ijaz Ahmed Utsa (161-15-7180)
• 3.
  Going to TellAbout……. Definition of Tree Basic Terminology of Tree Classification of Tree M-ary Tree Full M-ary Tree Binary Tree Strictly Binary Tree (SBT) Complete Binary Tree (CBT) Almost Binary Tree (ALT) Ordered Rooted Tree Decision Tree Traversing Binary Tree
• 4.
  What is Tree? •An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. • Every Tree is a Graph ,but every Graph is not a tree.
• 5.
  Basic Terminology ofTree  Node  Edge  Root  Leaf Node  Depth  Height  Parent  Children  Siblings  Ancestors  Descendants  Sub-Tree
• 6.
  Basic Terminology ofTree Node: A node is a fundamental part of a tree. Each letter represents one node. Edge: The arrows from one node to another are called edges.
• 7.
  Basic Terminology ofTree Root: The root of the tree is the only node in the tree that has no incoming edges. Here, a is the root. Leaf Node: A leaf node is a node that has no children. The bottom nodes (with no outgoing edges) are the leaves . Here, c , i , j , k , l , m are leaves Node.
• 8.
  Basic Terminology ofTree Depth: Depth tells the number of steps (nodes) to get from a node back to the root. Height: The height of a tree is equal to the maximum level of any node in the tree. This tree has height 5, so the maximum depth is 4 (height - 1).
• 9.
  Basic Terminology ofTree Parent:  a is the parent of b , c , d  b is the parent of e  d is the parent of f , g , h  e is the parent of i , j  f is the parent of k  h is the parent of l , m Siblings:  b , c , d are siblings of each other  f , g , h are siblings of each other  i , j are siblings of each other  l , m are siblings of each other Children:  b , c , d are children of a  f , g , h are children of d  e is the children of b  i , j are the children of e  k is the children of f  l , m are the children of h
• 10.
  Basic Terminology ofTree
• 11.
  Basic Terminology ofTree • Sub-Tree: A sub-tree of a given node includes one of its children and all of that child's descendants.
• 12.
  Classification of Tree
• 13.
  m-ary tree :A rooted tree is called an m-ary tree if every internal vertex has no more than m children. full m-ary tree :A tree is called a full m-ary tree if every internal vertex has exactly m children. binary tree :An m-ary tree with m  2 is called a binary tree
• 14.
  Strictly Binary Tree(SBT) • The tree is said to be strictly binary tree , if every non-leaf node made in a binary tree has non empty left & right sub-tree. • A strictly binary tree with n leaves node always contains 2n-1 nodes.
• 15.
  Complete Binary Tree(CBT) • . A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• 16.
  Almost Binary Tree(ALT) • An almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.
• 17.
  Decision Tree • Adecision tree is a decision support tool that uses atree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm.
• 18.
  Traversing Binary Tree Traversalin Binary Tree Pre-order Traversal In-order Traversal Post-order Traversal