如果知道某二叉树的前相遍历和中相遍历的结果,请重新配置该二叉树。 (步骤详情,代码后补) ) ) ) ) ) ) ) ) )。
前序扫描序列{1、2、4、7、3、5、6、8}
中序扫描序列{4、7、2、1、5、3、8、6}http://www.Sina.com/
首先,需要知道前后的遍历方法。
前序扫描:step1左右
中序扫描:左根右
后遍历:左右根
请注意根节点的位置
言归正传,前序中序是先看前序,第一个元素“1”是根节点,然后中序遍历中“1”位于根
中顺扫描中确认的根节点的位置是左右分别左侧的子树和右侧的子树step2
现在回过头来看前面的遍历,第二个元素是“2”,后面的遍历序列在“1”左边的树中得到“2”,因此二叉树的一部分可以绘制如下。
step3
注:前序遍历从左往右依此看元素,若是后序遍历则最后一个元素是根节点,并且从右往左看
1 .继续前面的遍历,第三个元素是“4”,而在后面的遍历中,4在2的左边,二叉树的一部分可以绘制如下:
2 .继续向前遍历,第四个元素是“7”,而在向后遍历中,7位于4的右侧,二叉树的一部分可以绘制如下:
3 .继续向前遍历,第五个元素是“3”,而在向后遍历中,3位于1的右侧,二叉树的一部分可以绘制如下:
4 .继续向前遍历,第六个元素是“5”,而在向后遍历中,5位于3的左边,二叉树的一部分如下:step4
可以按照上述步骤重建此二叉树。 可见这其实是递归的表达。 后续代码部分将继续更新和添加。 还没有手续。