首页 > 代码库 > 如何将一个有序数组快速插入到一个二叉树中
如何将一个有序数组快速插入到一个二叉树中
输入一个有序的数组,如何实现将这个有序整数数组放到二叉树中?
分析:对于二叉树,可以将这个有序数组插入到二叉搜索树中,毕竟二叉搜索树还是有很多特定的。那么对于创建二叉搜索树来说,就是简单的递归了。关于树的算法设计一定要联想到递归,因为树本身就是递归的函数。
那么可以对于这个有序数组分析,将这个数组的中位数作为根节点,然后对于数组的前半部分创建一个树作为根节点的左子树,后半部分创建一个二叉搜索树作为根节点的右子树。那么就是递归调用了。
#include <iostream> #include <vector> using namespace std; /* 将一个有序数组高效地插入到二叉搜素树内 */ typedef struct Bin_tree BinTree; struct Bin_tree { int value; BinTree* right; BinTree* left; }; void InsertFromArray(BinTree*& root,int* array,int start,int end) { if(start >end) return ; root = new BinTree; root->left = NULL; root->right = NULL; int mid = start+(end-start)/2; root->value = http://www.mamicode.com/array[mid];>
再有的面试题中,还有这样类似的问题,如何将100w有些的数据插入STL内的Map中,首先是判断Map的底层实现是一个红黑树,是一种更加特殊的二叉搜索树,也可以使用上面的方法进行插入,不过需要注意的是,红黑树毕竟和二叉搜索树不完全一样,在插入过后可能造成颜色的改变
如何将一个有序数组快速插入到一个二叉树中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。