Nothing Special   »   [go: up one dir, main page]
SlideShare a Scribd company logo

Graph and tree

•Download as PPTX, PDF•
•
Imran Hossain
Imran Hossain

The document defines and provides examples of different tree data structures: - A graph is a set of objects connected by links, with the objects called nodes and links called edges. - A tree is a type of graph where any two vertices are connected by exactly one path, and has properties like a root node, internal/external nodes, ancestors and descendants. - Binary trees restrict each internal node to have at most two children, ordered as left and right. Binary search trees and heap trees are examples of binary trees. - Traversals like preorder, inorder and postorder visit the nodes of a tree systematically.

1 of 19
Download to read offline
Graph and tree
Graph and tree
 A graph is a representative a set of objects where some pairs of objects are connected links.  The interconnected objects are called vertex or nodes And that links are called edges lines. 0 1 4 3 2
Graph and tree
 0 1 2 3 4  0 0 1 0 0 1  1 1 0 1 1 1  2 0 1 0 1 0  3 0 1 1 0 1 0 2 1 34
0 2 1 34 0 1 3 2 4 1 4 0 2 1 3 3 4 1 2 0 1 4 3
Graph and tree
subtree  Root: node without parent (A)  Siblings: nodes share the same parent  Internal node: node with at least one child (A, B, C, F)  External node (leaf ): node without children (E, I, J, K, G, H, D)  Ancestors of a node: parent, grandparent, grand-grandparent, etc.  Descendant of a node: child, grandchild, grand-grandchild, etc.  Depth of a node: number of ancestors  Height of a tree: maximum depth of any node (3)  Degree of a node: the number of its children  Degree of a tree: the maximum number of its node. A B DC G HE F I J K Subtree: tree consisting of a node and its descendants
 Three main methods:  Preorder  Postorder  Inorder  Preorder:  visit the root  traverse in preorder the children (subtrees)  Postorder  traverse in postorder the children (subtrees)  visit the root
 A traversal visits the nodes of a tree in a systematic manner  In a preorder traversal, a node is visited before its descendants  Application: print a structured document Become Rich 1. Motivations 3. Success Stories2. Methods 2.1 Get a CS PhD 2.2 Start a Web Site 1.1 Enjoy Life 1.2 Help Poor Friends 2.3 Acquired by Google 1 2 3 5 4 6 7 8 9
 In a postorder traversal, a node is visited after its descendants  Application: compute space used by files in a directory and its subdirectories cs16/ homeworks/ todo.txt 1K programs/ DDR.java 10K Stocks.java 25K h1c.doc 3K h1nc.doc 2K Robot.java 20K 9 3 1 7 2 4 5 6 8
 A binary tree is a tree with the following properties:  Each internal node has at most two children (degree of two)  The children of a node are an ordered pair  We call the children of an internal node left child and right child  Alternative recursive definition: a binary tree is either  a tree consisting of a single node, OR  a tree whose root has an ordered pair of children, each of which is a binary tree Applications: arithmetic expressions decision processes searching A B C F GD E H I
Examples of the Binary Tree A B C GE I D H F Complete Binary Tree 1 2 3 4 A B A B Skewed Binary Tree E C D 5
Binary search tree : binary search tree a particular type of containers: data structures that store items in memory.
HEAP TREE:A binary heap is a complete binary tree which satisfies the heap ordering property.
Graph and tree
Graph and tree
Graph and tree
Graph and tree

More Related Content

Graph and tree

  • 3.  A graph is a representative a set of objects where some pairs of objects are connected links.  The interconnected objects are called vertex or nodes And that links are called edges lines. 0 1 4 3 2
  • 5.  0 1 2 3 4  0 0 1 0 0 1  1 1 0 1 1 1  2 0 1 0 1 0  3 0 1 1 0 1 0 2 1 34
  • 6. 0 2 1 34 0 1 3 2 4 1 4 0 2 1 3 3 4 1 2 0 1 4 3
  • 8. subtree  Root: node without parent (A)  Siblings: nodes share the same parent  Internal node: node with at least one child (A, B, C, F)  External node (leaf ): node without children (E, I, J, K, G, H, D)  Ancestors of a node: parent, grandparent, grand-grandparent, etc.  Descendant of a node: child, grandchild, grand-grandchild, etc.  Depth of a node: number of ancestors  Height of a tree: maximum depth of any node (3)  Degree of a node: the number of its children  Degree of a tree: the maximum number of its node. A B DC G HE F I J K Subtree: tree consisting of a node and its descendants
  • 9.  Three main methods:  Preorder  Postorder  Inorder  Preorder:  visit the root  traverse in preorder the children (subtrees)  Postorder  traverse in postorder the children (subtrees)  visit the root
  • 10.  A traversal visits the nodes of a tree in a systematic manner  In a preorder traversal, a node is visited before its descendants  Application: print a structured document Become Rich 1. Motivations 3. Success Stories2. Methods 2.1 Get a CS PhD 2.2 Start a Web Site 1.1 Enjoy Life 1.2 Help Poor Friends 2.3 Acquired by Google 1 2 3 5 4 6 7 8 9
  • 11.  In a postorder traversal, a node is visited after its descendants  Application: compute space used by files in a directory and its subdirectories cs16/ homeworks/ todo.txt 1K programs/ DDR.java 10K Stocks.java 25K h1c.doc 3K h1nc.doc 2K Robot.java 20K 9 3 1 7 2 4 5 6 8
  • 12.  A binary tree is a tree with the following properties:  Each internal node has at most two children (degree of two)  The children of a node are an ordered pair  We call the children of an internal node left child and right child  Alternative recursive definition: a binary tree is either  a tree consisting of a single node, OR  a tree whose root has an ordered pair of children, each of which is a binary tree Applications: arithmetic expressions decision processes searching A B C F GD E H I
  • 13. Examples of the Binary Tree A B C GE I D H F Complete Binary Tree 1 2 3 4 A B A B Skewed Binary Tree E C D 5
  • 14. Binary search tree : binary search tree a particular type of containers: data structures that store items in memory.
  • 15. HEAP TREE:A binary heap is a complete binary tree which satisfies the heap ordering property.