二叉树的实现原理
- 组成结构
二叉树是由根节点与左右子树连接起来的数据结构。所以实现一棵二叉树，有两个必要结构数据：
-
节点数据结构用来连通各个节点 -
树结构用来包裹节点数据
- 节点数据的实现
节点数据有两点主要功能：
- 存放数据元素
- 能够连接左右节点
依据这些特点，可以使用下面的方式构建节点数据：
typealias BinaryTreeCompare = Comparable & Equatable
class Child<E: BinaryTreeCompare> : Equatable{
static func == (lhs: Child<E>, rhs: Child<E>) -> Bool {
let compareResult =
lhs.element == rhs.element &&
lhs.left == rhs.left &&
lhs.right == rhs.right
return compareResult
}
var element: E
var left: Child?
var right: Child?
init(element: E, left: Child?, right: Child?) {
self.element = element
self.left = left
self.right = right
}
func isLeaf() -> Bool { left == nil && right == nil }
func hasTwoChild() -> Bool { left != nil && right != nil }
}
- 二叉树结构内容的实现
树的结构是对其节点的包装，有这以下几个特点：
- 每棵二叉树都有一个
根节点root - 每一棵二叉树都有着其自己的容量大小
size - 添加新的
节点 - 移除每一棵树的某个节点
节点 - 清除一棵树的
所有节点 - 查找某个特定节点
是否存在
依据其功能特点，就抽象出了几个必要的基础接口，如下：
protocol BinaryTreeProtocol : CustomStringConvertible {
associatedtype T: BinaryTreeCompare
//根节点
var root: Child<T>? { set get }
//节点添加
mutating func add(element: T)
//清除二叉树所有节点
mutating func clear()
//移出特定节点元素
mutating func remove(element: T)
//获取容量
func size() -> Int
//是否为空
func isEmpty() -> Bool
//是否包含某个特定元素节点
func contains(element: T) -> Bool
}
具体实现
结构构建完成之后，依据抽象内容实现树的结构，直接实现第二步抽象出来的接口即可，如下：
struct BinaryTree<E: BinaryTreeCompare>: BinaryTreeProtocol {
var root: Child<E>?
var length: Int = 0
var binaryTreeTravelsal: BinaryTreeTraversal<E>?
typealias T = E
init() {
root = nil
}
init(travelsal: BinaryTreeTraversal<E>?) {
self.init()
self.binaryTreeTravelsal = BinaryTreeTraversal<E>()
}
mutating func add(element: E) {
if root == nil {
root = Child(element: element, left: nil, right: nil)
return
}
var child = root
var parent = root
var compareResult: BinaryTreeCompareResult?
while child != nil {
parent = child
if element > child!.element {
child = child?.right
compareResult = .BiggerThanRight
}else if element < child!.element {
child = child?.left
compareResult = .BiggerThanLeft
}else {
compareResult = .Equal
}
}
let childNode = Child(element: element, left: nil, right: nil)
if BinaryTreeCompareResult.BiggerThanLeft == compareResult {
parent?.left = childNode
length += 1
}else if BinaryTreeCompareResult.BiggerThanRight == compareResult {
parent?.right = childNode
length += 1
}
}
mutating func clear() {
root = nil
length = 0
}
mutating func remove(element: E) {
if root == nil { return }
var child = root
var parent = root
var compareResult: BinaryTreeCompareResult?
while child != nil {
if element > child!.element {
parent = child
child = child?.right
compareResult = .BiggerThanRight
}else if element < child!.element{
parent = child
child = child?.left
compareResult = .BiggerThanLeft
}else {
if compareResult == .BiggerThanRight {
parent?.right = nil
}else if compareResult == .BiggerThanLeft {
parent?.left = nil
}
length -= 1
break
}
}
}
func size() -> Int { length }
func isEmpty() -> Bool { length == 0 }
func contains(element: E) -> Bool {
var child = root
while child != nil {
if element > child!.element {
child = child!.left
}else if element < child!.element {
child = child!.right
}else {
return true
}
}
return false
}
var description: String {""}
}
二叉树的遍历
二叉树的遍历方式有以下几种：
- 前序遍历：
头节点先遍历，再依次遍历左子树与右子树 - 中序遍历：
左子树先遍历，再遍历头节点，最后遍历右子树 - 后序遍历：
左子树先遍历，再依次遍历右子树，最后遍历头节点 - 层序遍历：按照
二叉树的层级一层一层的往下遍历（这个在实现树的深度，以及判断是否是一棵完全二叉树中和查找中序遍历的前驱节点与后继节点等中用到，很重要）
这里的 前序、中序、后序 是指节点的遍历的先后顺序。这几种遍历可以通过 递归来实现，而最后的 层序遍历 ，在进行每一层 遍历 的时候，有着队列的 先进先出的特点，可以考虑将 节点放入到队列中，然后通过队列的 出队 间接实现层级的遍历，而终止条件就是 队列的长度为空 的时候。
/*
二叉搜索树遍历的几种方法：
1. 前序遍历 (PreOrder Traversal)
2. 中序遍历 (InOrder Traversal)
3. 后序遍历（Postorder Traversal）
4. 层序遍历（Level Order Traversal）
*/
class BinaryTreeTraversal<E : Equatable & Comparable> {
/*
前序遍历
*/
func preOrderTraversal(root: Child<E>?) {
if root == nil {
return
}
print(root!.element,terminator: " ")
// print(_ items: Any..., separator: String = " ", terminator: String = "\n")
preOrderTraversal(root: root?.left)
preOrderTraversal(root: root?.right)
}
/*
中序遍历
*/
func inOrderTraversal(root: Child<E>?) {
if root == nil {
return
}
inOrderTraversal(root: root?.left)
print(root!.element,terminator: " ")
inOrderTraversal(root: root?.right)
}
/*
后序遍历
*/
func postOrderTraversal(root: Child<E>?) {
if root == nil {
return
}
postOrderTraversal(root: root?.left)
postOrderTraversal(root: root?.right)
print(root!.element,terminator: " ")
}
/*
层序遍历（一层一层遍历）
*/
func levelOrderTraversal(root: Child<E>) {
var queue = SignalQueue<Child<E>>()
queue.enQueue(element: root)
var travelsalStr = "["
while !queue.isEmpty() {
let node = queue.deQueue()
travelsalStr.append("\(node!.element) ")
if let left = node?.left {
queue.enQueue(element: left)
}
if let right = node?.right {
queue.enQueue(element: right)
}
}
travelsalStr.removeLast()
travelsalStr.append("]")
print("\(travelsalStr)")
}
/*
层序遍历（一层一层遍历）
*/
func levelOrderTraversalCustom(root: Child<E>, enumtorEachClosure: (Child<E>)-> Bool) {
var queue = SignalQueue<Child<E>>()
queue.enQueue(element: root)
while !queue.isEmpty() {
let node = queue.deQueue()
if enumtorEachClosure(node!) {
return
}
if let left = node?.left {
queue.enQueue(element: left)
}
if let right = node?.right {
queue.enQueue(element: right)
}
}
}
}
关于搜索二叉树的节点删除（删除判断依据是按照该节点的度进行相应的调整）
二叉树的节点删除不要理解为是节点连同节点的左右子树一起删除，二叉树的节点删除是仅仅删除某个节点，但是删除节点的孩子节点还需要保留。所以针对于要删除的节点分为三种情况：
- 拥有两个孩子节点的情况（度为2）
- 拥有一个孩子节点的情况（度为1）
- 删除的节点是叶子结点（度为0）
- 删除的节点是根节点且只有一个子树
针对于三种情况下的删除，每种情况单独分析：
- 拥有两个孩子节点的情况
删除该节点之后由于没有了以当前节点为树的 根节点，所以需要找一个节点去 取代当前节点的位置，由于 二叉搜索树 有顺序大小，所以按照搜索树的特点，删除节点之后，这个顺序依然能够保持。
依据这个特点，可以通过二叉搜索树的 前驱节点 以及 后继节点 来替换要 删除的节点，同时能够保证其正常替代节点的功能。
- 拥有一个孩子节点的情况
如果 删除的节点node 只拥有一个孩子节点，需要用 子节点child 去替换删除的 节点node。这里要区分孩子 节点是左节点 还是 右节点
- 如果
child是左节点
child.parent = node.parent
node.parent.left = child
- 如果
child是右节点
child.parent = node.parent
node.parent.right = child
- 删除的节点是叶子节点
如果删除的节点是叶子结点，可以直接进行删除
node.parent = nil
- 删除的是根节点
root = child
child.parent = nil
综合上面的所有情况，可以实现删除方法
mutating func deleteNode(node: inout Child<E>){
//含有两个孩子（度为2的情况）
if node.hasTwoChild() {
if let behindNode = behindChildInOrderTree(node) {
//放入到根节点
node.element = behindNode.element
//指向当前的后继节点
node = behindNode
}
}
//节点度为1或者0的情况
let replaceNode = node.left != nil ? node.left : node.right
if replaceNode != nil {
//更换删除的子节点的父节点为删除子节点的父节点
replaceNode?.parent = replaceNode?.parent
if node.parent == nil{
root = replaceNode
replaceNode?.parent = nil
}else if node == replaceNode?.parent?.left {
replaceNode?.parent?.left = replaceNode
}else if node == replaceNode?.parent?.right{
replaceNode?.parent?.right = replaceNode
}
}
//叶子节点
else {
if node == node.parent?.left {
node.parent?.left = nil
}else {
node.parent?.right = nil
}
}
}
如何判断一棵树是否为完全二叉树
完全二叉树 的特点：可以理解为 满二叉树 多一层不满的情况，同时 满二叉树 也是一棵 完全二叉树。通过 层序遍历 树的节点来完成判定：
- 当前节点有两个孩子节点，继续向后遍历
- 当前节点不含有左孩子只含有右孩子，不是完全二叉树，直接返回
- 当前节点
不含有左孩子，也不含有右孩子，遍历后序节点，后序节点需要满足均为叶子节点才能满足其是完全二叉树 - 当前节点
含有左孩子，不含有右孩子，遍历后序节点，后序节点需要满足均为叶子节点才能满足其是完全二叉树
按照判定标准，可以实现其内容：
/*
通过直接判断当前节点是否满足情况，正常方案
*/
func compeleteTreeNormalMethod(root: Child<Int>) -> Bool {
var travelsalQueue = SignalQueue<Child<Int>>()
travelsalQueue.enQueue(element: root)
var isJudgeLeaf = false
while !travelsalQueue.isEmpty() {
let child = travelsalQueue.deQueue()
//判断是否是叶子节点
if isJudgeLeaf && !child!.isLeaf() {
return false
}
//正常节点，继续遍历下面的节点
if child!.hasTwoChild(){
travelsalQueue.enQueue(element: root.left!)
travelsalQueue.enQueue(element: root.right!)
}else if child?.left == nil && child?.right != nil {
return false
}else {
//注意当前如果左孩子不为空，需要将左孩子加入到队列以全部节点能够正常遍历
if child?.left != nil {
travelsalQueue.enQueue(element: child!.left!)
}
isJudgeLeaf = true
}
}
return true
}
以上的方案可以优化一下，可以直接 判定节点的左右孩子 进而保证只需要依次遍历左右孩子就能完成一次判定，不会像上面的方案 重复多次判定左右孩子节点为空的操作。
func isCompeleteTree(root: Child<Int>) -> Bool {
var travelsalQueue = SignalQueue<Child<Int>>()
travelsalQueue.enQueue(element: root)
var judgeIsLeaf = false
while !travelsalQueue.isEmpty() {
let child = travelsalQueue.deQueue()
if judgeIsLeaf && !child!.isLeaf() {
return false
}
if child?.left != nil {
travelsalQueue.enQueue(element: child!.left!)
}else if child?.right != nil{
return false
}
//左节点为nil
if child?.right != nil {
travelsalQueue.enQueue(element: child!.right!)
}else{
//此时包含两种情况：1.左节点有值 2.左节点没有值，在这两种情况下，只需要判断后序的节点是否是叶子节点即可
//包含两种情况：1. 左节点为nil 右节点为nil 2. 左节点非nil ，右节点nil 该节点为分界节点，后序节点需要满足均为叶子节点的特征
judgeIsLeaf = true
}
//经过一次循环遍历之后，此时已经过滤如下情况：
//1. 左节点为nil、右节点含有child
//2. 左节点有值，右节点含有值
//3. 左节点与右节点同时都没有值。
}
return true
}
如何翻转二叉树
二叉树的翻转是左右子树的元素节点进行交换，如下:
50
/ \
30 60
/ \ \
20 40 70
/ \
10 25
前序： 50, 30, 20, 10, 25, 40, 60, 70
中序： 10, 20, 25, 30, 40, 50, 60, 70
后序： 10, 25, 20, 40, 30, 70, 60, 50
=========== 翻转结果 ===========
50
/ \
60 30
/ / \
70 40 20
/ \
25 10
思想：
翻转是 交换左子树与右子树 的位置，所以通过 遍历来交换两者的位置 即可，
遍历的方法有 前序遍历、中序遍历、后序遍历以及层序遍历，都是能满足条件的
/*
前序遍历实现
*/
func invertTreeUsePreOrder(root: Child<Int>?) {
if root == nil { return }
let tmp = root?.left
root?.left = root?.right
root?.right = tmp
invertTreeUsePreOrder(root: root!.left)
invertTreeUsePreOrder(root: root!.right)
}
/*
后序遍历实现
*/
func invertTreeUsePostOrder(root: Child<Int>?) {
if root == nil { return }
invertTreeUsePostOrder(root: root?.left)
invertTreeUsePostOrder(root: root?.right)
let tmp = root?.left
root?.left = root?.right
root?.right = tmp
}
/*
中序遍历实现
注意中序遍历的时候，右子树再进行子节点交换前，同级别的节点先交换了左右子树，导致右子树变成了左子树，所以此种情况下应该依旧交换左子树内容
*/
func invertTreeUseInOrder(root: Child<Int>?) {
if root == nil { return }
invertTreeUseInOrder(root: root?.left)
let tmp = root?.left
root?.left = root?.right
root?.right = tmp
invertTreeUseInOrder(root: root?.left)
}
/*
使用层序遍历来完成二叉树的翻转
*/
func invertTreeUseLevel(root: Child<Int>) {
var travelQueue = SignalQueue<Child<Int>>()
travelQueue.enQueue(element: root)
while !travelQueue.isEmpty() {
let child = travelQueue.deQueue()
let tmp = child?.left
child?.left = child?.right
child?.right = tmp
if child?.left != nil {
travelQueue.enQueue(element: child!.left!)
}
if child?.right != nil {
travelQueue.enQueue(element: child!.right!)
}
}
}
如何依据遍历结果重构一棵二叉树
能够根据遍历结果来重新构建一棵唯一的二叉树的，有以下两种情况：
- 中序遍历 + 前序遍历
- 中序遍历 + 后序遍历
特点就是两种都必须有 中序遍历， 中序遍历 是用来确定左右子树的，所以对于重构唯一的二叉树是必不可少的。由于 前序遍历 + 后序遍历 结果组合是无法确定 左右子树 的，所以也就不能够确定唯一的 二叉树
比如：
前序： 50, 30, 20, 10, 25, 40, 60, 70
中序： 10, 20, 25, 30, 40, 50, 60, 70
根据前序顺序，确定根节点为 50，在中序遍历中找到根节点位置，中序遍历中，50左边的节点为 左子树节点，右边的节点为 右子树节点，然后依据前序遍历的第二个节点30得出中序遍历30的位置，确定 50左子树的根节点为30，循环查找构建出一棵完整的树。
50
/ \
30 60
/ \ \
20 40 70
/ \
10 25
二叉树的前驱节点与后继节点查找
二叉树的 前驱节点 是针对中序遍历顺序来说的，指的 中序遍历 的节点的 前一个节点。有着以下几个特点：
- 如果存在左子树，前驱节点就是左子树最后一个遍历的节点（
while child != nil { child.left.right.right }） - 如果不存在左子树，那么前驱节点是按照当前节点的层层父节点往上找，直到当前的节点为父节点的右子树节点的时候，那么往上找到的节点的父节点就是前驱节点(
while child.parent.right != child { child = child.parent })
中序遍历顺序
二叉树的 后继节点是中序遍历节点的 后一个节点
后继节点 几点重要特性（与前驱节点恰恰相反）:
- 如果存在右子树，那么
右子树的最左边的child就是后继节点 - 如果
不存在右子树，直接找父节点，直到父节点的左孩子节点是当前节点的时候，那么该父节点就是其后继节点
结合上面的内容，可以大致实现其方法：
func preChildInOrderTree(_ target: Child<Int>) -> Child<Int>? {
var child = target
if child.left != nil {
child = child.left!
while child.right != nil {
child = child.right!
}
return child
}
//没有左子树
else {
while child.parent != nil && child.parent?.right != child {
child = child.parent!
}
return child.parent
}
}
func behindChildInOrderTree(_ target: Child<Int>) -> Child<Int>? {
var child = target
if child.right != nil {
child = child.right!
while child.left != nil {
child = child.left!
}
return child
}
//没有右子树
else {
while child.parent != nil && child.parent?.left != child {
child = child.parent!
}
return child.parent
}
}
