OX0001 基本概念

  1. 树

    n(n >= 0) 个节点 的有限集。当 n=0 时，称为空树，在任意一个非空树种有如下特点：

    1. 有且仅有一个特定的称为根的节点。
    2. 当 n > 1 时，其余节点分为 m (m > 0) 个互不相交的有限集，每个集合本身又是一个树，并称为根的子树

  2. 二叉树

    每个节点只有两个孩子的树

  3. 满二插树

    一个二叉树的所有非叶子节点都存在左右孩子，并且所有的叶子节点都在同一个层级

  4. 完全二叉树

    对一个有 n 个节点的二叉树，按层级顺序编号，所有节点的编号为 1到 n，如果这个数的所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树

OX0002. 存储方式

  1. 链表

    					         [NodeA|data1|left|right]
						//									\\
					//											\\
				//												   \\
[NodeB|data2|null|null]			            [NodeC|data3|null|null]

  2. 数组 - 层序存储 (主要用于完全二叉树，否则会大量浪费空间)

    父节点下标为parent，则做孩子的下标为 2* parent + 1，有孩子为 2*parent + 2

    				 【1】
				//	 \\
			【2】	  【3】
			//	\\         \\
		【4】 【5】   【6】
			\\
			【8】
			
[1][2][3][4][5][null][6][null][8]
 0  1  2  3  4   5    6   7    8

OX0003. BST 二叉查找树/二叉排序树

  1. 左子树不为空，左子树的值均小于根
  2. 右子树不为空，右子树的值均大于根
  3. 左右子树也是 BST
  4. 时间复杂度: O(logn)O(logn)