Árvores de decisão ou árvores de classificação são definidas informalmente como modelos de aprendizado supervisionado que representam regras de decisão baseadas nos valores dos atributos. São muito usadas em inteligência artificial, por isso, vamos definir formalmente o que é uma árvore na área de ciência da computação.

Uma árvore é uma coleção de elementos chamados nós, dentre os quais um é distinguido como uma raiz, juntamente com uma relação de parentesco que impõe uma estrutura hierárquica sobre os nós.

Formalmente: uma árvore pode ser definida recursivamente da seguinte maneira:

1. Um único nó é uma árvore. Este nó é também a raíz da árvore.

2. Suponha que t seja um nó e T1, T2, …, Tk sejam árvores com raízes t1, t2, …, tk, respectivamente. Podemos construir uma nova árvore transformando t no pai dos nós t1, t2, …, tk. Nessa árvore, t será a raiz e T1, T2, …, Tk serão as subárvores ou ramos da raiz. Os nós t1, t2, …, tk são chamados filhos do nó t.

Se t1, t2, …, tk é uma sequência de nós em uma árvore tais que ti é o pai de ti+1 para 1 ≤ i < k, então esta sequência é denominada um caminho do nó t1 até o nó tk. Se existe um caminho do nó a ao nó b, então a é um ancestral de b e b é um descendente de a. Todo nó é ancestral e descendente de si mesmo. Dado um nó t ∈ T, a sub-árvore ou ramo Tt de T consistirá do nó t (que será a raiz de Tt) juntamente com todos os descendentes de t em T. Todos os nós que não possuem filhos são chamados nós terminais ou folhas. Os nós que contêm filhos são chamados nós não-terminais ou nós internos. O conjunto das folhas de T será denotado por T.