iOS数据结构与算法实战 Binary Trees 上

二叉树的节点最大分支度是2，也说明每个节点最多拥有2个子节点，范围是[0-2]。

Binary Tree的几个常见类型

• A degenerate (or pathological) tree。（树的每个节点只有一个子节点或者是右孩子或者是左孩子，这时候这个树就和链表性能差不多了。）

• Full Binary Tree （树的任何一个节点都有0或者2个孩子节点。或者这样定义树的任何一个非叶子节点都有两个孩子节点）

• Complete Binary Tree（可能除了树的最后一层其它层级的每个节点都有左右孩子节点，最后一层要么是满的要么节点都靠左边）

  

  

• Perfect Binary Tree （它是一个这样的二叉树，他所有的非叶子节点都有左右子节点，并且所有的叶子节点都在同一层级）

和Binary Tree有关的一些公式

• 节点数和二叉树树Height的关系，假如h是树的Height，n是树节点个数。那么Min Nodes(n = h+1),Max Nodes(2 ^h+1 -1)。看下图例子，很容易推导出Min Nodes(n = h+1)。

  

  

下面我们推导下Max Nodes。上图第三种情况h = 3，Max Nodes = 1 +2 + 2 ² + 2 ³ = 15，也就是Max Nodes = 1 +2 + 2 ² + 2 ³ + ....+ 2 ^h = ,也就是等比数列求和，如下图：

-1

等比数列求和可以参考如下链接： zh.wikipedia.org/wiki/等比数列

反过来可以很容易推导出Min Height (h = Log ₂ (n+1)-1),Max Height(h = n-1)。

• 如果是full binary tree那么节点数和树Height的关系又是什么呢？ 推导过程可以参考上面的步骤，Min Nodes(n = 2h+1),Max Nodes(2 ^h+1 -1)，反过来可以很容易推导出Min Height (h = Log ₂ (n+1)-1),Max Height(h = )。

• 第i层至多拥有2 ^i-1 个节点，最少有1个节点。从下图可以很容易看出来，

  

• 度为0的节点数n1和度为2节点数n2的关系。n1 = n2 + 1。看下图

  

二叉树的存储方式

• Array Representation
• Linked Representation

Array Representation

二叉树可以被以广度优先的顺序作为隐式数据结构存储在数组中。注意的是如果这个二叉树是complete binary tree，这些不会浪费空间，但是如果对于A degenerate (or pathological) tree这种高度很大的树就很浪费空间，可以参考后面根据这个存储方式判断这个树是不是complete binary tree的介绍。这种存储方法通常也用在binary heaps。

举例：找E的父节点，E的索引是5，那么Parent = i/2 = 5/2 = 2.5,向下取整就是2，对应的就是B。反之假如找A的左右孩子，A的索引是1，那么左孩子索引就是2对应B，右孩子索引就是3对应C。

注意：Parent的索引如果有存在小数情况是向下取整。

下面我们看怎么根据这个表示方法判断是不是complete binary tree。

上三个图中1，2元素之间没有空白的空间是complete binary tree，图3元素之间有空白的空间说明不是complete binary tree。

Linked Representation

@interface DSTreeNode : NSObject

@property (nonatomic, strong) NSObject   *object;
@property (nonatomic, strong) DSTreeNode *leftChild;
@property (nonatomic, strong) DSTreeNode *rightChild;
@property (nonatomic, strong) DSTreeNode *parent;
@property (nonatomic, assign) SEL         compareSelector;


- (void)printDescription;
//是否是左还是结点
- (BOOL)isLeftChildOfParent;


@end
复制代码

这种存储二叉树方法浪费了不少内存,由于那些节点的左右指针（为null或者指向某些节点）。