100 天 iOS 数据结构与算法实战 Day 13：Binary Tree（上）

一张图来描述Binary Tree

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

Binary Tree的几个常见类型

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

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

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

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

和Binary Tree有关的一些公式

代入求和

等比数列求和可以参考如下链接：https://zh.wikipedia.org/wiki/%E7%AD%89%E6%AF%94%E6%95%B0%E5%88%97

• 度为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

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

关注公众号关注最新动态

Github地址

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm

如果感觉写的还行，请点击文章末尾在看。