树

• n(n ≥ 0)个节点构成的有限集合，n为0时称为空树. 共有n - 1条边

一般概念

• 树的顶部节点称为根节点(Root), 用r标识.

• 除根节点外的节点称为原来树的子树(SubTree)，子树之间是不相交的!

• 每个节点有且只有一个父节点

基本术语

• 树的度(Degree): 树的所有节点中最大的子树个数

• 叶子节点(Leaf)：度为0的节点(没有子树)

• 父节点(Parent)：有子树的节点是其子树的父节点

• 子节点(Child)：父节点的孩子节点

• 兄弟节点(Sibling)：拥有同一个父节点的子节点

• 树的深度(Depth)：树的层次

树的表示

• 链表实现【儿子-兄弟表示法】

可以将任意一个树转化为二叉树

旋转45°后来看为二叉树：

二叉树(Binary tree)

有穷的节点集合(可以为空). 由根节点、左子树、右子树构成的不相交的树【最大度为2，最多两个节点】。

二叉树的五种基本形态

• 空、单节点、只有左子树或只有右子树(斜二叉树)、存在左右子树

二叉树的重要性质

• 第k层最大的节点数为：2^(k-1)个节点【eg：第三层最多有4个节点】

• 最多有 2^k-1 个节点

特殊二叉树

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

完美二叉树(满二叉树)

除了叶子节点外，其他节点都有两个子节点的二叉树

非完全二叉树，排序不规范

二叉搜索树

节点的左子树只包含 小于 根节点的数

节点的右子树只包含 大于 根节点的数

所有左子树和右子树自身必须也是二叉搜索树

• 二叉搜索树

• 非二叉搜索树

二叉树的储存结构

数组储存

非完全二叉树

从上至下、从左至右顺序存储，部分为null的节点会造成一定的空间浪费

• 下图用数组储存可表示为: [1, 2, 3, null, null, 6, null, null, null, null, null, null, 13]

完全二叉树

从上至下、从左至右顺序存储

• 下图用数组储存: [1, 2, 3, 4, 5, 6, 7, 8, 9]

链表储存

• Left - Data - Right