What is the breadth-first traversal of a tree below after deleting the node 5 by copying?
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, 8, 1, 3, 7, 9". Cây có gốc 5, bên trái là 2 với hai con 1 và 4 trong đó 4 có con trái 3, bên phải là 8 với hai con 7 và 9. Xoá 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ỗ nút bị xoá 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à 8; 2 có hai con 1 và 3; 8 có hai con 7 và 9. Duyệt bề rộng cho 4, rồi 2 và 8, rồi 1, 3, 7, 9. Vì vậy "2, 1, 4, 3, 8, 7, 9" sai vì đó là kết quả của phép xoá bằng cách nối, treo cây con phải 8 vào nút 4 rồi đưa 2 lên làm gốc; "2, 1, 4, 3, 8, 9, 7" sai vì ngoài việc đưa 2 lên gốc nó còn in 9 trước 7, trong khi duyệt bề rộng lấy con trái trước con phải; "2, 1, 4, 3, 7, 8, 9" sai vì nó in 7 trước 8 dù 8 ở tầng ngay dưới gốc còn 7 ở tầng sâu hơn.
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