基本性质
每个结点最多有两棵子树,左子树和右子树,顺序不可颠倒。
- 非空二叉树第\(n\)层最多有\(2^{n-1}\)个元素。
- 深度为\(h\)的二叉树,至多有\(2^h-1\)个结点。
结点结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
二叉树的遍历
遍历即将树的所有结点都访问且仅访问一次。按照根结点访问次序的不同,可以分为前序遍历,中序遍历,后序遍历。
- 前序遍历:根结点 -> 左子树 -> 右子树
- 中序遍历:左子树 -> 根结点 -> 右子树
- 后序遍历:左子树 -> 右子树 -> 根结点
另外还有一种层次遍历,即每一层都从左向右遍历。
例如:求下图的二叉树的遍历
前序遍历:abdefgc
中序遍历:debgfac
后序遍历:edgfbca
层次遍历:abcdfeg