给定一个有序整数数组,元素各不相同且按照升序排列,编写一个算法,创建一个高度最小的二叉查找树
给定一个有序整数数组,元素各不相同且按照升序排列,编写一个算法,创建一个高度最小的二叉查找树
一贱书生 发表于1年前
给定一个有序整数数组,元素各不相同且按照升序排列,编写一个算法,创建一个高度最小的二叉查找树
  • 发表于 1年前
  • 阅读 16
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

      二叉查找树是,对于任意一个结点,左边的结点均小于它,右边的结点均大于它

要创建一个高度最小的树,就必须让左右子结点的数量越接近越好,也就是说,要让中间值成为根节点,这样,左边的一半是左子树,右边的一半是右子树

然后,继续以类似的方式构造整棵树,数据每一段的中间值成为根元素,左边一半成为左子树,右边一半成为右子树

用递归方式运用createMinimumBST()

 

[java] view plain copy

 

  1. import BTreeBalanced.TreeNode;  
  2.   
  3.   
  4. public class minimumBST {  
  5.     TreeNode createMinumumBST(int arr[], int start, int end) {  
  6.         if (end < start) {  
  7.             return null;  
  8.         }  
  9.           
  10.         int mid = (start + end) / 2;  
  11.         TreeNode n = new TreeNode (arr[mid]);  
  12.         n.left = createMinimumBST(arr, start, mid - 1);  
  13.         n.right = createMinumumBST(arr, mid + 1, end);  
  14.         return n;  
  15.     }  
  16.       
  17.     TreeNode createMinimumBST(int arr[]) {  
  18.         return createMinimumBST(array, 0, array.length - 1);  
  19.     }  
  20. }
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 17
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: