一、理论知识
二叉树的常见规律推导
二叉树有几个比较重要的特性, 在笔试题中比较常见:
- 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;
- 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。
二叉树的概念
- 二叉树的定义
- 二叉树可以为空, 也就是没有结点.
- 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
- 二叉树有五种形态:
- 注意c和d是不同的二叉树, 因为二叉树是有左右之分的.
什么是二叉搜索树?
- 二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树
- 二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树本身也都是二叉搜索树。
二叉搜索树的操作
- 二叉搜索树有哪些常见的操作呢?
insert(key)：向树中插入一个新的键。search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false。inOrderTraverse：通过中序遍历方式遍历所有结点。preOrderTraverse：通过先序遍历方式遍历所有结点。postOrderTraverse：通过后序遍历方式遍历所有结点。min：返回树中最小的值/键。max：返回树中最大的值/键。remove(key)：从树中移除某个键。
二、遍历二叉树
1.先序遍历
- 遍历过程为：
- ①访问根结点；
- ②先序遍历其左子树；
- ③先序遍历其右子树。
3.后序遍历
- 遍历过程为：
- ①后序遍历其左子树；
- ②后序遍历其右子树；
- ③访问根结点。
