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

首先，樹的形狀就是類似這個樣子的：

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

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

樹

          
            # 定義一個普通的樹類
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
          
        

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

這里的樹類其實是一個節(jié)點類，很多個這樣的節(jié)點可以構(gòu)成一棵樹，而我們就用根節(jié)點來代表這顆樹。

接下來我們實例化一棵樹：

          
            # 初始化一個樹
tree = Tree(0)
# 添加三個子節(jié)點
tree.addChild(Tree(1))
tree.addChild(Tree(2))
tree.addChild(Tree(3))
children = tree.getChildren()
# 每個子節(jié)點添加兩個子節(jié)點
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))
          
        

我們實例化好的樹大概是這個樣子的：

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

廣度優(yōu)先遍歷

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

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

          
            # 用以實現(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)
          
        

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

利用隊列我們只要在節(jié)點出隊的時候讓該節(jié)點的子節(jié)點入隊即可。

          
            # 廣度優(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]

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

          
            # 遞歸方式實現(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é)點的子節(jié)點再遍歷節(jié)點的兄弟節(jié)點。

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

          
            # 用以實現(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()
          
        

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

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

          
            # 深度優(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]

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

          
            # 遞歸方式實現(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]

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