阅读 474

Swift 数据结构:二叉树

这篇文章主要介绍树结构中的一种特殊存在——二叉树。主要内容有:

  • 二叉树的概念
  • 二叉树的基本结构
  • 二叉树的操作

概念

  • 二叉树: 每个结点最多有两个子结点,两个子结点是有次序的,且子结点次序不能颠倒。两个子结点一般称之为左结点及右结点。

  • 层次: 在树中,节点的层次从根开始定义,根为第一层。

  • 深度: 树中节点的最大层次为树的深度。

  • 度: 结点拥有的结点数。

  • 分支结点: 度不为0的结点。

  • 叶子节点: 度为0的结点。

  • 特殊二叉树

    • 满二叉树:所有分支结点都存在左右两节点,并且所有叶子结点都在同一层。
    • 斜树:所有的结点都只有左子结点或者右子结点。
    • 完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<=i<=n)的结点 与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则称之为完全二叉树。
    • 二叉查找树:左子树中节点的值都小于根节点的值,右子树中节点的值都大于根节点的值。

结构

顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系。使用顺序存储结构表现二叉树的时候,在其线性结构中,会存在一些空结点,但是其会占据一定的内存空间,会造成存储空间的浪费。

链式存储结构

由于二叉树的每个结点最多有两个孩子,所以为每个结点设计一个数据域和两个指针域。

结点的定义

结点的结构定义:

class TreeNode {
    var value: String
    var left: TreeNode?
    var right: TreeNode?
    
    init(_ value: String) {
        self.value = value
    }
}
复制代码

操作

创建二叉树

现在我们创建一棵如图所示的二叉树:

预期

为了能让每个结点确认是否有左右子结点,我们将预期二叉树进行一个扩展:

扩展

我们给每一个结点的空指针引出一个虚结点,其值为一个特定值——#。

创建这棵二叉树代码:

let arr = ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"]
var index = 0

func preCreateTree(_ tree: inout BinaryTreeNode?) {
    if index > arr.count-1 {
        return
    }

    let value = arr[index]

    index += 1

    if value == "#" {
        tree = nil
    } else {
        // 生成根结点
        tree = BinaryTreeNode(value)

        // 构造左子树
        preCreateTree(&tree!.leftChild)

        // 构造右子树
        preCreateTree(&tree!.rightChild)
    }
}

var root: BinaryTreeNode? = BinaryTreeNode(nil)

preCreateTree(&root)
复制代码

遍历

二叉树的遍历主要分为四种:

  • 前序遍历: 根结点-->左子树-->右子树。
  • 中序遍历: 左子树-->根结点-->右子树。
  • 后序遍历: 左子树-->右子树-->根结点。
  • 层序遍历: 从上至下一层一层遍历。

前序遍历

前面创建二叉树时,我们有一个数组 ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"],这个数组是如何得到的呢?

就是根据前序遍历扩展二叉树的结果得到的这个数组,并利用这个数组前序创建了我们预期的二叉树。

前序遍历代码:

func preOrderTraverse(_ tree: BinaryTreeNode?) {
    if let node = tree {
        print("value is \(node.value)")

        // 先序遍历左子树
        preOrderTraverse(node.leftChild)

        // 再先序遍历右子树
        preOrderTraverse(node.rightChild)
    }
}
复制代码

中序遍历

中序遍历代码:

func inOrdertraverse(_ tree: BinaryTreeNode?) {
    if let node = tree {
        // 中序遍历左子树
        inOrdertraverse(node.leftChild)

        print("value is \(node.value)")

        // 中序遍历右子树
        inOrdertraverse(node.rightChild)
    }
}
复制代码

后序遍历

后序遍历代码:

func lastOrdertraverse(_ tree: BinaryTreeNode?) {
    if let node = tree {
        // 后序遍历左子树
        lastOrdertraverse(node.leftChild)

        // 后序遍历右子树
        lastOrdertraverse(node.rightChild)

        print("value is \(node.value)")
    }
}
复制代码

层序遍历

层序遍历代码:

func levelOrdertraverse(_ tree: BinaryTreeNode?) {
    guard let root = tree else {
        return
    }
    
    var tempQueue: [BinaryTreeNode] = []
    
    // 将根节点加入数组
    if let _ = root.value {
        tempQueue.insert(root, at: 0)
    }
    
    while tempQueue.count != 0 {
    	  // 取出数组最后一个元素
        let temp = tempQueue.popLast()!
        
        // 将下一层结点依次插入到数组最前面
        if let l = temp.leftChild, l.value != nil {
            tempQueue.insert(l, at: 0)
        }
        
        if let r = temp.rightChild, r.value != nil {
            tempQueue.insert(r, at: 0)
        }
        
        print(temp.value)
    }
}
复制代码

树的最大深度

func maxDepth(_ tree: BinaryTreeNode?) -> Int {
    guard let root = tree else {
        return 0
    }
    
    return max(maxDepth(root.leftChild), maxDepth(root.rightChild)) + 1
}
复制代码

推导遍历结果

遍历特点:

前序遍历: 根结点-->左子树-->右子树。

中序遍历: 左子树-->根结点-->右子树。

后序遍历: 左子树-->右子树-->根结点。

根据遍历特点,得出解题思路:

  1. 找到根-->找到左右子树
  2. 一直重复这个操作,直到最后一个子节点。

题目一:求后序遍历

题目: 已知前序遍历 ABDGHCEIF 及中序遍历 GDHBAEICF,求出后序遍历顺序?

解答:

  1. 先序遍历的结果是ABDGHCEIF,根据先序得到根节点是A;中序遍历的结果是GDHBAEICF,根据中序得到A之前的节点都是左子树,A之后的节点都是右子树。

  2. 再对左右子树进行第一步的分析。最终能得到二叉树的完整结构。

过程分析

题目二:求前序遍历

题目: 已知后序遍历 GHDBIEFCA 及中序遍历 GDHBAEICF,求出后序遍历顺序?

解答:

  1. 后序遍历的结果是GHDBIEFCA,根据先序得到根节点是A;中序遍历的结果是GDHBAEICF,根据中序得到A之前的节点都是左子树,A之后的节点都是右子树。
  2. 再对左右子树进行第一步的分析。最终能得到二叉树的完整结构。

过程分析

总结一下

  1. 已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。
  2. 已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

但是,已知前序和后序是不能确定一棵二叉树的。

例如:前序遍历序列为 ABC 及后序遍历序列为 CBA。

可以确定 A 一定是根节点,但是接下来无法确定哪些是左子树,哪些是右子树。此时,这棵二叉树有以下四种可能:

可能

关注下面的标签,发现更多相似文章
评论