最近看唐巧的iOS面试之道里讲到二叉树相关的算法，讲的挺好，同时觉得有必要复下
1. 概念
二叉树是每个节点最多有两个子树的树结构，通常被称为左子树和右子树，二叉树常被用于实现二叉查找树和二叉堆。二叉树不是树的一种特殊形式，尽管其与树有很多相似之处，但树和二叉树有两个主要差别:
- 树中节点的最大度数没有限制，而二叉树节点的最大度数为2
- 树的节点无左、右之分，而二叉树的节点有左右之分
二叉树算法主要是递归的思想
递归：在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法
二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决
2. 分类
-
完全二叉树：若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的节点数都达到最大个数，第h层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。
特点：叶子节点的位置比较规律。因此在对数据进行排序或查找时可以用到它，比如堆排序就使用了它 -
满二叉树：除了叶节点外每个节点都有左右子叶且叶子节点都处在最底层的二叉树
-
平衡二叉树：平衡二叉树又被称为AVL树(区别于AVL算法),它是一颗二茬排序树，且具有以下特质
- 它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树
二叉树的存储结构有顺序和链式两种方式，前者虽然简单，但是存在浪费空间的问题，举个例子，下图的二叉树，用顺序的方式存储(0表示空，没有子树)是1 2 3 4 5 6 7 0 0 0 0 8 0 0 0
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的节点，即用一维数组存储二叉树中的节点，因此，必须把二叉树的所有节点安排成一个恰当的序列，节点在这个序列的相互位置能反映出节点直接的逻辑关系。用编号的方法从树根起，自上层至下层，每层自左至右的给所有节点编号
根据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中节点的序号可以唯一的反映出节点之间的逻辑关系，这样即能够最大可能的节省存储空间，又可以利用数组元素的下标值确定节点在二叉树中的位置，以及节点之间的关系
但是对于一般的非完全二叉树来说，如果仍然是按照从上到下，从左到右的次序存储在一维数组中，则数组下标之间不能准确反映树中节点间的逻辑关系，可以在非完全二叉树中添加一些并不存在的空节点使之变成完全二叉树，不过这样做有可能造成空间的浪费，在最坏的情况下，一颗深度为k的右斜树，它只有k个节点，却需要2^k-1个节点存储空间，这显然是对存储空间的严重浪费，所以顺序存储结构一般只用于完全二叉树或满二叉树
二叉树的链式存储结构是指用链表来表示一颗二叉树，即用链表来指示元素的逻辑关系，二叉树的每个节点最大有两个子节点，因此，每个节点除了存储自身的数据外，还应设置两个指针分别向左、由子节点，data是数据域，lchild和rchild都是指针域，分别存放指向左子节点和右子节点的指针，当没有孩子节点时，相应的指针域置为空
左图就是二叉链表结构，右图是三叉链表结构
链式
二叉查找树
二叉树的提出其实主要就是为了提高查找效率，比如我们常用的HashMap在处理哈希冲突严重时，拉链过长导致查找效率降低，就引入了红黑树。二分查找可以缩短查找的时间，但是它要求查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集，于是有了二叉查找树这个概念
二叉查找树(又叫二叉排序树)，它是具有下列性质的二叉树
- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
- 左右子树也分别为二叉排序树
二叉排序树
二叉查找树中，左子树都比节点小，右子树都比节点大，递归定义，根据二叉排序树这个特点我们可以知道：二叉排序树的中序遍历一定是从小到大的。比如上图，中序遍历结果是:
1 3 4 6 7 8 10 13 14
在最好的情况下，二叉排序树的查找效率比较高，是O(logn,其访问性能近似于折半查找，但最差时会是O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行
如果我们可以保证二叉排序树不出现上面提到的极端情况（插入的元素是有序的，导致变成一个链表），就可以保证很高的效率了。但这在插入有序的元素时不太好控制，按二叉排序树的定义，我们无法判断当前的树是否需要调整。因此就要用到平衡二叉树(AVL树)了。
平衡二叉树在添加和删除时需要进行旋转保持整个树的平衡，内部做了这么多复杂的工作后，我们在使用它时，插入、查找的时间复杂度都是O(logon),性能已经相当好了
遍历顺序
- 前序遍历： 先访问根节点，再访问左子树，最后访问右子树
- 中序遍历:先访问左子树，再访问根节点，再访问右子树
- 后续遍历:先访问左子树，再访问右子树，最后访问根节点
- 层序遍历：一层层节点依次遍历
这颗二叉树
前序遍历：1 2 4 5 7 3 6
中序遍历： 4 2 5 7 1 6 3
后序遍历： 4 2 5 7 6 3 1
层序遍历：1 2 3 4 5 6 7
递归固然是清晰明了，但是存在效率低的问题，非递归的方案用栈结构来存节点信息，通过出栈访问来遍历二叉树。它的思想是这样的：当栈顶中的指针非空时，遍历左子树，也就是左子树根的指针进栈。当栈顶指针为空时，应退至上一层，如果是左子树返回的，访问当前层，也就是栈顶中的根指针节点。如果是从右子树返回，说明当前层遍历完毕，继续退栈
参考:iOS算法之二叉树
网友评论