树

术语

树的术语.png

位于树顶部的节点叫作根节点（11）。它没有父节点。
树中的每个元素都叫作节点，节点分为内部节点和外部节点。

键是树相关的术语中对节点的称呼。

至少有一个子节点的节点称为内部节点（7、5、9、15、13和20是内部节点）。
没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18和25是叶节点）。

深度

节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。
比如，节点3有3个祖先节点（5、7和11），它的深度为3。

树的高度

树的高度取决于所有节点深度的最大值。
一棵树也可以被分解成层级。根节点在第0层，它的子节点在第1层，以此类推。
上图中的树的高度为3（最大高度已在图中表示——第3层）。

二叉树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。

二叉搜索树（BST：Binary（二进制、二元的） Search Tree）：左小右大

二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。

树的遍历

中序、先序、后序

中序

从最小到最大
3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

image.png

先序

先序遍历是以优先于后代节点的顺序访问每个节点的
11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

image.png

后序

序遍历则是先访问节点的后代节点，再访问节点本身。
后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。
3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

image.png