二叉树_非递归先中后序_递归非递归求深度

#include<stdlib.h>
#include<stdio.h>
#include<stack>
#define N 50
using namespace std;

typedef struct tree{
    char ch;
    struct tree *lchild;
    struct tree *rchild;
}BitTree; 

//键盘输入 
BitTree *CreateTree(){
    BitTree *bt;
    char str;
    scanf("%c", &str);
    if(str=='#')
        return NULL;
    else{
        bt=(BitTree *)malloc(sizeof(BitTree));
        bt->ch=str;
        bt->lchild=CreateTree();
        bt->rchild=CreateTree();
        return bt;
    }
}

//数组输入
BitTree *CreateTree(int A[], int i, int n){
    BitTree *bt;
    if(i>n)
        return NULL;
    else{
        bt=(BitTree *)malloc(sizeof(BitTree));
        if(A[i]=='#')
            return NULL;
        bt->ch=A[i];
        bt->lchild=CreateTree(A, 2*i, n);
        bt->rchild=CreateTree(A, 2*i+1, n);
        return bt;
    }
} 

//非递归先序 
void PreOrder(BitTree *bt){
    BitTree *STACK[N], *p = bt;
    int top = -1;
    while(top != -1 || p!=NULL){
        while(p != NULL){
            STACK[++top] = p;
            printf("%c ",p->ch);//和中序的不同之处 
            p = p->lchild;
        }
        p = STACK[top--];
        p = p->rchild;
    }
}

//非递归中序 
void InOrder(BitTree *bt){
    BitTree *STACK[N], *p = bt;
    int top = -1;
    while(top != -1 || p!=NULL){
        while(p != NULL){
            STACK[++top] = p;
            p = p->lchild;
        }
        p = STACK[top--];
        printf("%c ",p->ch);//和前序的不同之处 
        p = p->rchild;
    }
}

//非递归后序 
void PostOrder(BitTree *bt){
    BitTree *STACK1[N], *p = bt;
    int STACK2[N], top=-1, flag;
    while(top != -1 || p!=NULL){
        while(p != NULL){
            STACK1[++top] = p;
            STACK2[top] = 0;
            p = p->lchild;
        } 
        p = STACK1[top];
        flag = STACK2[top--];
        if(flag == 1){
            printf("%c ", p->ch);
            p = NULL;
        }
        else{
            STACK1[++top] = p;
            STACK2[top] = 1;
            p = p->rchild;
        }
    }
} 

//递归求二叉树深度
int Depth_1(BitTree *bt){
    int ldepth, rdepth;
    if(bt==NULL)
        return 0;
    else{
        ldepth=Depth_1(bt->lchild);
        rdepth=Depth_1(bt->rchild);
        if(ldepth>rdepth)
            return ldepth+1;
        else
            return rdepth+1;
    }
} 

//非递归求二叉树深度
int Depth_2(BitTree *bt){
    BitTree *STACK1[N], *p = bt;
    int STACK2[N];
    int cur , max = 0, top = -1;
    if(bt != NULL){
        cur = 1;
        while(top != -1 || p != NULL){
            while(p != NULL){
                STACK1[++top] = p;
                STACK2[top] = cur++;
                p = p->lchild;
            }
            p = STACK1[top];
            cur = STACK2[top--];
            if(p->lchild==NULL && p->rchild==NULL)
                if(cur > max)
                    max = cur;
            p = p->rchild;
            cur++;
        }
    }
    return max;
} 

int main(){
    int A[N]={'#','A','B','C','D','E','#','F','G','H'};
    BitTree *bt=CreateTree(A,1,9);
    printf("前序遍历非递归实现：
");
    PreOrder(bt);
    printf("
");
    printf("中序遍历非递归实现：
");
    InOrder(bt);
    printf("
");
    printf("后序遍历非递归实现：
");
    PostOrder(bt);
    printf("
");
    printf("Depth_Recursive:%d",Depth_1(bt));
    printf("
");
    printf("Depth_nonRecursive:%d",Depth_2(bt));
    return 0; 
}