前序遍历:若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树
中序遍历:若树为空,则空操作返回,否则从根结点开始(不是先访问根结点),中序遍历根结点的左子树,然后访问根节点,最后中序遍历右子树。
后序遍历:若树为空,则空操作返回,否则从左到右先访问叶子结点后结点的方式遍历左右子树,最后访问根节点。
层序遍历:若树为空,则空操作返回,否则从树的每一层,即从根节点开始访问,从上到下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。
假设已知后序遍历和中序遍历结果,从后序遍历的结果可以等到最后一个访问的结点是根节点,对于最简单的二叉树,此时在中序遍历中找到根节点之后,可以分辨出左右子树,这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树,重建得到根结点和暂时混乱的左右结点,通过递归将左右结点依次重建为子二叉树,即可完成整个二叉树的重建。(在得到根结点之后,需要在中序遍历序列中寻找根结点的位置,并将中序序列拆分为左右部分,所以要求序列中不能有相同的数字,这是序列重建为二叉树的前提。)
Root =None
strs="abc##d##e##" #前序遍历扩展的二叉树序列
vals =list(strs)
Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
print(Roots)
inorderSearch = inOrderTraverse2(Roots)
print(inorderSearch)
先序遍历简单说就是碰到啥就输出啥,不过二叉树有根节点,左右子节点的结构关系,所以先序遍历更准确的说,是先遍历根节点,然后左节点,右节点,在遍历左节点的时候,也是先遍历左节点的跟节点,然后左节点的左节点,左节点的右节点,依此类推。。。详细的信息可以看看计算机中的数据结构