Please enable JavaScript.

Coggle requires JavaScript to display documents.

CHAPTER 5: TREE, shahrul(slide 13), shahrul(slide 43), AYUNA SLIDE26),…

- - - - complete both of the tree
  - - - a binary tree is complete if all levels except possibly the last are completely full and the last level has all its nodes to the left side
  - - - Internal nodes : operators
      - External nodes : operands
      - Example : : (2 * ( a -1) + (3 x b))
      - Parentheses
      - exponentiation
      - multiplication and division left to right
      - addition and subtration left to right
    - - EXAMPLE
        (2(a-1) + (3xb))*
      - +
        
        x
        
        2
        
        -
        
        1
        
        a
        
        x
        
        3
        
        b
  - - - BINARY TREE
  - - - type of binary tree in which all the nodes have only either one child or no child.
  - - - Has root node
        
        Each node may not have child node, one or more child node
        
        Each node will have one node as parent node except root node
  - - - a tree is a data structure that emulates a hierarchical tree structure with a set of linked nodes to solve problems
      - Node- is a structure which may contain a value, a condition, or represent a separate data structure
      - Types of tree : general tree, binary tree, binary search tree, AVL tree and etc
  - - - 1st key will be the root node
      - Larger keys in all nodes in that node's right subtree
      - Smaller keys in all nodes in that node's left subtree
- - - - INFIX : ( A + B ) * (C + D )
        
        PREFIX : * + A B + C D
        
        POSTFIX : A B + C D + *
      - INFIX : ( A + B C ) + ( ( C E + F ) * G )
        
        PREFIX : + + A B C + * C E F G
        
        POSTFIX : A B C + C E F + G * +
      - INFIX : ( 25 * 3 ) / ( 10 - 5 )
        
        PREFIX : / * 25 3 - 10 5
        
        POSTFIX : 25 3 * 10 5 - /
  - - - Example :
        2+34
        Postfix
        234+
  - - - Example:
        ((-A B)(+(C D) (/E F)))
        
        x
        
        -
        
        A
        
        B
        
        +
        
        x
        
        C
        
        D
        
        /
        
        E
        
        F
    - - 1.First, make parenthesis of two operand that near the operator
        2.Then make parenthesis next two nearest parenthesis with operator until all being parenthesis
        
        A B C D / + E F -
        
        (A B ) (C D / ) + (E F - )
        
        ((A B ) (C D / ) +) (E F - )
    - - (-A B)+(C D) (/ E F)
      - (-A B)(+(C D) ( / E F))
      - - A B + C D / E F
      - ((- A B )(+ ( C D) (/ E F)))
      - make parenthesis of two operand that near the operator
      - Then make parenthesis next two nearest parenthesis with operator until all being parenthesis
  - - - a form of notation for logic, arithmetic, and algebra.
      - Its distinguishing feature is that it places operators to the left of their operands
  - - - The notation commonly used in arithmetical and logical formulae and statements.
      - Characterized by the placement of operators between operands
      - Example : 2 + 2
  - - - we do the same thing as prefix notation but instead of moving the symbol to the position of the left parenthesis, we move it to the right, we get postfix notation
      - Recall that A + B C can be written as (A + (B C))
  - - - (((A B ) (C D / ) +) (E F - ) )
- - - - Pre-Order Traversals
        (Dominic)
        
        In pre-order traversal a node is visited before its left and right sub-tree (VN -> LN -> RN )
        
        From the BST diagram, results from pre-order traversal are as below:
        L -> B -> A -> D -> N -> M -> Y
      - Post-Order Traversals
        (Anding)
        
        In post-order traversal a node is visited after its left and right sub-tree (LN -> RN -> VN)
        
        From the BST diagram, results from post-order traversal are as below:
        A -> D -> B -> M -> Y -> N -> L
      - In Order Traversals
        (Catherine)
        
        In an inorder traversal a node is visited after its left sub-tree and before its right sub-tree (LN ->VN->RN )
        
        From the BST diagram, results from an in-order
        traversal are as below:
        A ->B -> D -> L -> M -> N -> Y
  - - - Clarify node to replace the removing node. Make sure that the characteristic of BST are still implemented.
        
        Clarification based on two way:
        
        Find the largest node from left subtree
        
        Find the smallest node from right subtree
        
        Replace the node that wants to be removed with the node chosen above
  - - - Leaf node can be removed from BST just like that because there’s no relation will be clashed in the BST when removing it.
        Assign NULL value to parent pointer that point to the node that want to be removed