前面我們介紹了隊(duì)列、堆棧、鏈表，你親自動(dòng)手實(shí)踐了嗎？今天我們來(lái)到了樹(shù)的部分，樹(shù)在數(shù)據(jù)結(jié)構(gòu)中是非常重要的一部分，樹(shù)的應(yīng)用有很多很多，樹(shù)的種類也有很多很多，今天我們就先來(lái)創(chuàng)建一個(gè)普通的樹(shù)。其他各種各樣的樹(shù)將來(lái)我將會(huì)一一為大家介紹，記得關(guān)注我的文章哦~

首先，樹(shù)的形狀就是類似這個(gè)樣子的：

它最頂上面的點(diǎn)叫做樹(shù)的根節(jié)點(diǎn)，一棵樹(shù)也只能有一個(gè)根節(jié)點(diǎn)，在節(jié)點(diǎn)下面可以有多個(gè)子節(jié)點(diǎn)，子節(jié)點(diǎn)的數(shù)量，我們這里不做要求，而沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)。

好，關(guān)于樹(shù)的基本概念就介紹到這里了，話多千遍不如動(dòng)手做一遍，接下來(lái)我們邊做邊學(xué)，我們來(lái)創(chuàng)建一棵樹(shù)：

樹(shù)

          
            # 定義一個(gè)普通的樹(shù)類
class Tree:
    def __init__(self, data):
        self.data = data
        self.children = []

    def get(self):
        return self.data
    
    def set(self):
        return self.data

    def addChild(self, child):
        self.children.append(child)

    def getChildren(self):
        return self.children
          
        

這就是我們定義好的樹(shù)類了，并給樹(shù)添加了三個(gè)方法，分別是獲取節(jié)點(diǎn)數(shù)據(jù)、設(shè)置節(jié)點(diǎn)數(shù)據(jù)、添加子節(jié)點(diǎn)、獲取子節(jié)點(diǎn)。

這里的樹(shù)類其實(shí)是一個(gè)節(jié)點(diǎn)類，很多個(gè)這樣的節(jié)點(diǎn)可以構(gòu)成一棵樹(shù)，而我們就用根節(jié)點(diǎn)來(lái)代表這顆樹(shù)。

接下來(lái)我們實(shí)例化一棵樹(shù)：

          
            # 初始化一個(gè)樹(shù)
tree = Tree(0)
# 添加三個(gè)子節(jié)點(diǎn)
tree.addChild(Tree(1))
tree.addChild(Tree(2))
tree.addChild(Tree(3))
children = tree.getChildren()
# 每個(gè)子節(jié)點(diǎn)添加兩個(gè)子節(jié)點(diǎn)
children[0].addChild(Tree(4))
children[0].addChild(Tree(5))
children[1].addChild(Tree(6))
children[1].addChild(Tree(7))
children[2].addChild(Tree(8))
children[2].addChild(Tree(9))
          
        

我們實(shí)例化好的樹(shù)大概是這個(gè)樣子的：

OK，我們的樹(shù)已經(jīng)實(shí)例化好了，我們先來(lái)對(duì)它分別采用遞歸和非遞歸的方式進(jìn)行廣度優(yōu)先遍歷:

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷，就是從上往下，一層一層從左到右對(duì)樹(shù)進(jìn)行遍歷。

在用非遞歸方式進(jìn)行廣度優(yōu)先遍歷的時(shí)候，我們需要用到前面介紹過(guò)的隊(duì)列類型，所以我們來(lái)定義一個(gè)隊(duì)列類：

          
            # 用以實(shí)現(xiàn)廣度優(yōu)先遍歷
class Queue():
    def __init__(self):
        self.__list = list()

    def isEmpty(self):
        return self.__list == []

    def push(self, data):
        self.__list.append(data)
    
    def pop(self):
        if self.isEmpty():
            return False
        return self.__list.pop(0)
          
        

用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先遍歷

利用隊(duì)列我們只要在節(jié)點(diǎn)出隊(duì)的時(shí)候讓該節(jié)點(diǎn)的子節(jié)點(diǎn)入隊(duì)即可。

          
            # 廣度優(yōu)先遍歷
def breadthFirst(tree):
    queue = Queue()
    queue.push(tree)
    result = []
    while not queue.isEmpty():
        node = queue.pop()
        result.append(node.data)
        for c in node.getChildren():
            queue.push(c)
    return result
          
        

調(diào)用一下：

          
            print(breadthFirst(tree))
          
        

輸出： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

遞歸實(shí)現(xiàn)廣度優(yōu)先遍歷

          
            # 遞歸方式實(shí)現(xiàn)廣度優(yōu)先遍歷
def breadthFirstByRecursion(gen, index=0, nextGen=[], result=[]):
    
    if type(gen) == Tree:
        gen = [gen]
    result.append(gen[index].data)
    
    children = gen[index].getChildren()
    
    nextGen += children
    if index == len(gen)-1:
        if nextGen == []:
            return
        else:
            gen = nextGen
            nextGen = []
            index = 0
    else:
        index += 1
    breadthFirstByRecursion(gen, index, nextGen,result)

    return result
          
        

調(diào)用一下：

          
            print(breadthFirstByRecursion(tree))
          
        

輸出： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

深度優(yōu)先遍歷

深度優(yōu)先遍歷，就是從上往下，從左到右，先遍歷節(jié)點(diǎn)的子節(jié)點(diǎn)再遍歷節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

采用非遞歸方式實(shí)現(xiàn)深度優(yōu)先遍歷呢，我們需要用到前面介紹過(guò)的堆棧結(jié)構(gòu)，所以我們現(xiàn)在定義一個(gè)堆棧類吧：

          
            # 用以實(shí)現(xiàn)深度優(yōu)先遍歷
class Stack():
    def __init__(self):
        self.__list = list()

    def isEmpty(self):
        return self.__list == []

    def push(self, data):
        self.__list.append(data)
    
    def pop(self):
        if self.isEmpty():
            return False
        return self.__list.pop()
          
        

利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷

實(shí)現(xiàn)深度優(yōu)先遍歷，我們只要在節(jié)點(diǎn)出棧的時(shí)候把該節(jié)點(diǎn)的子節(jié)點(diǎn)從左到右壓入堆棧即可。

          
            # 深度優(yōu)先遍歷
def depthFirst(tree):
    stack = Stack()
    stack.push(tree)
    result = []
    while not stack.isEmpty():
        node = stack.pop()
        result.append(node.data)
        children = node.getChildren()
        children = reversed(children)
        for c in children:
            stack.push(c)
    return result
          
        

調(diào)用一下：

          
            # 深度優(yōu)先遍歷
print(depthFirst(tree))
          
        

輸出： [0, 1, 4, 5, 2, 6, 7, 3, 8, 9]

遞歸實(shí)現(xiàn)深度優(yōu)先遍歷

          
            # 遞歸方式實(shí)現(xiàn)深度優(yōu)先遍歷
def depthFirstByRecursion(tree, result=[]):
    result.append(tree.data)
    children = tree.getChildren()
    for c in children:
        depthFirstByRecursion(c, result)
    return result
          
        

調(diào)用一下：

          
            print(depthFirstByRecursion(tree))
          
        

輸出： [0, 1, 4, 5, 2, 6, 7, 3, 8, 9]

好啦，今天我們的樹(shù)就介紹到這里了，對(duì)于廣度優(yōu)先遍歷的遞歸實(shí)現(xiàn)，你有更好的方法嗎？請(qǐng)留言告訴我吧。