logo头像
Snippet 博客主题

二叉树

二叉树四种遍历(递归和非递归代码实现)

前序遍历(根->左->右)

若树为空,则空操作返回。否则,先访问根节点,然后前序遍历左子树,再前序遍历右子树。(根->左->右)。

中序遍历(左->根->右)

若树为空,则空操作返回。否则,从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历根节点的右子树。(左->根->右)。

后序遍历(左->右->根)

若树为空,则空操作返回。否则,从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。(左->右->根)。

层序遍历

若树为空,则空操作返回。否则,从树的第一层,也就是根节点开始访问,从上到下逐层遍历,在同一层中,按从左到右的顺序结点逐个访问。

参考文献
二叉树的四种遍历(递归和非递归)–Java实现
二叉树的四种遍历方式【Java实现】

树的分类

二叉树

每个节点至多有两个节点的树

二叉搜索树/查找树/排序树(BST)

特点:每个节点的值大于其任意左侧子节点的值,小于其任意右节点的值。

二叉平衡树

树的左右高度差不能超过1;任何往下递归的左子树与右子树满足第一条;没有任何节点的空树或只有根节点的树也是平衡树。

平衡二叉搜索树

是一种特殊情况下的二叉查找树,它的特殊之处在于,对于每一个节点,其左子树深度和右子树深度之差的绝对值不大于1。最早被发明的平衡二叉搜索树为AVL树。

红黑树

红黑树本质是二叉搜索树,还有5个约束
(1) 节点只能只红色或者黑色(红黑树嘛,就是说只有这俩个颜色)
(2) 根节点必须为黑色
(3) 所有NIL节点是黑色(Nothing In leaf,是红黑树中特殊的存在,即叶子节点上不存在的两个虚拟节点,是后续红黑树旋转的基础)
(4) 一条路径上不能出现相邻的两个红色节点
(5) 在任何递归子树内,根节点到叶子节点的所有路径上包含相同数目的黑色节点
红黑树的时间复杂度为: O(lgn),n为节点个数。

满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

完全二叉树

除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

B+树

b-