二叉树
二叉树中的每一个节点最多只有两个子节点，通常被称为左子节点、 右子节点
graph1.png
二叉树的Swift实现
public class BinaryNode<Element: Equatable> {
public var value: Element
public var leftChild: BinaryNode?
public var rightChild: BinaryNode?
public var parentNode: BinaryNode?
public init(value: Element) {
self.value = value
}
}
二叉树图形打印
将二叉树进行图形化打印
extension BinaryNode: CustomStringConvertible {
public var description: String {
return diagram(for: self)
}
private func diagram(for node: BinaryNode?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.leftChild == nil && node.rightChild == nil {
return root + "\(node.value)\n"
}
return diagram(for: node.rightChild,
top + " ", top + "┌──", top + "│ ")
+ root + "\(node.value)\n"
+ diagram(for: node.leftChild,
bottom + "│ ", bottom + "└──", bottom + " ")
}
}
对二叉树进行打印
var tree: BinaryNode<Int> = {
let zero = BinaryNode(value: 0)
let one = BinaryNode(value: 1)
let five = BinaryNode(value: 5)
let seven = BinaryNode(value: 7)
let eight = BinaryNode(value: 8)
let nine = BinaryNode(value: 9)
let eleven = BinaryNode(value: 11)
seven.leftChild = one
one.parentNode = seven
one.leftChild = zero
one.rightChild = five
seven.rightChild = nine
nine.parentNode = seven
nine.leftChild = eight
zero.parentNode = one
five.parentNode = one
eight.parentNode = nine
return seven
/*
7
/ \
1 9
/ \ /
0 5 8
*/
}()
print(tree)
┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
遍历
根据父节点的访问顺序可以将二叉树的遍历分为前序遍历,中序遍历，后序遍历。
前序遍历
节点的访问次序为 父节点->左节点->右节点
graph3.png
/*
前序遍历节点值
*/
func traversePreOrder(visit:(Element)->()) {
visit(self.value)
leftChild?.traversePreOrder(visit: visit)
rightChild?.traversePreOrder(visit: visit)
}
tree.traversePreOrder { (value) in
print(value)
}
结果为：7 1 0 5 9 8
中序遍历
节点的访问次序为 左节点->父节点->右节点
graph2.png
/*
中序遍历
*/
func traverseInOrder(visit:(Element)->()) {
leftChild?.traverseInOrder(visit: visit)
visit(self.value)
rightChild?.traverseInOrder(visit: visit)
}
结果为： 0 1 5 7 8 9
后序遍历
节点的访问次序为 左节点->右节点->父节点
graph4.png
/*
后序遍历
*/
func traversePostOrder(visit:(Element)->()){
leftChild?.traversePostOrder(visit: visit)
rightChild?.traversePostOrder(visit: visit)
visit(self.value)
}
结果为：0 5 1 8 9 7
同级遍历
节点的访问次序：先访问同一层的节点，然后在访问下一层的节点。
借助于队列，当节点出队时，将其左右子节点入队，当队列为空时，访问结束。
/*
同级遍历
*/
func traverSameLevel(visit:(Element?) ->()) {
var queue = QueueArray<BinaryNode?>()
queue.enqueue(self)
while let node = queue.dequeue() {
if let leftChild = node?.leftChild {
queue.enqueue(leftChild)
}
if let rightChild = node?.rightChild {
queue.enqueue(rightChild)
}
visit(node?.value)
}
}
结果为: 7 1 9 0 5 8
二叉搜索树
- 一个父节点最多只有两个子节点
- 左子节点的值必须小于其父节点
- 右子节点的值必须大于其父节点
/**
1, Left Child 小于 Parent
2, Right Child 大于 Parent
*/
public struct BinarySearchTree<Element: Comparable> {
public private (set) var root: BinaryNode<Element>?
public init() {}
}
extension BinarySearchTree: CustomStringConvertible {
public mutating func insert(_ value: Element) {
root = insert(from: root, value: value)
}
private func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> {
guard let node = node else {
return BinaryNode(value: value)
}
if value < node.value {
let newNode = insert(from: node.leftChild, value: value)
node.leftChild = newNode
newNode.parentNode = node
} else {
let newNode = insert(from: node.rightChild, value: value)
node.rightChild = newNode
newNode.parentNode = node
}
return node
}
public var description: String {
guard let root = root else { return "Empty tree" }
return String(describing: root)
}
}
二叉搜索树的前驱节点
前驱节点：中序遍历时该节点的前一个节点，在二叉搜索树中，前驱节点就是前一个比它小的节点。
在二叉搜索树中，中序遍历得到的结果其实是从小到大的结果
- 如果
node.left != nil，predecessor = node.left.right.right...直到right == nil为止 - 如果
node.left==nil，node.parent != nil，该节点为最小值，则prodecessor = node.parent.parent...
终止条件：node在parent的右子树中
func processorNode(_ node: BinaryNode<Element>) -> BinaryNode<Element>? {
// 如果 node.left != nil, prodecessor = node.left.right.right...直到 right 为 nil 为止
if node.leftChild != nil {
var childNode = node.leftChild
while childNode?.rightChild != nil {
childNode = childNode?.rightChild
}
return childNode
}
// 如果 左子节点为nil，父节点不为nil，该节点为最小值，则 prodecessor = node.parent.parent...
// 终止条件： node在parent的右子树中
else if node.leftChild == nil && node.parentNode != nil {
var cur = node
while cur.parentNode != nil && !(cur.parentNode?.rightChild?.containNode(node) ?? false) {
cur = cur.parentNode!
}
return cur.parentNode
}
else {
// node.leftChild == nil && node.parentNode == nil
return nil
}
二叉搜索树的后驱节点
后驱节点：中序遍历时该节点的后一个节点，在二叉搜索树中，后驱节点就是后一个比它大的节点。
/*
后驱节点：中序遍历时的后一个节点
在二叉搜索树中就是后一个比它大的节点
*/
func successorNode(_ node: BinaryNode<Element>) -> BinaryNode<Element>? {
if node.rightChild != nil {
var childNode = node.rightChild
while childNode?.leftChild != nil {
childNode = childNode?.leftChild
}
return childNode
}
else if node.rightChild == nil && node.parentNode != nil {
var cur = node
while cur.parentNode != nil && !(cur.parentNode?.leftChild?.containNode(node) ?? false) {
cur = cur.parentNode!
}
return cur.parentNode
}
else {
return nil
}
}
Challenage
1,计算一个二叉搜索树的高度。
- 使用递归
func treeHeight() -> Int {
return 1 + max(self.rightChild?.treeHeight() ?? 0 , self.leftChild?.treeHeight() ?? 0)
}
- 使用迭代
借助于同级遍历的思想,levelSize是该层的节点数量，当队列出队时，levelSize - 1,当levelSize == 0该层的节点已完全访问，下一层的子节点已全部入队，此时队列数量为下一层的节点总数量，如果队列数量不为0，则高度加1。当levelSize == 0 && queue.count == 0的时候，遍历结束
func treeHeightIteration() -> Int {
var queue = QueueArray<BinaryNode?>()
queue.enqueue(self)
var levelSize = 1 // 同一级包含的节点数
var height = 1 // 树的高度
while let node = queue.dequeue() {
// 出队时 levelSize - 1
levelSize -= 1
if let leftChild = node?.leftChild {
queue.enqueue(leftChild)
}
if let rightChild = node?.rightChild {
queue.enqueue(rightChild)
}
// 当levelSize == 0时，同一级的已完全出队
if levelSize == 0 && queue.count != 0{
height += 1
levelSize = queue.count
}
}
return height
}
2,判断一个树是否为完全二叉树
完全二叉树:叶子节点只会出现在最后2层，最后一层的叶子结点都靠左对齐
对二叉树采用同层遍历
- 当左子节点不为空，将左子节点入队
- 当左子节点为空，右子节点不为空，返回 false
- 当右子节点不为空，将右子节点入队
- 当右子节点为空时，以后遍历的所有节点应该都为叶子节点，才是完全二叉树
//MARK: -- 判断一棵树是否为完全二叉树
/*
使用同级遍历每一个节点
*/
func isFullBinaryNode() -> Bool {
var queue = QueueArray<BinaryNode?>()
queue.enqueue(self)
var needLeafNode = false
while let node = queue.dequeue() {
if needLeafNode && (node?.leftChild != nil || node?.rightChild != nil) {
return false
}
// 当左子节点不为空，将左子节点入队
if let leftChild = node?.leftChild {
queue.enqueue(leftChild)
}
// 当左子节点为空，右子节点不为空，返回 false
if node?.leftChild == nil && node?.rightChild != nil {
return false
}
// 当右子节点不为空，将右子节点入队
if let rightChild = node?.rightChild {
queue.enqueue(rightChild)
}else {
// 当右子节点为空时，以后遍历的所有节点应该都为叶子节点，才是完全二叉树
needLeafNode = true
}
}
return true
}
3,对二叉搜索树进行序列化
对一下二叉树进行序列化
graph5.png
序列化结果为
[15, 10, 5, nil, nil, 12, nil, nil, 25, 17, nil, nil, nil]
func traverSearialPreOrder(visit:(Element?)->()) {
visit(self.value)
if let left = leftChild {
left.traverSearialPreOrder(visit: visit)
}else {
visit(nil)
}
if let right = rightChild {
right.traverSearialPreOrder(visit: visit)
}else {
visit(nil)
}
}
4,判断一个树是否是 二叉搜索树
借助于栈，对二叉树进行中序遍历。二叉搜索树中序遍历的结果是从小到大的结果
extension NSObject {
// static
static func isValidBST(_ node: BinaryNode<Int>?) -> Bool {
var cur = node
var nodeStack = Stack<BinaryNode<Int>>()
var minNumber = Int.min
while !nodeStack.isEmpty() || cur != nil {
while cur != nil {
nodeStack.push(cur!)
cur = cur?.leftChild
}
cur = nodeStack.pop()
print(cur?.value ?? 0)
if cur?.value ?? 0 < minNumber { return false }
minNumber = cur?.value ?? 0
cur = cur?.rightChild
}
return true
}
}
最后附上本文的相关代码DataAndAlgorim
网友评论