Trees (including binary trees)：練習問題

Which of the following properties uniquely defines a tree in graph theory terms?

Consider a binary tree where every internal node has exactly two children. If the tree has \(n\) leaf nodes, how many internal nodes (including the root) does it have?

A binary search tree is constructed by inserting the following keys in order: 50, 30, 70, 20, 40, 60, 80. After these insertions, the key 50 is deleted and replaced by its in-order successor. What is the new root of the tree?

In a binary search tree (BST), if we want to output the data values in ascending order, which traversal algorithm should be used?

Which statement correctly describes the difference between static and dynamic implementation of a tree data structure?

Identify the specific type of tree traversal required to output the contents of a binary search tree in ascending numerical order.

In graph theory, a tree is defined as a connected, undirected graph with no cycles. If a tree has \( V \) vertices, exactly how many edges must it have, and why would adding one more edge between any two existing vertices violate the tree property?

Identify the specific tree traversal that would be used to produce a prefix expression from an expression tree and describe the order in which the root and its children are visited.

A Binary Search Tree (BST) is constructed by inserting the following keys in order: 50, 30, 70, 20, 40, 90.

a. Identify the root node and its immediate left and right children. (1 point)
b. Perform an In-order traversal of this tree and list the resulting sequence. (2 points)
c. Explain why an In-order traversal is particularly useful when applied to a Binary Search Tree. (1 point)

A binary search tree (BST) is a specific type of tree structure.

(a) Define the mathematical properties of a tree and explain what makes a tree a rooted tree.
(b) Identify the maximum number of children any node can have in a binary tree.
(c) A BST is constructed with the following keys inserted in order: 40, 20, 10, 30, 60, 50, 70. Describe the steps to find the key 50 and state how many comparisons are required.