前面我們介紹了隊(duì)列、堆棧胚委、鏈表挟鸠，你親自動手實(shí)踐了嗎？今天我們來到了樹的部分亩冬，樹在數(shù)據(jù)結(jié)構(gòu)中是非常重要的一部分艘希，樹的應(yīng)用有很多很多硼身，樹的種類也有很多很多，今天我們就先來創(chuàng)建一個普通的樹覆享。其他各種各樣的樹將來我將會一一為大家介紹佳遂，記得關(guān)注我的文章哦~
首先，樹的形狀就是類似這個樣子的：
它最頂上面的點(diǎn)叫做樹的根節(jié)點(diǎn)撒顿，一棵樹也只能有一個根節(jié)點(diǎn)丑罪，在節(jié)點(diǎn)下面可以有多個子節(jié)點(diǎn)，子節(jié)點(diǎn)的數(shù)量凤壁，我們這里不做要求吩屹，而沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)。
好拧抖，關(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é)點(diǎn)數(shù)據(jù)淌哟、設(shè)置節(jié)點(diǎn)數(shù)據(jù)厌衙、添加子節(jié)點(diǎn)、獲取子節(jié)點(diǎn)绞绒。
這里的樹類其實(shí)是一個節(jié)點(diǎn)類，很多個這樣的節(jié)點(diǎn)可以構(gòu)成一棵樹榕暇，而我們就用根節(jié)點(diǎn)來代表這顆樹蓬衡。
接下來我們實(shí)例化一棵樹：
# 初始化一個樹
tree = Tree(0)
# 添加三個子節(jié)點(diǎn)
tree.addChild(Tree(1))
tree.addChild(Tree(2))
tree.addChild(Tree(3))
children = tree.getChildren()
# 每個子節(jié)點(diǎn)添加兩個子節(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í)例化好的樹大概是這個樣子的：
OK，我們的樹已經(jīng)實(shí)例化好了彤枢，我們先來對它分別采用遞歸和非遞歸的方式進(jìn)行廣度優(yōu)先遍歷:
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷狰晚，就是從上往下，一層一層從左到右對樹進(jìn)行遍歷缴啡。
在用非遞歸方式進(jìn)行廣度優(yōu)先遍歷的時(shí)候壁晒，我們需要用到前面介紹過的隊(duì)列類型，所以我們來定義一個隊(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)先遍歷呢，我們需要用到前面介紹過的堆棧結(jié)構(gòu)帮孔，所以我們現(xiàn)在定義一個堆棧類吧：
# 用以實(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]
好啦，今天我們的樹就介紹到這里了晤斩，對于廣度優(yōu)先遍歷的遞歸實(shí)現(xiàn)焕檬，你有更好的方法嗎？請留言告訴我吧澳泵。
