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, 6, 1, 3, 8, 7". Cây có gốc 5, bên trái là 2 với hai con 1 và 4 trong đó 4 chỉ có con trái 3, bên phải là 6 chỉ có con phải 8 và 8 chỉ có con trái 7. Xoá gốc bằng cách sao chép kéo giá trị nút liền trước, tức nút phải nhất của cây con trái, lên chỗ gốc rồi cắt nút ấy: từ 2 đi phải hết cỡ được 4, nên 4 lên làm gốc; nút 4 chỉ có con trái 3 nên khi cắt nó, 3 lên thay chỗ và thành con phải của 2. Cây mới có gốc 4 với hai con 2 và 6; 2 có hai con 1 và 3; 6 có con phải 8; 8 có con trái 7. Duyệt bề rộng cho 4, rồi 2 và 6, rồi 1, 3, 8, rồi 7. Vì vậy "4, 2, 6, 1, 3, 7, 8" sai vì 8 ở tầng ngay dưới 6 còn 7 là con của 8 ở tầng sâu hơn, duyệt bề rộng phải vét xong tầng trên; "2, 1, 4, 3, 6, 8, 7" sai vì đó là kết quả của phép xoá bằng cách nối, treo cây con phải 6 vào nút 4 rồi đưa 2 lên làm gốc; "2, 1, 4, 3, 6, 7, 8" sai vì nó vừa đưa 2 lên gốc theo kiểu nối lại vừa in 7 trước 8, phá luôn thứ tự tầng.
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