-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsortedArray_to_bt.c
More file actions
51 lines (46 loc) · 1.13 KB
/
sortedArray_to_bt.c
File metadata and controls
51 lines (46 loc) · 1.13 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
* =========================================================
* Filename: sortedArray_to_bt.c
* Description: 有序数组转化为平衡二叉树
*
* =========================================================
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int elem;
struct node* left;
struct node* right;
}Node;
Node* change(int a[],int s, int e);
Node* newNode(int e);
void inOrder(Node* root);
int main(){
int a[] = {0,1,2,3,4,5,6,7,8,9};
Node* t;
t = change(a, 0, 9);
inOrder(t);
return 0;
}
Node* change(int a[],int s, int e){// 数学归纳法 利用n = 1 来写代码形式;利用 n=k -> n=k+1来检验正确性
if(s > e)
return NULL;
int mid = (s + e)/2;
printf("mid is %d\n",a[mid]);
Node *root = newNode(a[mid]);
root->left = change(a, s, mid-1);
root->right = change(a, mid+1, e);
return root;
}
Node* newNode(int e){
Node* n = (Node*)malloc(sizeof(Node));
n->elem = e;
return n;
}
void inOrder(Node* root){
if(root){
inOrder(root->left);
printf(" %d ",root->elem);
inOrder(root->right);
}
}