分治策略计算二叉树高度

测试二叉树输入序列：+-a##/b##+c##d##*e##f##
测试结果（高度）：5

1
#include <iostream> 
2
using namespace std; 
3
4
int maxh = 0; // 二叉树高度 
5
typedef struct BTNode{ 
6
    char data; 
7
    struct BTNode *lchild, *rchild; 
8
}BTNode, *BTree; // 二叉树节点，二叉树
9
10
void CreateTree(BTree &T) { // 创建二叉树
11
    char ch; 
12
    cin >> ch;
13
    if(ch == '#') T = NULL;
14
    else { 
15
        T = (BTree)malloc(sizeof(BTNode));
16
        T->data = ch; 
17
        CreateTree(T->lchild);
18
        CreateTree(T->rchild);
19
    } 
20
}
21
22
int BTDepth1(BTree T, int depth) { // 方法一 
23
    if(T) { 
24
        if(T->lchild)   BTDepth1(T->lchild, depth + 1); 
25
        if(T->rchild)   BTDepth1(T->rchild, depth + 1); 
26
    } 
27
    if(depth > maxh)     
28
        maxh = depth; 
29
    return depth; 
30
} 
31
32
int BTDepth2(BTree T) { // 方法二
33
    if(T == NULL) return 0; 
34
    else { 
35
        int m = BTDepth2(T->lchild); 
36
        int n = BTDepth2(T->rchild); 
37
        return (m > n) ? (m+1) : (n+1);  
38
    } 
39
} 
40
41
int main() { 
42
    BTree T = NULL; 
43
    CreateTree(T); 
44
    
45
    BTDepth1(T,1); 
46
    cout << "方法一求树高：H = " << maxh << endl; 
47
    cout << "方法二求树高：H = " << BTDepth2(T) << endl; 
48
    
49
    return 0; 
50
}