Results 1 to 1 of 1

Math Help - rooted ternary tree

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    6

    rooted ternary tree

    A rooted ternary tree can be de ned by the following recursive de nition.
    basis: The empty tree (containing no nodes) is a ternary tree.
    inductive step: Create a root node r. Let T1; T2; T3 be three disjoint trees (i.e.
    containing no nodes in common with r or one another). For each nonempty Ti,
    connect r to Ti's root ri. r1; r2; r3 are called r's children.
    A leaf is a node with no children. An internal node is a non-leaf node.
    (a) The height of a tree is the maximum length of a path from the root to a leaf. The length
    of a path is 1 less than the number of nodes it contains. What is the minimum height of
    a ternary tree with ` leaves? Prove, using strong induction, that your answer is correct.
    (b) A strict ternary tree is a ternary tree where each node has either exactly three children
    or no children. Prove, using structural induction, that, in any nonempty strict ternary
    tree, the number of leaves is equal to one plus twice the number of internal nodes. In
    other words, if `(t) is the number of leaves in the tree t and k(t) is the number of internal
    nodes, then `(t) = 2k(t) + 1.
    Last edited by CaptainBlack; February 9th 2010 at 04:10 AM. Reason: restored deleted question
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. rooted tree
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2010, 04:21 PM
  2. Rooted Trees
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 1st 2010, 11:55 AM
  3. intergrating of rooted function
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: May 1st 2009, 06:28 AM
  4. Components of Algebra rooted in pre-cal?
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: June 3rd 2008, 05:20 PM
  5. Cube rooted integral
    Posted in the Calculus Forum
    Replies: 5
    Last Post: December 15th 2007, 07:50 AM

Search Tags


/mathhelpforum @mathhelpforum