二叉樹的基本操作

由於崗位實踐需要，故寫了一個樹的基本操作，包括先，中，後序遞歸和非遞歸，計算高度，計算左子樹個數，無其他用處，警示自己而已 ..
[cpp] 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <stack> 
using namespace std; 
 
// tree node 
typedef struct TreeNode { 
    char data; 
    struct TreeNode* lChild; 
    struct TreeNode* rChild; 
} Node; 
 
int n; 
stack<Node*> s; 
 
// 先序 create tree 
void createTree(Node **t, char *c) 
{ 
    n++; 
    if(n > strlen(c) - 1) return; 
    if(c[n] == '0') *t = NULL; 
    else  
    { 
        (*t) = (Node*)malloc(sizeof(Node)); 
        (*t)->data = c[n]; 
        createTree(&(*t)->lChild, c); 
        createTree(&(*t)->rChild, c); 
    } 
} 
// 先序遞歸訪問 
void preVisit(Node *t) 
{ 
    if(t) 
    { 
        printf("%c", t->data); 
        preVisit(t->lChild); 
        preVisit(t->rChild); 
    } 
} 
// 中序遞歸訪問 
void midVisit(Node *t) 
{ 
    if(t) 
    { 
        midVisit(t->lChild); 
        printf("%c", t->data); 
        midVisit(t->rChild); 
    } 
} 
// 後序遞歸訪問 
void lastVisit(Node *t) 
{ 
    if(t) 
    { 
        lastVisit(t->lChild); 
        lastVisit(t->rChild); 
        printf("%c", t->data); 
    } 
} 
 
 
// 先序非遞歸訪問 
void uPre(Node* head) 
{ 
    while(!s.empty()) s.pop(); 
    while(head || !s.empty()) 
    { 
        while(head) 
        { 
            printf("%c", head->data); 
            s.push(head); 
            head = head->lChild; 
        } 
        if(!s.empty()) 
        { 
            head = s.top(); 
            s.pop(); 
            head = head->rChild; 
        } 
    } 
} 
 
// 中序非遞歸訪問 
void uMid(Node* head) 
{ 
    while(!s.empty()) s.pop(); 
    while(head || !s.empty()) 
    { 
        while(head) 
        { 
            s.push(head); 
            head = head->lChild; 
        } 
        if(!s.empty()) 
        {    
            head = s.top(); 
            printf("%c", head->data); 
            s.pop(); 
            head = head->rChild; 
        } 
    } 
 
} 
// 後序非遞歸訪問 
void uLast(Node* head) 
{ 
    Node *p = head; 
    head = NULL; 
    while(!s.empty()) s.pop(); 
    do 
    { 
        while(p) 
        { 
            s.push(p); 
            p = p->lChild; 
        } 
        p = s.top(); 
        p = p->rChild; 
        if(head == p || p == NULL) 
        { 
            head = s.top(); 
            s.pop(); 
            printf("%c", head->data); 
            p = NULL; 
        } 
    }while(!s.empty()); 
} 
// 計算高度 
int calH(Node* head) 
{ 
    if(!head) return 0; 
    int left = calH(head->lChild); 
    int right = calH(head->rChild); 
    int h; 
    if(left > right) { 
        h = left + 1; 
    } 
    else  
    { 
        h = right + 1; 
    } 
    return h; 
} 
 
// 計算左子葉子個數 
int calLeftChild(Node *t) 
{ 
    if(!t) return 0; 
    else if(t->lChild && !t->lChild->lChild && !t->lChild->rChild) return 1; 
    else return calLeftChild(t->lChild) + calLeftChild(t->rChild); 
} 
 
int main() 
{ 
    char a[1000]; 
    int c; 
    scanf("%d", &c); 
    while(c--) 
    { 
        n = -1; 
        scanf("%s", a); 
        Node *head; 
        createTree(&head, a); 
        preVisit(head); 
        putchar('\n'); 
        midVisit(head); 
        putchar('\n'); 
        lastVisit(head); 
        putchar('\n'); 
        printf("非遞歸先序\n"); 
        uPre(head); 
        putchar('\n'); 
        printf("\n非遞歸中序\n"); 
        uMid(head); 
        putchar('\n'); 
        printf("\n非遞歸後序\n"); 
        uLast(head); 
        putchar('\n'); 
        printf("\n%d\n", calH(head)); 
        printf("%d\n", calLeftChild(head)); 
    } 
    return 0; 
}