数据结构之树

树是一种分层数据的抽象模子。实际生存中最常见的树的例子是家谱，或是公司的构造架构图

• 树的干系术语
  

一个树结构包罗一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点

• 位于树顶部的节点叫做根节点(11)
  
• 树中的每个元素都叫作节点，节点分为内部节点和外部节点
  
  
  
  • 至少有一个子节点的节点称为内部节点（7、5、9、15、13 和 20 是内部节点）
    
  • 没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18 和 25 是叶节点）
    
  
  
• 一个节点可以有先人和后代
  
  
  
  • 一个节点（除了根节点）的先人包括父节点、祖父节点、曾祖父节点等, 节点 5 的先人有节点 7 和节点 11，
    
  • 一个节点的后代包括子节点、孙子节点、曾孙节点等, 节点 5 后代有节点 3 和节点 6
    
  
  
• 树的另一个术语是子树
  
  
  
  • 子树由节点和它的后代构成。比方，节点 13、12 和 14 构成了上图中树的一棵子树
    
  
  
• 节点的一个属性是深度
  
  
  
  • 节点的深度取决于它的先人节点的数量。比如，节点 3 有 3 个先人节点（5、7 和 11），它的深度为 3
    
  
  
• 树的高度取决于全部节点深度的最大值
  
  
  
  • 一棵树也可以被分解成层级。根节点在第 0 层，它的子节点在第 1 层，以此类推。上图中的树的高度为 3（最大高度已在图中表现——第 3 层）
    
  
  

• 二叉树和二叉搜索树
  

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点, 二叉搜索树（BST）是二叉树的一种，但是只答应你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。上一节的图中就显现了一棵二叉搜索树

• 创建二叉搜索树(BinarySearchTree)类
  

和链表一样, 我们通过指针(引用)来表现节点之间的关系, 树也是用两个指针, 但一个指向左侧子节点, 另一个指向右侧子节点, 差异于在之前的章节中将节点自己称作节点或项，我们将会称其为键