二叉树的基本操作

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;

const int N=100;
typedef struct edge* node;

struct edge
{
    char data;
    node l;
    node r;
};

//通过先序序列和中序序列构造二叉树 
node insert(char *a, char *b, int n)
{
    int i;
    int n1=0, n2=0;
    int m1=0, m2=0;
    char la[N], ra[N];
    char lb[N], rb[N];
    node BT=NULL;
    if(n==0)
        return NULL;
    BT=(node) malloc(sizeof(struct edge));
    if(!BT)
        return NULL;
    memset(BT,0,sizeof(edge));
    BT->data=a[0];
    for(i=0;i<n;i++)
    {
        if(i<=n1&&(b[i]!=a[0]))
            lb[n1++]=b[i];
        else if(b[i]!=a[0])
            rb[n2++]=b[i];
    }
    for(i=1;i<n;i++)
    {
        if(i<=n1)
            la[m1++]=a[i];
        else
            ra[m2++]=a[i];
    }
    BT->l=insert(la, lb, n1);
    BT->r=insert(ra, rb, n2);
    return BT;
}

//通过后序序列和中序序列构造二叉树 
node push(char *a, char *b, int n)
{
    int i;
    int n1=0, n2=0;
    int m1=0, m2=0;
    char la[N], ra[N];
    char lb[N], rb[N];
    node BT=NULL;
    if(n==0)
        return NULL;
    BT=(node) malloc(sizeof(struct edge));
    if(!BT)
        return NULL;
    memset(BT,0,sizeof(edge));
    BT->data=a[n-1];
    for(int i=0;i<n;i++)
    {
        if(i<=n1&&(b[i]!=a[0]))
            lb[n1++]=b[i];
        else if(b[i]!=a[0])
            rb[n2++]=b[i];
    }
    for(i=0;i<n-1;i++)
    {
        if(i<=n1)
            la[m1++]=a[i];
        else
            ra[m2++]=a[i];
    }
    BT->l=push(la, lb, n1);
    BT->r=push(ra, rb, n2);
    return BT;
}

//先序遍历 
void Preorder(node BT)
{
    if(BT==NULL)
        return;
    printf("%c ", BT->data);
    Preorder(BT->l);
    Preorder(BT->r);
}

//非递归的先序遍历 
//void 

//中序遍历
void Inorder(node BT)
{
    if(BT==NULL)
        return;
    Inorder(BT->l);
    printf("%c ", BT->data);
    Inorder(BT->r);
}

//非递归的中序遍历
//void

//后序遍历
void Postorder(node BT)
{
    if(BT==NULL)
        return;
    Postorder(BT->l);
    Postorder(BT->r);
    printf("%c ", BT->data);
}

//非递归的后序遍历 
//void 

//层序遍历
void  Traversal(node BT)
{
    queue<char> q;
    if(!BT) return;
    q.push(BT->data);
    while(q.size())
    {
        printf("%c ", q.front());
        q.pop();
        if(BT->l) q.push(BT->l->data);
        if(BT->r) q.push(BT->r->data);
    }
}

//计算二叉树树高 
int high(node BT)
{
    if(BT)
    {
        int hl=high(BT->l);
        int hr=high(BT->r);
        int maxh=(hl>hr)?hl:hr;
        return maxh+1;
    }
    else return 0;
}

//输出二叉树的叶子结点 
void yezi(node BT)
{
    if(BT)
    {
        if(!BT->l&&!BT->r) 
            printf("%c ", BT->data);
        yezi(BT->l);
        yezi(BT->r);
    } 
} 


int main()
{
    int n;
    char a[N], b[N];
    node BT;
    BT=NULL;
    scanf("%d", &n);
    getchar();
    for(int i=0;i<n;i++)
        scanf("%c", &a[i]);
    getchar();
    for(int i=0;i<n;i++)
        scanf("%c", &b[i]);
    BT=insert(a, b, n);
    int t=high(BT);
    printf("%d\n", t);
    return 0;
}