電腦科學與資訊工程科 Computer Science & Information Engineering
190005 Taiwan
由DFS與BFS序列重建樹結構之唯一性探討 On the Uniqueness of Reconstructing Tree Structures from DFS and BFS Sequences
This study investigates the tree structure reconstruction problem of general rooted trees, focusing on whether the original tree structure can be uniquely reconstructed using only Depth-First Search (DFS) and Breadth-First Search (BFS) sequences. An O(n) algorithm implemented in C++ is proposed, and the source of non-uniqueness is identified as the so-called Traversal Isomorphic Block (TIB). To resolve this ambiguity, the reversed Depth-First Search (DFS⁻) is introduced as an additional condition. The results show that the combination of the three sequences (DFS, BFS, DFS⁻) enables the unique reconstruction of the original tree in O(n) time, forming a practical linear-time reconstruction framework and clarifying the ambiguities inherent in DFS and BFS.