CCI_Q4.3

本文参考该作者文章当作编程笔记：

作者：Hawstein
出处：http://hawstein.com/posts/ctci-solutions-contents.html

给定一个有序数组(递增)，写程序构建一棵具有最小高度的二叉树。

思路：

取数组中间元素当作二叉树的根，递归插入。

CODE：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<limits.h>
 4 #define N 6
 5 #define key(A) (A)
 6 #define less(A,B) (A<B)
 7 typedef struct node
 8 {
 9     char item;
10     struct node *l,*r;
11 }node;
12 void insertNode(node **h,char *s,int start,int end)
13 {
14     int mid=(start+end)/2;
15     if(start>end)
16         return;
17     (*h)=(node *)malloc(sizeof(node));
18     (*h)->item=s[mid];
19     (*h)->l=NULL;
20     (*h)->r=NULL;
21     insertNode(&((*h)->l),s,start,mid-1);
22     insertNode(&((*h)->r),s,mid+1,end);
23 }
24 void printfNode(char item,int blank)
25 {
26     int i;
27     for(i=0;i<blank;++i)
28         printf(" ");
29     printf("%c
",item);
30 }
31 void traversePre(node *h,int blank)
32 {
33     if(h==NULL)
34     {printfNode('*',blank); return;}
35     printfNode(h->item,blank);
36     traversePre(h->l,blank+1);
37     traversePre(h->r,blank+1);
38 }
39 int max=INT_MIN,min=INT_MAX,hight=-1;
40 /*根节点为第0层，当到达叶子节点时，判断是否为最大、最小高度*/
41 void traversePreMaxMin(node *h)
42 {
43     if(h==NULL)
44         return;
45     ++hight;
46     traversePreMaxMin(h->l);
47     traversePreMaxMin(h->r);
48     if(h->l==NULL && h->r==NULL)
49     {
50         if(max<hight)
51             max=hight;
52         if(min>hight)
53             min=hight;
54     }
55     --hight;
56 }
57 int main()
58 {
59     node *head=NULL;
60     char s[]="ABCDEF";
61     int i;
62     insertNode(&head,s,0,N-1);    /*取有序数组中间的元素，当作根，递归插入*/
63     traversePre(head,0);    /*前序遍历树*/
64     printf("%d	%d
",max,min);    /*max和min初始值*/
65     traversePreMaxMin(head);    /*找出树的最大、最小高度*/
66     printf("%d	%d
",max,min);    /*输出最大、最小高度*/
67     return 0;
68 }

View Code

错误：第39行，单词错误。。，应为height。高度（height）：树中节点层数中的最大值，根节点在第0层。