二叉搜索树是一类特殊的树，它或者是一棵空树，或者满足若左子树不为空，则其左子树所有节点的值都小于其根节点的值，若右子树不为空，则其右子树所有节点的值都小于其根节点的值。
现有一个有序的整数数列，生成一棵合理的二叉搜索树。
生成一棵二叉搜索树，首先，创建节点类。
<pre>
class TreeNode {
int value;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode(int value, TreeNode parent, TreeNode left, TreeNode right) {
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
}
</pre>
之后将数列中每一个值按照规则分别插到树中。待插入节点的值若比当前比较的节点的值小且当前节点的左子树不为空，则将待插入节点与其左边的节点比较，若比当前比较的节点的值大且当前节点的右子树不为空，则将待插入节点与其右边的节点比较；直到节点左或右子树为空时将待插入节点插入。
<pre>
//root为根节点，newNode为待插入节点
public TreeNode insert(TreeNode root, TreeNode newNode) {
if(root == null) {
root = newNode;
}else if(newNode.value < root.value) {
root.left = insert(root.left, newNode);
}else if(newNode.value > root.value) {
root.right = insert(root.right, newNode);
}
return root;
}
</pre>
生成了一棵二叉搜索树，可以将其打印出来。
<pre>
/前序遍历/
public void preOrder(TreeNode node) {
if(node != null) {
System.out.print(node.value + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/中序遍历/
public void inOrder(TreeNode node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.value + " ");
inOrder(node.right);
}
}
/后序遍历/
public void postOrder(TreeNode node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value + " ");
}
}
</pre>
但是还有一个条件未满足，如何生成一棵合理的二叉搜索树？
我的思路是已知是一个有序的整数数列，则将数列中间的数作为根节点，接下来数列左右两边再分别取中间值插入，直到插入所有值。
所以将数值插入树之前，对数列进行重新排序，生成新的数列。
<pre>
/动态数组用于方便存储新数列/
ArrayList<Integer> tmp = new ArrayList<Integer>();
</pre>
处理数列代码
<pre>
public void handle(int[] value) {
if(value == null) {
return;
}
//获取中间值并放入新数列中
int goal = returnCenterValue(value);
tmp.add(value[goal]);
if(value.length == 1) {//若长度为1，已是最后一个值
return;
}else if(value.length == 2) {//若长度为2，将最后一个值也放入新数列
tmp.add(value[0]);
}else {
//数列左右两边再分别取中间值插入
handle(Arrays.copyOfRange(value, 0, goal));
handle(Arrays.copyOfRange(value, goal+1, value.length));
}
}
/寻找数列中间值位置，若为偶数取较大值/
public int returnCenterValue(int[] value) {
if(value.length == 1) {
return 0;
}else if(value.length == 2) {
return 1;
}else {
int tmp = value.length;
return (tmp/2);
}
}
</pre>
以上是个人思路，以后有更好的解决方法我会及时更新。
未经同意，不得转载。
