python实现②叉树和它的七种遍历

树是数据结构中非常重要的一种主要的用途是用来提高查找效率，对于要重复查找的情况效果更佳如二叉排序树、FP-树。另外可以用来提高编码效率如哈弗曼树。

• 递归实现前序遍历、中序遍历、后序遍历
• 栈实现前序遍历、中序遍历、后序遍历

 """利用递归实现树的先序遍历"""
 """利用递归实现树的中序遍历"""
 """利用递归实现树的后序遍历"""
 """利用堆栈实现树的先序遍历"""
 """利用堆栈实现树的中序遍历"""
 """利用堆栈实现树的后序遍历"""
 """利用队列实现树的层次遍历"""
 

 

 树的遍历主要有两种一种是深度优先遍历，像前序、中序、后序；另一種是邻接矩阵广度优先遍历历像层次遍历。在树结构中两者的区别还不是非常明显但从树扩展到有向图，到无向图的时候深度优先搜索和广度优先搜索的效率和作用还是有很大不同的。
深度优先一般用递归广度优先一般用队列。一般情况下能用递归实现的算法大部汾也能用堆栈来实现
我印象中是有递归构造树的方法，却一直想不出该怎么构造后来仔细想了一下，递归思想有点类似深度优先算法而树的构造应该是广度优先的。如果用递归的话一定要有个终止条件例如规定树深等。不然构造出来的树会偏向左单子树或者右单子樹所以一般树的构造还是应该用队列比较好。