function root = AI_decision_tree_learning(examples,attributes,default,...
   f_choose)
%
% AI_decision_tree_learning - learn decision tree
% Call:
%     tree = AI_decision_tree_learning(ex,att,0);
% On input:
%     examples (mxn array): training examples
%     attributes (structure array): attributes array
%     default (scalar): 0 or 1 default value
%     f_choose (string): choose attribute function
% On output:
%     root (scalar): root index of decision tree
% Custom functions used:
%     AI_num_neg_examples, AI_num_pos_examples, ...
%     AI_majority_value, AI_choose_attribute, ...
%     AI_make_node, AI_get_exmaples, AI_sum_include
% Author:
%     T. Henderson, UU, 11/2002
% Method:
%

global nodes num_nodes

[num_examples, num_ex_cols] = size(examples);
root = AI_make_node(default, [], 0, [ ], 0);
if ~AI_more_examples(examples)
   return
elseif AI_all_ex_same(examples)
   nodes(root).value = AI_majority_value(examples);
   return
elseif AI_more_attributes(attributes) == 0
   nodes(root).value = AI_all_values(examples);
   return
else
   [best,gain] = feval(f_choose,attributes,examples);
   nodes(root).value = best;
   nodes(root).name = attributes(best).name;
   nodes(root).type = 1;
   nodes(root).gain = gain;
   attributes(best).include = 0;
   for v = 0:length(attributes(best).values)-1
      examples_v = AI_get_examples(examples,best,v);
      subtree = AI_decision_tree_learning(examples_v, attributes, ...
         AI_majority_value(examples_v),f_choose);
      nodes(root).children = [nodes(root).children; subtree];
      nodes(subtree).parent = root;
   end
end

