什么是树
树是由结点和边组成的，不存在环的一种数据结构。看下图：
image
与树相关的术语
-
树的结点（node）：包含一个数据元素及若干指向子树的分支；
-
孩子结点（child node）：结点的子树的根称为该结点的孩子；
-
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
-
兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；
-
叶子结点：也叫终端结点，是度为 0 的结点；
-
树的深度：树中最大的结点层数；
二叉树是什么
二叉树是一种被高频使用的特殊树。在二叉树中，每个结点最多有两个分支，即每个结点最多有两个子结点，分别称作左子结点和右子结点。
在二叉树中，有下面两个特殊的类型：
满二叉树，定义为只有最后一层无任何子结点，其他所有层上的所有结点都有两个子结点的二叉树。
image
完全二叉树，定义为除了最后一层以外，其他层的结点个数都达到最大，并且最后一层的叶子结点都靠左排列。
image
完全二叉树看上去并不完全，但为什么这样称呼它呢？这和二叉树的存储有关系。存储二叉树有两种办法，一种是基于指针的链式存储法，另一种是基于数组的顺序存储法。
链式存储法，也就是像链表一样，每个结点有三个字段，一个存储数据，另外两个分别存放指向左右子结点的指针，如下图所示：
image
顺序存储法，就是按照规律把结点存放在数组里，如下图所示，为了方便计算，我们会约定把根结点放在下标为 1 的位置。随后，B 结点存放在下标为 2 的位置，C 结点存放在下标为 3 的位置，依次类推。
image
存储方法：
image
根据这种存储方法，我们可以发现如果结点 X 的下标为 i，那么 X 的左子结点总是存放在 2 * i 的位置，X 的右子结点总是存放在 2 * i + 1 的位置。
之所以称为完全二叉树，是从存储空间利用效率的视角来看的。对于一棵完全二叉树而言，仅仅浪费了下标为 0 的存储位置。而如果是一棵非完全二叉树，则会浪费大量的存储空间。
image
树的基本操作
- 树的遍历
遍历一棵树，有非常经典的三种方法，分别是前序遍历、中序遍历、后序遍历。这里的序指的是父结点的遍历顺序，前序就是先遍历父结点，中序就是中间遍历父结点，后序就是最后遍历父结点。不管哪种遍历，都是通过递归调用完成的。
前序遍历，对树中的任意结点来说，先打印这个结点，然后前序遍历它的左子树，最后前序遍历它的右子树。
中序遍历，对树中的任意结点来说，先中序遍历它的左子树，然后打印这个结点，最后中序遍历它的右子树。
后序遍历，对树中的任意结点来说，先后序遍历它的左子树，然后后序遍历它的右子树，最后打印它本身。
image
三种遍历方式的代码方式：
// 先序遍历
func preOrder( _ root: TreeNode?) {
guard let rt = root else {
return
}
print(rt.val)
preOrder(rt.left)
preOrder(rt.right)
}
// 中序遍历
func inOrderTraverse(_ root: TreeNode?) {
guard let rt = root else {
return
}
preOrder(rt.left)
print(rt.val)
preOrder(rt.right)
}
// 后序遍历
func postOrderTraverse(_ root: TreeNode?) {
guard let rt = root else {
return
}
preOrder(rt.left)
preOrder(rt.right)
print(rt.val)
}
二叉树遍历过程中，每个结点都被访问了一次，其时间复杂度是 O(n)。执行增加和删除数据的操作时，在找到位置后,我们只需要通过指针建立连接关系就可以了。对于没有任何特殊性质的二叉树而言，抛开遍历的时间复杂度以外，真正执行增加和删除操作的时间复杂度是 O(1)。
这里穿插讲下递归
递归是指在函数的定义中使用函数自身的方法。
递归有两层含义：
- 递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题。并且这些子问题可以用完全相同的解题思路来解决；
- 递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点）。一旦原问题到达了这个临界点，就不用再往更小的问题上拆解了。最后，从这个临界点开始，把小问题的答案按照原路返回，原问题便得以解决。
通过二叉树的定义和特性可知，二叉树的遍历可用递归的方式处理，临界点是叶子结点的左子树和右子树皆为空，为空就return返回了。
二叉查找树
二叉查找树（也称作二叉搜索树）具备以下几个的特性：
- 在二叉查找树中的任意一个结点，其左子树中的每个结点的值，都要小于这个结点的值。
- 在二叉查找树中的任意一个结点，其右子树中每个结点的值，都要大于这个结点的值。
- 在二叉查找树中，会尽可能规避两个结点数值相等的情况。
- 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。
二叉查找树的查找操作
在利用二叉查找树执行查找操作时，我们可以进行以下判断：
- 首先判断根结点是否等于要查找的数据，如果是就返回。
- 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。
- 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。
这样的“二分查找”所消耗的时间复杂度就可以降低为 O(logn)。代码如下：
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let rt = root else {
return nil
}
if rt.val > val {
return searchBST(rt.left, val)
} else if rt.val < val {
return searchBST(rt.right, val)
} else {
return rt
}
}
二叉查找树的增加操作
从根结点开始，如果要插入的数据比根结点的数据大，且根结点的右子结点不为空，则在根结点的右子树中继续尝试执行插入操作。直到找到为空的子结点执行插入动作。
二叉查找树插入数据的时间复杂度是 O(logn)。但这并不意味着它比普通二叉树要复杂。原因在于这里的时间复杂度更多是消耗在了遍历数据去找到查找位置上，真正执行插入动作的时间复杂度仍然是 O(1)。
func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let currNode = root else {
return TreeNode(val)
}
if val > currNode.val {
root?.right = insertIntoBST(root?.right, val)
} else {
root?.left = insertIntoBST(root?.left, val)
}
return root
}
二叉查找树的删除操作
/*
根据二叉搜索树的性质
如果目标节点大于当前节点值，则去右子树中删除；
如果目标节点小于当前节点值，则去左子树中删除；
如果目标节点就是当前节点，分为以下三种情况：
其无左子：其右子顶替其位置，删除了该节点；
其无右子：其左子顶替其位置，删除了该节点；
其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
*/
func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
guard var root = root else {
return nil
}
if key > root.val {
root.right = deleteNode(root.right, key)
} else if key < root.val{
root.left = deleteNode(root.left, key)
} else {
if nil == root.right {
return root.left
} else if nil == root.left {
return root.right
} else if let _ = root.right, let _ = root.left {
var temp = root.right
while let _ = temp?.left {
temp = temp?.left
}
temp?.left = root.left
if let right = root.right {
root = right
}
}
}
return root
}
总结
本文主要讲解的是二叉树的基本理解和操作，理解二叉树的各类操作无外乎查增删，链式二叉树增删的时间复杂度都是0(1),真正耗时的是查，时间复杂度是O(logn)，所以二叉树的增删查的时间复杂度都是0(logn)。另外二叉树的查找分两种，深度优先遍历还是广度优先遍历，本文讲的都是深度优先的查找操作即递归。
网友评论