1.引言
學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)對(duì)二叉樹應(yīng)該不陌生:二叉樹是一個(gè)連通的無環(huán)圖,每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。如下圖(一)就是一個(gè)深度k=3的二叉樹。
(圖一) (圖二)
二元決策樹與此類似。不過二元決策樹是基于屬性做一系列二元(是/否)決策。每次決策從下面的兩種決策中選擇一種,然后又會(huì)引出另外兩種決策,依次類推直到葉子節(jié)點(diǎn):即最終的結(jié)果。也可以理解為是對(duì)二叉樹的遍歷,或者很多層的if-else嵌套。
這里需要特別說明的是:二元決策樹中的深度算法與二叉樹中的深度算法是不一樣的。二叉樹的深度是指有多少層,而二元決策樹的深度是指經(jīng)過多少層計(jì)算。以上圖(一)為例,二叉樹的深度k=3,而在二元決策樹中深度k=2。
圖二就是一個(gè)二元決策樹的例子,其中最關(guān)鍵的是如何