定义
二叉树(binary tree)是指树中节点的度不大于2的有序树,树节点的子节点称作左节点和右节点。
可以用类对象简单定义出一个树节点,如下:
1 | class TreeNode: |
细分
斜树
- 所有节点都只有左节点的树称为左斜树
- 所有节点都只有右节点的树称为右斜树
(本质上可以视为链表)
满二叉树/完美二叉树
所有非叶子节点都有两个子节点,且子节点都在同一层次上(即左右子数高度相等)
完全二叉树
所有非叶子节点都有两个子节点,但不要求子节点都在同一层次上
二叉查找树 - BST
二叉查找树是空树或满足以下性质的二叉树,
- 若任意节点的左子树不为空,则左子树上的所有节点的值都小于它根节点的值
- 若任意节点的右子树不为空,则右子树上的所有节点的值都大于它根节点的值
- 任意左子树和右子树也都为二叉查找树
- 节点的值不相等。
红黑树
红黑树是一种自平衡的二叉查找树
- 每个节点要么是红,要么是黑
- 根节点是黑的。
- 叶节点是黑的。
- 如果一个节点是红,则两个子节点为黑。
- 对于任意节点,其到叶节点空指针的每天路径都包含相同数目的黑节点。
用法最广:
- Java ConcurrentHashMap & TreeMap
C++ STL: map & set
linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
epoll在内核中的实现,用红黑树管理事件块
nginx中,用红黑树管理timer等
哈夫曼树
又称最优二叉树。是一种带权路径长度最短的二叉树。
一般按如下方式构建,
- 将左右子树都为空的作为根节点
- 在森林中选出两棵根节点权值最小的树作为一棵新树的左右子树,且置新树的附加根节点的权值为左右子树的权值之和
B树
B+树
R树
遍历
二叉树的遍历依据遍历行进的方向主要分为深度优先和广度优先(层次遍历)。其中,
深度遍历又分为:前序,中序,后序。
四种主要的遍历思想为:
- 前序遍历(preOrderTraverse):根 -> 左 -> 右
- 后序遍历(postOderTraverse):左 -> 右 -> 根
- 中序遍历(inOrderTraverse):左 -> 根 -> 右
- 层次遍历:上 -> 下,每一层
对下面二叉树进行遍历:
前序遍历
结果:1->2->4->5->7->8->3->6
1 | def pre_order_traverse(node: TreeNode): |
使用迭代方式遍历
使用迭代方式进行前序遍历需要借助与栈结构,原因如下:
整体上,前序遍历的过程是,从根节点开始,先记录自身值,然后始终有限从左节点开始访问。
https://zhuanlan.zhihu.com/p/376166992
后序遍历
结果: 4->7->8->5->2->6->3->1
1 | def post_order_traverse(node: TreeNode): |
中序遍历
结果: 4->2->7->5->8->1->6->3
1 | def in_order_traverse(node: TreeNode): |
层次遍历
层次遍历通常不采用递归来实现,一般对借用队列结构,从根节点开始排队进入队列。
结果:1->2->3->4->5->6->7->8
1 | def level_traverse(node: TreeNode): |