首页 > 代码库 > 有序数组放到二叉树 【微软面试100题 第八十六题】

有序数组放到二叉树 【微软面试100题 第八十六题】

题目要求

  怎样编写一个程序,把一个有序整数数组放到二叉树中?

题目分析

  二叉搜索树:左<中<右。

  因此通过递归,把数组分成两半,左边一半作为左子树然后继续递归,右边一半作为右子树然后继续递归。

代码实现

#include <iostream>#include <queue>using namespace std;typedef struct BinaryTree{    struct BinaryTree *left,*right;    int data;}BinaryTree;BinaryTree *ArrayToTree(int *a,int n);void PrintTree(BinaryTree *root);int main(void){    int a[] = {2,3,5,6,8,10};    BinaryTree *tree = ArrayToTree(a,6);    PrintTree(tree);    return 0;}void PrintTree(BinaryTree *root){    if(root==NULL)        return ;    queue<BinaryTree *> queueTemp;    queueTemp.push(root);    queueTemp.push(0);    while(!queueTemp.empty())    {        BinaryTree *tmp = queueTemp.front();        queueTemp.pop();        if(tmp)        {            cout << tmp->data << " ";            if(tmp->left)                queueTemp.push(tmp->left);            if(tmp->right)                queueTemp.push(tmp->right);        }        else if(!queueTemp.empty())        {            queueTemp.push(0);            cout << endl;        }    }}BinaryTree *ArrayToTreeCore(int *a,int start,int end){    if(start>end)        return NULL;    int mid = start + (end-start)/2;    BinaryTree *root = new BinaryTree;    root->data =http://www.mamicode.com/ a[mid];    root->left = ArrayToTreeCore(a,start,mid-1);    root->right = ArrayToTreeCore(a,mid+1,end);    return root;}BinaryTree *ArrayToTree(int *a,int n){    if(a==NULL || n<=0)        return NULL;    return ArrayToTreeCore(a,0,n-1);}

 

有序数组放到二叉树 【微软面试100题 第八十六题】