Podcast
Questions and Answers
What is the number of vertices in a full m-ary tree with I internal vertices and L leaves?
What is the number of vertices in a full m-ary tree with I internal vertices and L leaves?
- I + L - 1
- I × L - 1
- m × I + 1 (correct)
- m × I - L
What is the formula for the number of internal vertices in a full m-ary tree with n vertices?
What is the formula for the number of internal vertices in a full m-ary tree with n vertices?
- I = (n - 1) × m
- I = (n + 1) / m
- I = (n + 1) × m
- I = (n - 1) / m (correct)
What is the level of the root in a rooted tree?
What is the level of the root in a rooted tree?
- 0 (correct)
- 1
- -1
- 2
What is the height of a rooted tree?
What is the height of a rooted tree?
What is a balanced tree?
What is a balanced tree?
What is the order of visiting vertices in a pre-order traversal?
What is the order of visiting vertices in a pre-order traversal?
What is the order of visiting vertices in an in-order traversal?
What is the order of visiting vertices in an in-order traversal?
What is the order of visiting vertices in a post-order traversal?
What is the order of visiting vertices in a post-order traversal?
What is a characteristic of a tree?
What is a characteristic of a tree?
What is the name of a graph with no simple circuits?
What is the name of a graph with no simple circuits?
What is a rooted tree?
What is a rooted tree?
What is the definition of a parent in a rooted tree?
What is the definition of a parent in a rooted tree?
What is the order of traversal in Post-order notation?
What is the order of traversal in Post-order notation?
What is a child in a rooted tree?
What is a child in a rooted tree?
What is the term for vertices with the same parent in a rooted tree?
What is the term for vertices with the same parent in a rooted tree?
Which notation is easy for humans to read, write, and speak in?
Which notation is easy for humans to read, write, and speak in?
What is another name for Prefix Notation?
What is another name for Prefix Notation?
What is the term for a vertex with in-degree 0 in a rooted tree?
What is the term for a vertex with in-degree 0 in a rooted tree?
What is the term for a graph that is not connected?
What is the term for a graph that is not connected?
In which notation is the operator written after the operands?
In which notation is the operator written after the operands?
What is the difficulty with using Infix Notation in computing devices?
What is the difficulty with using Infix Notation in computing devices?
What is the order of operands and operator in Prefix Notation?
What is the order of operands and operator in Prefix Notation?
What is the equivalent of 'a - b + c' in Infix Notation?
What is the equivalent of 'a - b + c' in Infix Notation?
How many notations can an arithmetic expression be written in?
How many notations can an arithmetic expression be written in?
Which notation requires a fully parenthesized expression to remove ambiguity?
Which notation requires a fully parenthesized expression to remove ambiguity?
What is the correct prefix notation for the expression ((x + y)^2) + ((x – 4) / 3)?
What is the correct prefix notation for the expression ((x + y)^2) + ((x – 4) / 3)?
What is the correct postfix notation for the expression ((x + y)^2) + ((x – 4) / 3)?
What is the correct postfix notation for the expression ((x + y)^2) + ((x – 4) / 3)?
What type of traversal is used to evaluate a prefix expression?
What type of traversal is used to evaluate a prefix expression?
What type of traversal is used to evaluate a postfix expression?
What type of traversal is used to evaluate a postfix expression?
What is the notation where operators precede their operands?
What is the notation where operators precede their operands?
What is the notation where operators follow their operands?
What is the notation where operators follow their operands?
What is an ancestor of a vertex in a tree?
What is an ancestor of a vertex in a tree?
Which notation is also known as Polish notation?
Which notation is also known as Polish notation?
What is a leaf in a tree?
What is a leaf in a tree?
What is a subtree in a tree?
What is a subtree in a tree?
What is the level of a vertex in a tree?
What is the level of a vertex in a tree?
What is a full m-ary tree?
What is a full m-ary tree?
What is an ordered rooted tree?
What is an ordered rooted tree?
What is the height of a tree?
What is the height of a tree?
What is true about a tree with n vertices?
What is true about a tree with n vertices?
Study Notes
Trees
- A tree is a connected simple undirected graph with no simple circuits.
- Properties of a tree:
- Unique simple path between any two vertices.
- No loops.
- No multiple edges.
Forest
- An undirected graph without simple circuits is called a forest.
- A forest is a set of trees having disjoint sets of nodes.
Rooted (Directed) Trees
- A rooted tree is a tree in which one node has been designated the root and every edge is directed away from the root.
- Key terms:
- Root: Vertex with in-degree 0.
- Parent: Vertex u is a parent, such that there is a directed edge from u to v.
- Child: If u is a parent of v, then v is a child of u.
- Siblings: Vertices with the same parents.
- Ancestors: Vertices in the path from the root to vertex v, excluding v itself, including the root.
- Descendents: All vertices that have v as ancestors.
- Leaf: Vertex with no children.
- Internal node: Vertex that has children.
- Subtree: Subgraph consisting of v and its descendents and their incident edges.
Levels and Height
- Level of v is the length of the unique path from the root to v.
- Height is the maximum of the vertices' levels.
m-ary Trees
- A rooted tree is called m-ary if every internal vertex has no more than m children.
- A full m-ary tree is a tree where every internal vertex has exactly m children.
- A 2-ary tree is called a binary tree.
Ordered Rooted Trees
- A rooted tree where the children of each internal node are ordered.
- In ordered binary trees, we can define left child, right child, left subtree, and right subtree.
- For m-ary trees with m > 2, we can use terms like “leftmost”, “rightmost”, etc.
Properties of Trees
- A tree with n vertices has n - 1 edges.
- A full m-ary tree with I internal vertices and L leaves contains:
- n = m × I + 1 vertices.
- n = I + L vertices.
Balanced Trees
- A rooted m-ary tree of height h is balanced if all leaves are at levels h or h - 1.
Tree Traversal
- Traversal algorithms:
- Pre-order traversal.
- In-order traversal.
- Post-order traversal.
- Tree traversals:
- Pre-order: Root, Left, Right.
- In-order: Left, Root, Right.
- Post-order: Left, Right, Root.
Infix, Prefix, and Postfix Notation
- Infix notation: Operators are used in-between operands.
- Prefix notation (Polish notation): Operator is prefixed to operands.
- Postfix notation (Reverse-Polish notation): Operator is postfixed to operands.
- Notations can be used to represent mathematical expressions.
- Examples:
- Infix: a + b.
- Prefix: +ab.
- Postfix: ab+.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about the properties and examples of trees in graph theory, including connected simple undirected graphs with no simple circuits.
