Select the correct statement. Suppose T is a binary tree with 14 nodes. What is the minimum possible height of T? (Note: In a tree the height of root is 1)
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "4". Với quy ước gốc có chiều cao 1, mức thứ i của cây nhị phân chứa tối đa 2 lũy thừa i trừ 1 nút, nên cây chiều cao h chứa tối đa 2 lũy thừa h trừ 1 nút: chiều cao 3 chứa nhiều nhất 1 cộng 2 cộng 4 bằng 7 nút, thêm mức thứ tư tối đa 8 nút nữa thành 15 nút. Vì 14 lớn hơn 7, không thể gói 14 nút vào ba mức; vì 14 không vượt 15, bốn mức là đủ, nên chiều cao nhỏ nhất bằng 4. "2" chỉ chứa tối đa 3 nút nên quá nhỏ. "3" chứa tối đa 7 nút, còn thiếu 7 nút so với 14. "5" là chiều cao đạt được nhưng không phải nhỏ nhất, vì chỉ cần dồn 14 nút vào bốn mức là xong; chiều cao 5 mới bắt buộc khi số nút vượt 15.
Cùng phần 4
What is the minimum number of nodes in a nearly complete binary tree with height 4?
(In a tree the height of root is 1, and a binary tree with height h is called nearly complete if the tree is complete at level d for d = 1, 2, ..., h-1, and the leaves in the last level are all in the leftmost positions).Có lời giảiCâu hỏiTo implement an AVL tree, a concept balance factor is introduced (bal = height(right)-height(left)). Suppose an AVL tree is created by inserting to the tree the following keys sequentially:
6, 3, 7, 2, 5, 1
What is the balance factor of the node 6? (please note that the tree is still AVL)Có lời giảiCâu hỏiSuppose the binary search tree T is made by inserting the following keys consequently: 6, 7, 8, 9, 3, 2, 5, 4
What is the result of breadth-first traverse of T?Có lời giảiCâu hỏiCả 76 câu của chủ đề76 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây