How can alpha zero learn if the tree search stops and restarts before finishing a game?
You're right that AlphaGo Zero doesn't perform rollouts in its MCTS. It does complete many, many games, though.

Realize that AlphaGo Zero only iterates MCTS 1,600 times before taking an action. The next state resulting from that action becomes the root of future search trees. Since a typical game of Go only lasts a few hundred moves, the board will very quickly reach a terminal state.  

None of this is dependent on the initial performance of the neural network. The neural net can be incredibly bad; actions/moves will still be taken at the same frequency. Of course, since AlphaGo Zero trains with self-play, one of its two selves in a game will usually be the winner (ties are possible). So the neural net will improve over time. 

I recommend going over the "Self-Play Training Pipeline" section of the paper.