You have to run another step after installing the command line tools:
sudo installer -pkg /Library/Developer/CommandLineTools/Packages/macOS_SDK_headers_for_macOS_10.14.pkg -target /
Why? Apple have introduced a new build tool dance - system includes are now only kept under a specific SDK's path with Xcode 10 onwards:
The Command Line Tools package installs the macOS system headers inside the macOS SDK. Software that compiles with the installed tools will search for headers within the macOS SDK [...] provided by either Xcode [...] or the Command Line Tools [...] depending on which is selected using xcode-select.
The command line tools will search the SDK for system headers by default. However, some software may fail to build correctly against the SDK and require macOS headers to be installed in the base system under
/usr/include [emphasis added]. If you are the maintainer of such software, we encourage you to update your project to work with the SDK or file a bug report for issues that are preventing you from doing so. As a workaround, an extra package is provided which will install the headers to the base system. In a future release, this package will no longer be provided. You can find this package at:
To make sure that you're using the intended version of the command line tools, run
xcode-select -s <path to Xcode> or
xcode select -s /Library/Developer/CommandLineTools after installing.