二叉树
二叉树
本文摘自 代码随想录
定义
满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。
但是, 下图根据国内定义就不是一个满二叉树
完全二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树
二叉搜索树
- 一个有序树
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉搜索树
- AVL (Adelson-Velsky and Landis)
- 空树
- 左右两个子树高度绝对值不超过1 (<=1), 并且两个子树都是 AVL
存储方式
- 顺序, 数组
- 链式, 指针方式
链式:
顺序:
- 遍历
- 如果父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。
注意: 常用的还是链式