【算法】二叉树基础

二叉树种类

1. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

   

   深度为k，有2^k-1个节点

2. 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

   

3. 二叉搜索树

   数值大小：左 < 父 < 右

4. 平衡二叉搜索树（AVL树）。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式

链式：指针

顺序：数组

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树定义

class TreeNode {
	int data;
	TreeNode left;
	TreeNode right;

	public TreeNode(){}
	public TreeNode(int data){
		this.data = data;
	}
	public TreeNode(int data, TreeNode left, TreeNode right){
		this.data = data;
		this.left = left;
		this.right = right;
	}
}