二叉树Binary tree

每个节点至多有两个孩子，用父子关系表达层级。

一棵平衡的二叉搜索树示例；普通二叉树不必满足键序。

常见操作#

n 为节点数，h 为树高，w 为最大一层宽度；普通二叉树不保证有序或平衡。

操作	时间复杂度	条件与说明
从已知节点访问子节点	$O(1)$	节点保存左右子节点引用。
查找任意值	$O(n)$	没有搜索树的顺序约束，最坏检查全部节点。
已知空位置挂接 / 摘除子树	$O(1)$	只计算修改链接；逐节点销毁子树仍需与子树大小成正比的时间。
深度优先遍历	$O(n)$	递归或显式栈的辅助空间为 $O(h)$ 。
层序遍历	$O(n)$	队列辅助空间为 $O(w)$ 。

树高可能达到 $O(n)$ ；不能从“每节点最多两个孩子”推出对数查找。

基础原理参考资料

Open Data Structures · BinaryTree二叉树表示、父子关系及递归和非递归遍历。