Swift-二叉樹遍歷

二叉樹常見的四種遍歷方式枢赔，先序遍歷桅咆，中序遍歷括授，后序遍歷以及層次遍歷，先來看一張二叉樹的圖:

FlyElephant.jpg

遍歷之前我們可以先自己實(shí)現(xiàn)樹岩饼，不過為了效率荚虚，可以通過函數(shù)自己創(chuàng)建樹~

二叉樹創(chuàng)建

方式一：

var d = TreeNode(data: "d",leftChild: nil,rightChild: nil)

var b = TreeNode(data: "b",leftChild: nil,rightChild: d)

var e = TreeNode(data: "e",leftChild: nil,rightChild: nil)

var c = TreeNode(data: "c", leftChild: nil, rightChild: e)

var a = TreeNode(data: "a",leftChild: b,rightChild: c)

print("FlyElephant")
print("先序遍歷:")
preOrder(a)
print("\n中序遍歷:")
inOrder(a)
print("\n后序遍歷:")
postOrder(a)
print()

FlyElephant.png

方式二，輸入一個(gè)先序的二叉樹序列籍茧，空節(jié)點(diǎn)設(shè)置為#版述，以上圖為例:

let rootList="ABD##E##CF###"
var rootIndex = -1

func createTree(inout root:TreeNode?) -> Void {
    
    rootIndex=rootIndex+1
    
    if rootIndex>=rootList.characters.count {
        return
    }
    
    let data=rootList[rootIndex] as String
    if data != "#" {
        root = TreeNode()
        root?.data = data
        
        createTree(&root!.leftChild)
        createTree(&root!.rightChild)
    } else {
        root = nil
    }
}

二叉樹的定義:

class TreeNode: NSObject {
    var data:NSString?
    var leftChild:TreeNode?
    var rightChild:TreeNode?
    
    override init() {}
    
    init(data:NSString,leftChild:TreeNode?,rightChild:TreeNode?) {
        self.data = data
        self.leftChild = leftChild
        self.rightChild = rightChild
    }
}

先序遍歷

遍歷的順序:根節(jié)點(diǎn)->左節(jié)點(diǎn)->右節(jié)點(diǎn)

func preOrder(rootNode:TreeNode?) -> Void {
    if rootNode != nil {
        if let data = rootNode?.data {
            print("\(data)\t", terminator: "")
            preOrder(rootNode?.leftChild)
            preOrder(rootNode?.rightChild)
        }
    }
}

中序遍歷

遍歷的順序:左節(jié)點(diǎn)->根節(jié)點(diǎn)->右節(jié)點(diǎn)

func inOrder(rootNode:TreeNode?) -> Void {
    if rootNode != nil {
        if let data = rootNode?.data {
            inOrder(rootNode?.leftChild)
            print("\(data)\t", terminator: "")
            inOrder(rootNode?.rightChild)
        }
    }
}

后序遍歷

遍歷的順序:左節(jié)點(diǎn)->右節(jié)點(diǎn)->根節(jié)點(diǎn)

func postOrder(rootNode:TreeNode?) -> Void {
    if rootNode != nil {
        if let data = rootNode?.data {
            postOrder(rootNode?.leftChild)
            postOrder(rootNode?.rightChild)
            print("\(data)\t", terminator: "")
        }
    }
}

層次遍歷

遍歷的方式從上到下，從左到右:

func levelOrder(rootNode:TreeNode?) -> Void {
    var arr:[AnyObject]=[];
    arr.append(rootNode!);
    
    while arr.count>0 {
        let firstNode=arr[0] as! TreeNode
        
        if let data=firstNode.data {
            print("\(data)\t", terminator: "")
            arr.removeFirst()
        }
        
        if (firstNode.leftChild != nil) {
            arr.append(firstNode.leftChild!)
        }
        
        if (firstNode.rightChild != nil) {
            arr.append(firstNode.rightChild!)
        }
    }
}

測(cè)試

let rootList="ABD##E##CF###"
var rootIndex = -1

func createTree(inout root:TreeNode?) -> Void {
    
    rootIndex=rootIndex+1
    
    if rootIndex>=rootList.characters.count {
        return
    }
    
    let data=rootList[rootIndex] as String
    if data != "#" {
        root = TreeNode()
        root?.data = data
        
        createTree(&root!.leftChild)
        createTree(&root!.rightChild)
    } else {
        root = nil
    }
}

var rootNode:TreeNode?
createTree(&rootNode)
print("先序遍歷:")
preOrder(rootNode)
print("\n中序遍歷:")
inOrder(rootNode)
print("\n后序遍歷:")
postOrder(rootNode)
print("\n層次遍歷:")
levelOrder(rootNode)

測(cè)試結(jié)果如圖所示: