Given a binary search tree T below. What is a result of breadth-first traverse of T after you delete by copying the root (node 5)?
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, 2, 7, 1, 3, 8, 9". Cây có gốc 5, nhánh trái 2 với hai con 1 và 4, dưới 4 là con trái 3, nhánh phải 7 với con phải 8 và dưới 8 là con phải 9. Xoá bằng cách sao chép lấy nút cực phải của nhánh trái làm giá trị thay thế: đi từ 2 sang 4, mà 4 không có con phải nên 4 chính là tiền nhiệm trung tố; gán 4 cho gốc rồi tháo nút 4 cũ, con trái 3 của nó lên thế chỗ làm con phải của 2. Cây mới có gốc 4, nhánh trái 2 với hai con 1 và 3, nhánh phải vẫn là 7, 8, 9. Duyệt theo chiều rộng cho 4, rồi 2 và 7, rồi 1, 3, 8, rồi 9. Dãy "4, 2, 7, 1, 8, 3, 9" xếp 8 trước 3 ở cùng mức, nhưng duyệt chiều rộng đọc từ trái sang phải nên 3 nằm dưới 2 phải đứng trước 8 nằm dưới 7. Dãy "2, 1, 4, 7, 8, 3, 9" đưa 2 lên làm gốc, đó là lối xoá bằng cách nối chứ không phải sao chép. Dãy "2, 1, 4, 3, 7, 8, 9" cũng nâng 2 lên gốc và treo nhánh phải xuống dưới 4, vẫn là phép nối cây chứ không phải thay giá trị gốc.
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