根节点是什么？树形结构最顶端的那个起点

根节点（Root Node）是树形结构中位于最顶端的那个节点。它是整棵树的起点，没有父节点；树中的所有其他节点，都是从它出发、一层层地延伸出来的。树形结构在计算机科学和机器学习中无处不在，根节点是理解它们的起点。

树形结构的基本概念

在计算机科学中，树是一种由节点和连接节点的边组成的层次结构。与自然界中的树不同，它通常被画成“倒过来”的样子：根在最上面，枝叶向下展开。几个基本的概念包括：根节点，最顶端、没有父节点的那个节点，一棵树有且只有一个根节点；父节点和子节点，如果一个节点直接连接着下一层的某些节点，它就是这些节点的父节点，下一层的节点就是它的子节点；叶子节点，位于最底端、没有任何子节点的节点；内部节点，既不是根节点也不是叶子节点的中间节点；节点的深度，从根节点到这个节点所经过的边的数量，根节点的深度为零；树的高度，从根节点到最远的叶子节点的深度。

生活中很多结构都是树形的：电脑中的文件夹，最上层的磁盘或根目录就是根节点；公司的组织架构图，总经理位于根节点；家谱中的始祖；网页的结构中，最外层的 html 元素就是整棵文档树的根节点。

决策树中的根节点

在机器学习的决策树中，根节点有着特殊的重要性。在训练开始时，所有的训练样本都位于根节点。决策树算法会在根节点上，从所有的特征中挑选出一个最能区分不同类别的特征，以及合适的划分点，比如“年龄是否小于 30 岁”，然后根据这个条件把所有的样本分成两部分或几部分，分别进入下一层的子节点。接着，在每个子节点上重复这个过程，直到满足停止的条件，最终形成叶子节点，每个叶子节点给出一个预测的结果。

根节点上进行的是第一次划分，它面对的是全部的样本，所选择的特征通常是对预测结果影响最大、区分能力最大的特征，衡量的标准可以是信息增益、基尼系数的下降，或者均方误差的下降。因此，观察决策树根节点上使用的是哪个特征，往往能对数据中最重要的规律有一个直观的认识。比如在预测泰坦尼克号乘客是否生还的经典例子中，决策树的根节点通常会选择“性别”这个特征，这反映了当时“妇女和儿童优先”的救生原则对生还的影响。

预测一个新样本时，也总是从根节点开始：根据样本的特征回答根节点上的问题，沿着相应的分支走到下一个节点，再回答下一个问题，如此一直走到某个叶子节点，就得到了预测的结果。

其他场合中的根节点

在搜索算法中，比如下棋程序的博弈树，根节点代表当前的棋局，每个子节点代表走一步棋之后的局面。在蒙特卡罗树搜索中，从根节点出发不断地探索和评估可能的走法，AlphaGo 就使用了这一方法。在解析树中，根节点代表整个句子或整段程序代码。在数据库的索引结构，比如 B 树中，所有的查找都从根节点开始。