資料結構›Ch9 進階樹第 63 題/共 88 題
63. Compressed Binary Trie、BFS、bitNumber
#DS-09-063中Compressed Binary TrieBFSbitNumber
題組題幹(本題:(b),共 2 小題)點擊展開
A campus system stores device IDs. Each ID is a 6-bit binary string. Given the following seven 6-bit keys: 000001, 000010, 000011, 001111, 100000, 101011, 111110.
[4%] (Continue Question 1) Build the compressed binary trie for the same seven 6-bit keys. For each branch node, define its bitNumber as the bit index used at that node to choose the left or right child. The leftmost bit is index 1 and the rightmost bit is index 6. Perform BFS starting from the root. When visiting a branch node, enqueue the left child before the right child. List the bitNumber of each visited branch node in BFS order.
Answer format: bitNum1, bitNum2, …
📄 成大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch9 進階樹