iOS开发算法--二叉树

淩亂°似流年 2023-10-17 13:26 6阅读 0赞

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆(详见堆排序)。二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二 叉树有两个主要差别：树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 树的结点无左、右之分，而二叉树的结点有左、右之分。

详细代码请参考[Algorithm][]。参考代码比文字好理解。

##### 分类 #####

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

![1240][]

二叉树的存储结构有顺序和链式两种方式。前者虽然使用简单，但是存在浪费空间的问题，举个例子，下图的二叉树，用顺序的方式存储(0表示空，没有子树)是1 2 3 4 5 6 7 0 0 0 0 8 0 0 0。

![1240 1][]

链式结构可以参考链表。

##### 三遍历顺序 #####

先序遍历是先访问根结点，再左子树，再右子树。中序是先访问左子树, 再根结点，再右子树。后序是先访问左子树, 再右子树，再根结点。递归固然是清晰明了，但是存在效率低的问题，非递归的方案用栈结构来存结点信息，通过出栈访问来遍历二叉树。它思想是这样的，当栈顶中的指针非空时，遍历左子树，也就是左子树根的指针进栈。当栈顶指针为空时，应退至上一层，如果是从左子树返回的，访问当前层，也就是栈顶中的根指针结点。如果是从右子树返回，说明当前层遍历完毕，继续退栈。

[Algorithm]: https://github.com/dangdangfeng/Algorithm
[1240]: http://upload-images.jianshu.io/upload_images/1170656-5a5492bf84d52b72.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
[1240 1]: http://upload-images.jianshu.io/upload_images/1170656-9d1a8a66d051b631.jpeg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240