Swift算法之二叉树实现的方法示例

一、概述

二叉树的结构一般是以二叉链表的形式来存储的。二叉链表的结构类似于双向链表，二叉链表的节点也是有两个结点指针的，一个指向左子树，一个指向右子树。二叉树主要有四种遍历方式：先序遍历、中序遍历、后序遍历、层次遍历。关于二叉树的内容网上有很多，这里不再做过多的陈述。

本文将用Swift去实现二叉树的创建、四种遍历方式等。下面的实现部分内容参考了青玉伏案和唐巧两位大神相关的文章。

二、实现思路及代码

以下面二叉树为例：

先序遍历：先遍历根节点然后再遍历左子树，最后遍历右子树。

故上面先序遍历的顺序为： A B D E C F

不过为了看到更详细的步骤可以把上面 C 结点的左子节点的 value 值打印为#号，类似的D、E、F也一样，他们的左右子节点的 value 值都打印为#号，则打印结果为：A B D # # E # # C # F # #

中序遍历：先遍历左子树，然后遍历根节点，最后遍历右子树。

故上面先序遍历的顺序为：# D # B # E # A # C # F #

后序遍历：后序遍历是先遍历左子树，然后再遍历右子树，最后遍历根节点

故上面先序遍历的顺序为：# # D # # E B # # # F C A

层次遍历：层次遍历相对上面的几个遍历实现起来要稍微复杂，层次遍历就是图中以二叉树的根节点为起始节点的广度搜索（BFS）

故上面先序遍历的顺序为：A B C D E # F # # # # # #

下面为上述几种遍历的Swift实现：

class BinaryTreeNote{

 var value:String
 var leftChild:BinaryTreeNote?
 var rightChild:BinaryTreeNote?

 init(_ value:String) {
 self.value = value
 }

}

class BinaryTreeHelper{

 var array:[String]
 var index = -1

 init(_ array:[String]) {
 self.array = array
 }

 //创建二叉树
 func createTree() -> BinaryTreeNote? {

 self.index = self.index + 1
 if index < self.array.count && index >= 0 {

  let value = self.array[index]

  if value == "" {
  return nil
  } else {
  let note = BinaryTreeNote(value)
  note.leftChild = createTree()
  note.rightChild = createTree()
  return note
  }
 }
 return nil;
 }

 //先序遍历二叉树
 func preOrderTraverse(_ note:BinaryTreeNote?){

 if note == nil {
  print("#")
  return
 }
 print(note!.value)
 preOrderTraverse(note!.leftChild)
 preOrderTraverse(note!.rightChild)
 }

 //中序遍历二叉树
 func inOrderTraverse (_ note: BinaryTreeNote?) {
 if note == nil {
  print("#")
  return
 }
 inOrderTraverse(note!.leftChild)
 print(note!.value)
 inOrderTraverse(note!.rightChild)
 }

 //后序遍历二叉树
 func afterOrderTraverse (_ note: BinaryTreeNote?) {
 if note == nil {
  print("#")
  return
 }
 afterOrderTraverse(note!.leftChild)
 afterOrderTraverse(note!.rightChild)
 print(note!.value)
 }

 //层次遍历二叉树
 func levelOrder(_ root: BinaryTreeNote?){

 var result = [[BinaryTreeNote]]()
 var level = [BinaryTreeNote]()

 level.append(root!)
 while level.count != 0 {
  result.append(level)
  var nextLevel = [BinaryTreeNote]()
  for node in level {
  if let leftNode = node.leftChild {
   nextLevel.append(leftNode)
  }
  if let rightNode = node.rightChild {
   nextLevel.append(rightNode)
  }
  }
  level = nextLevel
 }

 let ans = result.map { $0.map { $0.value }}
 print(ans)
 }

}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者使用swift能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • Swift算法之栈和队列的实现方法示例

    Swift算法之栈和队列的实现方法示例

    一.概述 栈和队列在数据结构中是比较重要的一个数据结构. 其实对于栈和队列并不需要太深入的介绍,栈和队列的核心内容是栈是先进后出.队列是先进先出.在实际开发中有些场景也可能会用到,比如 APP 中用户可以撤销操作,比如下棋 APP 中的悔棋操作,返回上一步就是先进后出(后进先出),也就是栈的特性. 比如在售票 APP 中,为先下订单的用户先出票,就需要用到队列.当然这两个只是在简单场景下的情况,实际开发中情况可能更复杂,比如售票 APP 为会员用户优先出票等. 接下来就通过 Swift 去实现栈

  • Swift学习笔记之元组（tuples）

    元组 元组(tuples)是由其它类型组合而成的类型.元组可能包含零或多个类型,比如 字符串.整数.字符.布尔以及其它元组.同时请注意,元组是值传递,而不是引用. 在Swift中创建元组的方式很简单,元组类型是用括号包围,由一个逗号分隔的零个或多个类型的列表.例如: let firstHighScore = ("Mary", 9001) 另外,在创建元组时你还可以给元组中的元素命名: let secondHighScore = (name: "James", sco

  • iOS中关于Swift UICollectionView横向分页的问题

    iOS中关于Swift UICollectionView横向分页的问题

    下面通过图文并茂的形式给大家介绍UICollectionView横向分页的问题,具体内容详情如下所示: 情况 直接看图 滚前 滚后 已经设置collectionView的isPagingEnabled为true了,可是出现了这种情况,原因就是collectionView的contentSize不够. <UICollectionView: 0x7fc565076000; frame = (0 0; 375 197); clipsToBounds = YES; gestureRecognizers

  • Swift中字典与JSON转换的方法

    Swift中经常会遇到字典和字符串的相互转换,因此可以转换可以封装起来,转换代码如下: func convertStringToDictionary(text: String) -> [String:AnyObject]? { if let data = text.data(using: String.Encoding.utf8) { do { return try JSONSerialization.jsonObject(with: data, options: [JSONSerializat

  • swift guard关键字详解及使用

    swift guard关键字详解及使用 Swift提供guard关键字,guard关键字可以简化繁琐的判断逻辑 func buy( money: Int , price: Int , capacity: Int , volume: Int){ if money >= price{ if capacity >= volume{ print("I can buy it!") print("\(money-price) Yuan left.") print(&

  • swift3.0指纹解锁的实现方法

    swift3.0指纹解锁的实现方法

    最近学习swift3.0, 不忙的时候开始用 Swift 重写现有的项目,有些地方的写法变得让人不知道怎么写了,今天就分享一下我在重写 指纹解锁工具类的时候遇到的一些问题吧. 先展示一下成果 class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() TouchIdManager.touchIdWithHand(fallBackTitle: "", succeed:

  • swift 隐式可选型实例详解

    1.隐式可选型的基本使用 var errorMessage: String? = nil errorMessage = "Not Found" "The message is " + errorMessage! 隐式可选型的定义 var errorMessage: String! = nil errorMessage = "Not Found" "The message is " + errorMessage 隐式可选型不需要

  • Swift算法之二叉树实现的方法示例

    Swift算法之二叉树实现的方法示例

    一.概述 二叉树的结构一般是以二叉链表的形式来存储的.二叉链表的结构类似于双向链表,二叉链表的节点也是有两个结点指针的,一个指向左子树,一个指向右子树.二叉树主要有四种遍历方式:先序遍历.中序遍历.后序遍历.层次遍历.关于二叉树的内容网上有很多,这里不再做过多的陈述. 本文将用Swift去实现二叉树的创建.四种遍历方式等.下面的实现部分内容参考了青玉伏案和唐巧两位大神相关的文章. 二.实现思路及代码 以下面二叉树为例: 先序遍历:先遍历根节点然后再遍历左子树,最后遍历右子树. 故上面先序遍历的顺

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

  • iOS swift实现转场动画的方法示例

    iOS swift实现转场动画的方法示例

    转场动画介绍 转场动画在我们日常开发中是经常遇到的,所谓转场动画,就是一个控制器的view切到另一个控制器的view上过程中过的动画效果.本例子是实现了在导航控制器的titleView边上慢慢弹出一个控制器.下面话不多说,来一起看看详细的介绍: 效果图: 专场前 专场后 示例代码 首先自定义一个animator类.在需要转场的控制器内,设置代理 //需要设置转场动画的控制器titleViewVc.transitioningDelegate = aniamator//这里的animator是ani

  • Python cookbook（数据结构与算法）实现优先级队列的方法示例

    本文实例讲述了Python实现优先级队列的方法.分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素: 解决方案:采用heapq模块实现一个简单的优先级队列 # example.py # # Example of a priority queue import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index =

  • Python cookbook（数据结构与算法）字典相关计算问题示例

    本文实例讲述了Python cookbook(数据结构与算法)字典相关计算问题.分享给大家供大家参考,具体如下: 问题:在字典上对数据执行各式各样的计算(比如求最小值.最大值.排序). 解决方案:利用zip()将字典的键-值对"反转"为值-键对序列. 例如:如下字典存放的股票名称和对应的价格: >>> prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.20, 'FB': 10.75 }

  • Swift算法实现字符串转数字的方法示例

    前言 最近学完Swift之后一直没有机会实战,发现由于Swift发展历史原因,目前网上大部分的算法都是使用C.Java或其他语言实现的,几乎没有使用Swift实现的,所以自己打算使用Swift去实现一些主流的算法,既是对自己Swift的回顾,也是对自己算法方面的提高. 首先是用Swift实现字符串转数字,当然,肯定是不能使用Swift自带的字符串转数字的api. 题目: 使用Swift实现一个方法,输入字符串,输出该字符串转换成的数字. 例如,输入字符串"125",输出数字125 实现

  • Swift算法实现逐字翻转字符串的方法示例

    前言 翻转字符串在字符串算法中算是比较常见的,而且被很多公司用作笔试题."逐字翻转字符串"是翻转字符串的翻版,也是之前Google的面试题,原题是这样的: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

随机推荐