python3实现二叉树遍历及递归算法分析1.二叉树的三种遍历方式 二叉树共有三种遍历方式：前序遍历，中序遍历，和后续遍历即：先中后指访问根节点的顺序eg：先序rootleftmiddleorderleftrootrightpostorderleftleftroot 遍历的总体思路：将树分为1.1前序遍历 a先访问根节点 b访问左节点 c访问右节点 a（b(d(h))(e(i)))(c(f)(g))--abdheicfg1.2中序遍历 a先访问左节点 b访问根节点 c访问右节点 (((h)d)b((i)e))a((f)c(g))--hdbieafcg1.3后序遍历 a先访问左节点 b访问右节点 cvi坐根节点 ((hd)(ie)b)(fgc)a--hdiebfgca2,python3implementtreestructure#一个实现树结构的类，树的节点有三个私有属性，左指针和右指针的值本身classNode():def__init__(self,data=None):self._data=dataself._left=Noneself._right=Nonedefset_data(self,data):self._data=datadefget_data(self):返回self._datadefset_left(self,node):self._left=nodedefget_left(self):returnself._leftdefset_right(self,node):self._right=nodedefget_right(self):returnself._rightif__name__=='__main__':#实例化根节点root_node=Node('a')#root_node.set_data('a')#实例化左子节点left_node=Node('b')#实例化右子节点right_node=node('c')#给根节点的左指针赋值，使其指向左子节点root_node.set_left(left_node)#给根节点的右指针赋值，使其指向左子节点到右子节点root_node.set_right(right_node)print(root_node.get_data(),root_node.get_left().get_data(),root_node.get_right().get_data())3.实现树的递归遍历（前中后三层遍历）下面的例子是树的遍历算法，其中对树类进行了优化，#一个实现树结构的类。树的节点有三个私有属性左指针右指针自己的值classNode():def__init__(self,data=None,left=None,right=None):self._data=dataself._left=leftself._right=right#顺序遍历遍历过程根左右defpro_order(tree):iftree==None:returnFalseprint(tree._data)pro_order(tree._left)pro_order(tree._right)#后序遍历defpos_order(tree):iftree==None:returnFalse#print(tree.get_data())pos_order(tree._left)pos_order(tree._right)print(tree._data)#中序遍历defmid_order(tree):iftree==None:returnFalse#print(tree.get_data())mid_order(tree._left)print(tree._data)mid_order(tree._right)#层级遍历defrow_order(tree):#print(tree._data)queue=[]queue.append(tree)while真：ifqueue==[]:breakprint(queue[0]._data)first_tree=queue[0]iffirst_tree._left!=None:queue.append(first_tree._left)iffirst_tree._right!=None:queue.append(first_tree._right)queue.remove(first_tree)if__name__=='__main__':tree=Node('A',Node('B',Node('D'),Node('E')),节点('C',Node('F'),Node('G')))pro_order(tree)mid_order(tree)pos_order(tree)4.递归算法以上两张图转自知乎；图1中途返回后，直接返回上层的返回。这个想法并不全面。比较合理的返回应该如图2所示，子函数返回的时候，应该返回到调用子函数的那个??节点，这样在剩下的代码执行完之后，再返回到上层，如果它根据图1返回，二叉树的遍历无法按照上面的例子实现。#递归求N!defrecursive_mix(n):ifn==2:return1returnn*recursive_mix(n-1)#decimaltobinarydefrecursive_conversion(n):ifn==0:returnrecursive_conversion(int(n/2))print(n%2)#returnn%2#数字闪回的递归实现defrecursive_back(n):ifn==0:returnprint(n%10)recursive_back(int(n/10))recursive_conversion(23)recursive_mix(5)recursive_back(1234)请继续关注我的公众号请让你的梦想慢慢成长，谢谢
