Abstract
Tree construction problem is always an interesting topic under fault-tolerant distributed systems. In this thesis, we present a deterministic self-stabilizing spanning tree construction algorithm, which runs in a non-uniform network with general graph topology. It requires only extremely small memory space per node. Each node only keeps a pointer to identify its parent and three 1-bit variables to interact with its neighbors. The Stabilizing time of the algorithm is O(n2), where n is the number of nodes in the system.