如果要把一个有序的整数数组放到二叉树中,那么所构造出来的二叉树必定也是一棵有序的二叉树。鉴于此,实现思路为:取数组的中间元素作为根结点,将数组分成左右两部分,对数组的两部分用递归的方法分别构建左右子树。如下图所示。
如上图所示,首先取数组的中间结点6作为二叉树的根结点,把数组分成左右两部分,然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建,例如,对于左半部分子数组,取中间结点3作为树的根结点,再把孩子数组分成左右两部分。依此类推,就可以完成二叉树的构建,实现代码如下:
package main
import(
"fmt"
."yfzxmn.com/isdamir/gotype" //引入定义的数据结构
)
func arrayToTree(arr[]int, start int, end int)*BNode{
varroot*BNode
if end>=start{
root=NewBNode()
mid:=(start+end+1)/2
//树的根结点为数组中间的元素
root.Data=arr[mid]
//递归的用左半部分数组构造root的左子树
root.LeftChild=arrayToTree(arr, start, mid-1)
//递归的用右半部分数组构造root的右子树
root.RightChild=arrayToTree(arr, mid+1, end)
}
return root
}
func main(){
data:=[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
fmt.Println("数组:", data)
root:=arrayToTree(data, O, len(data)-1)
fmt.Print("转换成树的中序遍历为:")
PrintTreeMidOrder(root)
fmt.Println()
}
程序的运行结果为
数组:1 2 3 4 5 6 7 8 9 10
转换成树的中序遍历为:1 2 3 4 5 6 7 8 9 10
算法性能分析: 由于这种方法只遍历了一次数组,因此,算法的时间复杂度为O(n),其中,N表示的是数组长度。