数据结构中你需要知道的关于树的一切

a_node.insert_left('b')

a_node.insert_right('c')

b_node = a_node.left_child

b_node.insert_right('d')

c_node = a_node.right_child

c_node.insert_left('e')

c_node.insert_right('f')

d_node = b_node.right_child

e_node = c_node.left_child

f_node = c_node.right_child

print(a_node.value) # a

print(b_node.value) # b

print(c_node.value) # c

print(d_node.value) # d

print(e_node.value) # e

print(f_node.value) # f

如今，我们来思虑一下树的遍历。

遍历树有两种选择：深度优先搜刮(DFS)和广度优先搜刮(BFS)。

DFS是用来遍历或搜刮树数据构造的算法。大年夜根节点开端，在回溯之前沿着每一个分支尽可能远的摸索。
BFS是用来遍历或搜刮树数据构造的算法。大年夜根节点开端，在摸索下一层邻居节点前，起首摸索同一层的邻居节点。

DFS 在回溯和搜刮其他路径之前找到一条到叶节点的路径。让我们看看这种类型的遍历的示例。

此算法的结不雅是 1–2–3–4–5–6–7 。

为什么呢?

让我们分化下。

大年夜根节点(1)开端。输出之。
进入左孩子(2)。输出之。
然落后入左孩子(3)。输出之。(此节点无子孩子)
回溯，并进入右孩子(4)。输出之。(此节点无子孩子)
回溯到根节点，然落后入其右孩子(5)。输出之。
进入左孩子(6)。输出之。(此节点无子孩子)
回溯，并进入右孩子(7)。输出之。(此节点无子孩子)
完成。

当我们深刻到叶节点时回溯，这就被称为 DFS 算法。

既然我们对这种遍历算法已经熟悉了，我们将评论辩论下 DFS 的类型：前序、中序和后序。

前序遍历

这和我们在上述示例中的作法根本类似。

输出节点的值。
进入其左孩子并输出之。当且仅当它拥有左孩子。
进入右孩子并输出之。当且仅当它拥有右孩子。

def pre_order(self): 
    print(self.value) 
 
    if self.left_child: 
        self.left_child.pre_order() 
 
    if self.right_child: 
        self.right_child.pre_order()

中序遍历

数据构造中你须要知道的关于树的一切

左孩子优先，之后是中心，最后是右孩子。

如今让我们编码实现之。

def in_order(self): 
    if self.left_child: 
        self.left_child.in_order() 
 
    print(self.value) 
 
    if self.right_child: 
        self.right_child.in_order()

进入左孩子并输出之。当且仅当它有左孩子。
输出节点的值。
进入右孩子并输出之。当且仅当它有右孩子。

数据构造中你须要知道的关于树的一切

以此树为例的后序算法的结不雅为 3–4–2–6–7–5–1 。

左孩子优先，之后是右孩子，中心的最后。

让我们编码实现吧。

def post_order(self): 	
			 3/4   首页 上一页 1 2 3 4 下一页 尾页	
			

　　推荐阅读
　　简单几条命令，轻松开启MacOS系统隐藏功能
            Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践
            Mac 中有一个搁笔是「黑色的窗口」名为「终端  Terminal」的应用，对于一个通俗人用户来说，它就似乎有一>>>详细阅读


本文标题：数据结构中你需要知道的关于树的一切
地址：http://www.17bianji.com/lsqh/38849.html
 1/2    1