二叉树
- 二叉树
- 平衡二叉树
- 二叉树中任意结点的左右子树深度相差不超过 1。
- 二叉搜索树
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
- 没有键值相等的节点
深度优先遍历(或搜索)有三种
- 先序遍历
- 中序遍历
- 后序遍历
广度优先遍历(或搜索)一般有一种。
最近公共祖先(Lowest Common Ancestor)
二叉树打印
二叉树按层遍历
- 即广度优先遍历
- 使用队列结构实现
- 可能要求时要求把行号也打印出来
二叉树的序列化和反序列化
- 序列化
- 二叉树→字符串
- 反序列化
- 字符串→二叉树