How should a decision tree handle an attribute that can be anything? Say I have AttributeA that can take values A1, A2, A3, AttributeB that can take values B1, B2, B3, etc. and I know ahead of time that my classification table looks like

AttributeA | AttributeB | AttributeC | Classification

A1 | B1 | anything | Class 1

anything | B2 | anything | Class 2

A3 | B1 | C2 | Class 3

A2 | anything | C3 | Class 4

...

I'm curious how I would modify a decision tree to handle attributes that can take on any value. One idea I had was to change single rules with "anything" into multiple rules where every possible value of that attribute is explicitly stated. For instance, the rule A1 | B1 | anything | Class 1 could be changed into the three rules:

A1 | B1 | C1 | Class 1

A1 | B1 | C2 | Class 1

A1 | B1 | C3 | Class 1

I'm sure this would work, but I'd like to see if there are any existing decision tree implementations that can handle "anything" or "does not matter" entries.
I think your description of anything matches the idea of missing values. Basically by stating that a value could take any value you say that you do not know the value. In standard Breiman description of CART or random forests there is a way to handle missing values. If you use Python stack, however, the implementations does not allow missing values. If that is the case one surrogate would be a different new value for categorical data. For numerical continuous variables I don’t know something better than imputing with average, but it is not quite the same thing.