66. 有序数组构造二叉搜索树[array to binary search tree]

时间:2023-03-09 01:26:52
66. 有序数组构造二叉搜索树[array to binary search tree]

【本文链接】

http://www.cnblogs.com/hellogiser/p/array-to-binary-search-tree.html

题目

编写一个程序,把一个有序整数数组放到二叉搜索树中。

例如 4,6,8,10,12,14,16

转换为二叉搜索树为

10

/ \

6    14

/ \    /  \

4   8 12   16

【分析】

按照中序遍历的方法转换到二叉搜索树中。先要确定一个根节点,然后递归创建左右子树。

代码

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/5/31
*/
// binary tree node struct
struct BinaryTreeNode
{
    int value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

// array to tree recursively
BinaryTreeNode *arrayToTree(int array[], int start, int end)
{
    if (start > end)
        return NULL;
    ;
    BinaryTreeNode *root = new BinaryTreeNode();
    root->value = array[mid];
    root->left = arrayToTree(array, start, mid - );
    root->right = arrayToTree(array, mid + , end);
    return root;
}

// array to tree
BinaryTreeNode *ArrayToTree(int array[], unsigned int n)
{
    if (NULL == array || n<=0)
        return NULL;
    );
}

【参考】

http://blog.csdn.net/dahai_881222/article/details/7816127

【本文链接】

http://www.cnblogs.com/hellogiser/p/array-to-binary-search-tree.html