树-1-有序数组放入到二叉树中

将一个有序数组的元素放入到二叉树中

• 题目

  ​ 将一个有序数组的元素放入到二叉树中，形成的二叉树为二叉搜索树。

• 实现思路:

  ​ 1.获取数组的中间元素位置，构建根节点。

  ​ 2.在将数组开始到中间元素前一个位置构造为节点的左子树。中间元素后一个到数组末尾元素构造为节点的右子树。

  ​ 3.如果数组的开始位置等于结束位置，则返回。

  ​ 4.递归调用进行构造。

• 图示说明

  ​

• 实现代码

  package main
  
  import "fmt"
  
  // 定义一个节点的结构体
  type TreeNode struct {
    // 值域
    Value interface{}
    // 左子节点
    LiftNode *TreeNode
    // 右子节点
    RightNode *TreeNode
  }
  
  // 构造函数，返回指针类型的一个节点
  func Constructor() *TreeNode {
  	c := new(TreeNode)
  	return c
  }
  
  // 将数组转化为树的函数
  func ArrayConvertTree(arr []int, start, end int) *TreeNode {
  	// 定义一个跟节点
  	var root *TreeNode
  	// 只要结束节点大于等于开始节点
  	if end >= start {
  		// 构造一个根节点
  		root = Constructor()
  		// 取出中间位置
  		mid := (start+end+1)/2
  		// 如果开始等于结束,该节点的左右节点都为nil
  		root.Value = arr[mid]
  		// 该节点的左子节点
  		root.LiftNode = ArrayConvertTree(arr, start, mid-1)
  		// 该节点的右子节点
  		root.RightNode = ArrayConvertTree(arr, mid+1, end)
  	}
  	return root
  }
  
  // 树中序的遍历
  func TreeMid(t *TreeNode) {
  	// 如果节点为空
  	if t == nil {
  		return
  	}
  	TreeMid(t.LiftNode)
  	fmt.Println(t.Value)
  	TreeMid(t.RightNode)
  }
  
  
  func main() {
  	arr := []int{1,2,3,4,5,6,7,8,9}
  	fmt.Println(arr)
  	r := ArrayConvertTree(arr,0, len(arr)-1)
  	//fmt.Printf("%#v", r.Value, r.LiftNode.Value, r.RightNode.Value)
  	TreeMid(r)
  }
  输出如下:
  输入的数组：
  [1 2 3 4 5 6 7 8 9]
  中序遍历的输出
  1
  2
  3
  4
  5
  6
  7
  8
  9
  一致