数据结构笔记（树->二叉树）

二叉树(Binary Tree)：
根节点、左子树TL和右子树TR

特殊二叉树：
1、斜二叉树(Skewed Binary Tree)
2、完美二叉树(Perfect Binary Tree) 即满二叉树(Full Binary Tree)
3、完全二叉树(Compelet Binary Tree)

二叉树重要性质：
1、一个二叉树第i层的最大节点数为：2^(i-1)，i>=1
2、深度为k的二叉树的最大节点数为：2^k - 1,k>=1
3、对于任一非空二叉树，叶节点 = 度为2的非叶节点 + 1

常用遍历方法：
1、先序：根、左、右
2、中序：左、根、右
3、后序：左、右、根
4、层次遍历：从上到下、从左到右

二叉树存储结构：
1、顺序存储结构（数组存储）：
1、完全二叉树：
1、非根节点（i>1）的父结点的序号是i/2
2、节点(i)的左孩子节点的序号是2i(2i<n)
3、节点(i)的右孩子节点的序号是2i+1(2i+1<n)
2、一般二叉树
1、补齐为完全二叉树（空间浪费）
2、链表存储
1、1、三个域：data、left、right

遍历方法（链式存储为例）：
递归：
1、先序遍历：
1、访问根节点
2、先序遍历左子树
3、先序遍历右子树
2、中序遍历：
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树
3、后序遍历：
1、后序遍历左子树
2、后序遍历右子树
3、访问根目录
先序、中序、后序遍历路线相同、访问节点时机不同。
中序遍历非递归算法实现：
使用堆栈：根节点压入堆栈、进入左子树判断；无左子树则抛出节点，进入右子树判断：无右子树则返回上一层

层序遍历：
1、队列实现：遍历从根节点开始，根节点入队，执行循环：根节点出队，访问，将其左右子树入队