Extensive research has been devoted to the segmentation of the coronary artery. However, owing to its complex anatomical structure, it is extremely challenging to automatically segment the coronary artery from 3D coronary computed tomography angiography (CCTA). Inspired by recent ideas to use tree-structured long short-term memory (LSTM) to model the underlying tree structures for NLP tasks, we propose a novel tree-structured convolutional gated recurrent unit (ConvGRU) model to learn the anatomical structure of the coronary artery. However, unlike tree-structured LSTM proposed for semantic relatedness as well as sentiment classification in natural language processing, our tree-structured ConvGRU model considers the local spatial correlations in the input data as the convolutions are used for input-to-state as well as state-to-state transitions, thus more suitable for image analysis. To conduct voxel-wise segmentation, a tree-structured segmentation framework is presented. It consists of a fully convolutional network (FCN) for multi-scale discriminative feature extraction and the final prediction, and a tree-structured ConvGRU layer for anatomical structure modeling. The proposed framework is extensively evaluated on four large-scale 3D CCTA dataset (the largest to the best of our knowledge), and experiments show that our method is more accurate as well as efficient, compared with other coronary artery segmentation approaches.