树

描述

树是一个分层数据的抽象模型

相关术语

1. 根节点
2. 祖先节点
3. 后代节点
4. 父节点
5. 子节点
6. 内部节点
7. 外部节点（叶节点）
8. 子树
9. 深度
10. 高度

二叉树和二叉搜索树

​ 二叉树中的节点最多只有两个子节点

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

创建 BrnarySearchTree 类

function BinarySearchTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    var root = null;
}

节点之间的关系称之为 “边”

节点在树中相关的术语是 “键”

树的遍历

• 中序遍历
• 先序遍历
• 后序遍历

中序遍历

中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。

中序遍历的一种应用就是对树进行排序操作。

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。

先序遍历的一种应用是打印一个结构化的文档

后序遍历

后序遍历则是先访问节点的后代节点，再访问节点本身。

后序遍历的一种应用就是计算一个目录和它的子目录中所有文件所占空间的大小

搜索树中的值

• 搜索最小值
• 搜索最大值
• 搜索特定的值