用前序中序创建二叉树(用中序后序创建二叉树)

定义二叉树结点
用前序中序创建二叉树(用中序后序创建二叉树)
比如就拿这个二叉树
用前序中序创建二叉树(用中序后序创建二叉树)

前序中序创建

因为前序遍历的顺序是 根 , 左 ,右。
中序的遍历是 左 根 右。
我们会很不好想,但我们可以用前序和中序把上面那个二叉树的遍历一边

	前序遍历:ABDEHCFG
	中序遍历:DBEHAFCG

然后根据这我们来想
创建的时候,值都是以数组的形式传进来,所以找到根节点,前序和中序左子树个数一定相等,都是r。
前序和中序创建左子树的时候,挨个往后走就行,传的数组长度也就是个数就是r,左子树的个数,到右子树时。此时左子树创建完,所以前序要跳过r个元素,也就是创建左子树的个数,并加上根节点,也就是r+1.,创建右子树时个数就要减去根+左子树的个数。中序也是如此。

用前序中序创建二叉树(用中序后序创建二叉树)
程序一开始,要先找到r的大小,也就是中序遍历和前序遍历时根结点的位置。
用前序中序创建二叉树(用中序后序创建二叉树)

中序后序创建

与之前的道理是相似的,先找到根节点所在位置,也就是左子树个数
用前序中序创建二叉树(用中序后序创建二叉树)
然后找到根的值,也就是后序数组中的最后一个,然后道理相同,先左,再右
用前序中序创建二叉树(用中序后序创建二叉树)