数据结构-树

概念

• 一种非顺序数据结构，分层数据抽象模型。如家谱，公司组织架构图等。
• 一个树包含一系列存在父子节点关系的节点，每个节点都有一个父节点（除了顶部的第一个节点）以及零个或者多个子节点
• 树顶部节点叫做根节点（没有父节点）
• 至少有一个子元素的节点称为内部节点
• 没有子元素的节点称为外部节点或叶节点
• 子树 - 子树由节点和它的后代构成，如节点13，12，14构成一颗子树
• 节点深度- 节点深度取决于他祖先节点的数量
• 树的高度- 取决于节点深度的最大值

二叉树和二叉搜索树

• 二叉树 - 节点最多只能有两个子节点：一个左侧子节点，一个右侧子节点
• 二叉搜索树 - 二叉树的一种，只允许左侧节点存储比父节点小的值，右侧节点存储比父节点大的值