Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    Binary Tree Properties & Representation

    Uploaded by

    kn_bs
    Binary tree properties and representation are discussed. A binary tree with n nodes has a height between log2(n+1) and n. Binary trees can be represented using arrays or linked nodes. Array representation numbers nodes from 1 to 2h-1 and stores the element of node i in tree[i]. Linked representation uses BinaryTreeNode objects with left/right child and element references. Common binary tree operations involve traversing the tree in preorder, inorder, postorder or level order.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Binary Tree Properties & Representation

    Uploaded by

    kn_bs
    29 views20 pages
    Binary tree properties and representation are discussed. A binary tree with n nodes has a height between log2(n+1) and n. Binary trees can be represented using arrays or linked nodes. Array representation numbers nodes from 1 to 2h-1 and stores the element of node i in tree[i]. Linked representation uses BinaryTreeNode objects with left/right child and element references. Common binary tree operations involve traversing the tree in preorder, inorder, postorder or level order.

    Original Title

    lec20

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary tree properties and representation are discussed. A binary tree with n nodes has a height between log2(n+1) and n. Binary trees can be represented using arrays or linked nodes. Array representation numbers nodes from 1 to 2h-1 and stores the element of node i in tree[i]. Linked representation uses BinaryTreeNode objects with left/right child and element references. Common binary tree operations involve traversing the tree in preorder, inorder, postorder or level order.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    29 views20 pages

    Binary Tree Properties & Representation

    Uploaded by

    kn_bs
    Binary tree properties and representation are discussed. A binary tree with n nodes has a height between log2(n+1) and n. Binary trees can be represented using arrays or linked nodes. Array representation numbers nodes from 1 to 2h-1 and stores the element of node i in tree[i]. Linked representation uses BinaryTreeNode objects with left/right child and element references. Common binary tree operations involve traversing the tree in preorder, inorder, postorder or level order.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 20

    Binary Tree Properties & Representation

    Minimum Number Of Nodes


    • Minimum number of nodes in a binary tree whose height is h.
    • At least one node at each of first h levels.

    minimum number of
    nodes is h
    Maximum Number Of Nodes
    • All possible nodes at first h levels are present.

    Maximum number of nodes


    = 1 + 2 + 4 + 8 + … + 2h-1
    = 2h - 1
    Number Of Nodes & Height

    • Let n be the number of nodes in a binary


    tree whose height is h.
    • h <= n <= 2h – 1
    • log2(n+1) <= h <= n
    Full Binary Tree
    • A full binary tree of a given height h has 2h – 1
    nodes.

    Height 4 full binary tree.


    Numbering Nodes In A Full Binary
    Tree
    • Number the nodes 1 through 2h – 1.
    • Number by levels from top to bottom.
    • Within a level number from left to right.
    1

    2 3

    4 5 6 7
    8 9 10 11 12 13 14 15
    Node Number Properties
    1

    2 3

    4 5 6 7
    8 9 10 11 12 13 14 15

    • Parent of node i is node i / 2, unless i = 1.


    • Node 1 is the root and has no parent.
    Node Number Properties
    1

    2 3

    4 5 6 7
    8 9 10 11 12 13 14 15

    • Left child of node i is node 2i, unless 2i > n,


    where n is the number of nodes.
    • If 2i > n, node i has no left child.
    Node Number Properties
    1

    2 3

    4 5 6 7
    8 9 10 11 12 13 14 15

    • Right child of node i is node 2i+1, unless 2i+1


    > n, where n is the number of nodes.
    • If 2i+1 > n, node i has no right child.
    Complete Binary Tree With n Nodes

    • Start with a full binary tree that has at least


    n nodes.
    • Number the nodes as described earlier.
    • The binary tree defined by the nodes
    numbered 1 through n is the unique n node
    complete binary tree.
    Example
    1

    2 3

    4 5 6 7
    8 9 10 11 12 13 14 15

    • Complete binary tree with 10 nodes.


    Binary Tree Representation

    • Array representation.
    • Linked representation.
    Array Representation
    • Number the nodes using the numbering scheme
    for a full binary tree. The node that is numbered
    i is stored in tree[i].
    a1

    2 3
    b c

    4 5 6 7
    d e f g
    8 9 10
    h i j

    tree[] a b c d e f g h i j
    0 5 10
    Right-Skewed Binary Tree
    a1
    b 3
    7
    c
    15
    d

    tree[] a - b - - - c - - - - - - - d
    0 5 10 15

    • A n n node bina ry tre e ne e ds a n ar r ay w hose le ngth is betwe e n n+ 1 a nd 2 n.


    Linked Representation

    • Each binary tree node is represented as an object whose data type is


    BinaryTreeNode.
    • The space required by an n node binary tree is n * (space required by one
    node).
    The Class BinaryTreeNode
    package dataStructures;
    public class BinaryTreeNode
    {
    Object element;
    BinaryTreeNode leftChild; // left subtree
    BinaryTreeNode rightChild;// right subtree
    // constructors and any other methods
    // come here
    }
    Linked Representation Example
    root a

    b c

    d e

    g
    f
    leftChild
    element h
    rightChild
    Some Binary Tree Operations
    • Determine the height.
    • Determine the number of nodes.
    • Make a clone.
    • Determine if two binary trees are clones.
    • Display the binary tree.
    • Evaluate the arithmetic expression
    represented by a binary tree.
    • Obtain the infix form of an expression.
    • Obtain the prefix form of an expression.
    • Obtain the postfix form of an expression.
    Binary Tree Traversal
    • Many binary tree operations are done by
    performing a traversal of the binary tree.
    • In a traversal, each element of the binary tree is
    visited exactly once.
    • During the visit of an element, all action (make
    a clone, display, evaluate the operator, etc.)
    with respect to this element is taken.
    Binary Tree Traversal Methods

    • Preorder
    • Inorder
    • Postorder
    • Level order

    You might also like