數(shù)據(jù)結構-樹以及深度盅称、廣度優(yōu)先遍歷（遞歸和非遞歸歌焦，python實現(xiàn)）

前面我們介紹了隊列飞几、堆棧、鏈表独撇，你親自動手實踐了嗎屑墨？今天我們來到了樹的部分，樹在數(shù)據(jù)結構中是非常重要的一部分纷铣，樹的應用有很多很多卵史，樹的種類也有很多很多，今天我們就先來創(chuàng)建一個普通的樹搜立。其他各種各樣的樹將來我將會一一為大家介紹程腹，記得關注我的文章哦~

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

一棵樹

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

好蒜哀，關于樹的基本概念就介紹到這里了，話多千遍不如動手做一遍吏砂，接下來我們邊做邊學撵儿，我們來創(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ù)淀歇、設置節(jié)點數(shù)據(jù)、添加子節(jié)點匈织、獲取子節(jié)點浪默。

這里的樹類其實是一個節(jié)點類，很多個這樣的節(jié)點可以構成一棵樹缀匕，而我們就用根節(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)實例化好了乡小，我們先來對它分別采用遞歸和非遞歸的方式進行廣度優(yōu)先遍歷:

廣度優(yōu)先遍歷

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

在用非遞歸方式進行廣度優(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)先遍歷呢奴饮，我們需要用到前面介紹過的堆棧結構，所以我們現(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]