Each CT has zero error on its training set. The overall structure in each training set is the same (shown by the circles and triangles). Each CT, however, fits

Each CT has zero error on its training set. The overall structure in each training set is the same (shown by the circles and triangles). Each CT, however, fits to the noise that is specific each training set. This causes the "linear" regions you mention. This is caused by how CTs recursively subdivide the feature space - these are essentially small subdivision areas fit to noise, which have extended beyond the class region to which they "should" belong.