数据结构树的专题

#include<stdio.h>  
#include<stdlib.h>  
  
typedef char ElemType;  
  
typedef struct Node  
{  
    ElemType data;  
    struct Node *lchild, *rchild;  
} BiTree;  
  
BiTree *createBT()  //键盘输入创建二叉树  
{  
    BiTree *b;  
    ElemType ch;  
    scanf("%c", &ch);  
    fflush(stdin);  // 清空键盘缓冲  
    if(ch != '#')   // #表示空  
    {  
        b = (BiTree *)malloc(sizeof(BiTree));  
        b->data = ch;  
        printf("请输入%c的左孩子：", ch);  
        b->lchild = createBT();  
        printf("请输入%c的右孩子：", ch);  
        b->rchild = createBT();  
    }  
    else  
        b = NULL;  
    return b;  
}  
  
void createBT(BiTree *&b, char *s)  //用括号表示法的字符串s生成二叉树b  
{  
    BiTree *st[100], *t;    //st存放树结点的栈  
    int top = -1;  
    int k;      //k=1表示左孩子， k=2表示右孩子  
      
    b = NULL;  
    while(*s)  
    {  
        switch(*s)  
        {  
        case '(':  
            top++;  
            st[top] = t;  
            k = 1;      //准备处理左孩子  
            break;  
        case ')':  
            top--;  
            break;  
        case ',':  
            k = 2;      //准备处理右孩子  
            break;  
        default:  
            t = (BiTree *)malloc(sizeof(BiTree));  
            t->data = *s;  
            t->lchild = t->rchild = NULL;  
            if(b == NULL)  
                b = t;  
            else  
            {  
                switch(k)  
                {  
                case 1:  
                    st[top]->lchild = t; break;  
                case 2:  
                    st[top]->rchild = t; break;  
                }  
            }  
        }  
        s++;  
    }  
}  
  
BiTree *createBT_PreIn(char *pre, char *in, int n)  //由先序序列pre和中序序列in的n个字符构造二叉树并返回  
{  
    BiTree *b;  
    int i;  
    if(n<=0)  
        return NULL;  
    b = (BiTree *)malloc(sizeof(BiTree));  
    b->data = *pre;  
    for(i=0; i<n; i++)  
        if(in[i] == *pre)  
            break;  
    b->lchild = createBT_PreIn(pre+1, in, i);  
    b->rchild = createBT_PreIn(pre+i+1, in+i+1, n-i-1);  
  
    return b;  
}  
  
BiTree *createBT_InPost(char *in, char *post, int n)    //由中序序列in和后序序列post的n个字符构造二叉树并返回  
{  
    BiTree *b;  
    int i;  
    if(n <= 0)  
        return NULL;  
    b = (BiTree *)malloc(sizeof(BiTree));  
    b->data = *(post + n - 1);  
    for(i=0; i<n; i++)  
        if(in[i] == b->data)  
            break;  
    b->lchild = createBT_InPost(in, post, i);  
    b->rchild = createBT_InPost(in+i+1, post+i, n-i-1);  
  
    return b;  
}  
  
void preOrder(BiTree *b)    //先序遍历二叉树  
{  
    if(b)  
    {  
        printf("%c", b->data);  
        preOrder(b->lchild);  
        preOrder(b->rchild);  
    }  
}  
  
void inOrder(BiTree *b)     //中序遍历二叉树  
{  
    if(b)  
    {  
        inOrder(b->lchild);  
        printf("%c", b->data);  
        inOrder(b->rchild);  
    }  
}  
  
void postOrder(BiTree *b)   //后序遍历二叉树  
{  
    if(b)  
    {  
        postOrder(b->lchild);  
        postOrder(b->rchild);  
        printf("%c", b->data);  
    }  
}  
  
void dispBT(BiTree *b)      //括号法输出二叉树  
{  
    if(b)  
    {  
        printf("%c", b->data);  
        if(b->lchild || b->rchild)  
        {  
            printf("(");  
            dispBT(b->lchild);  
            if(b->rchild)  
                printf(",");  
            dispBT(b->rchild);  
            printf(")");  
        }  
    }  
}  
  
int BT_depth(BiTree *b)     //返二叉树的高度  
{  
    int dep1, dep2;  
    if(b == NULL)  
        return 0;  
  
    dep1 = BT_depth(b->lchild);  
    dep2 = BT_depth(b->rchild);  
      
    return (dep1 > dep2 ? dep1 :dep2) + 1;  
}  
  
int leafNum(BiTree *b)      //统计叶子节点的个数  
{  
    if(b == NULL)   
        return 0;  
    if(b->lchild == NULL && b->rchild == NULL)  
        return 1;  
    return leafNum(b->lchild) + leafNum(b->rchild);  
}  
  
BiTree *findNode(BiTree *b, ElemType x)     //查找二叉树b中值为x的结点，并返回该结点的指针  
{  
    BiTree *p;  
    if(b == NULL)  
        return NULL;  
    else if(b->data == x)  
        return b;  
    else  
    {  
        p = findNode(b->lchild, x);  
        if(p != NULL)  
            return p;  
        else  
            return findNode(b->rchild, x);  
    }  
}  
  
void destroyBT(BiTree *&b)  //销毁二叉树  
{  
    if(b)  
    {  
        destroyBT(b->lchild);  
        destroyBT(b->rchild);  
        free(b);  
        b = NULL;  
    }  
}  
  
void main()  
{  
    BiTree *b;  
    char *s = "A(B(,X),C)";  
    char *pre = "ABXC";  
    char *in = "BXAC";  
    char *post = "XBCA";  
  
    //键盘输入二叉树  
    //printf("输入根结点(#表示空)：");  
    //b = createBT();  
  
    //括号表示法输入二叉树  
    //createBT(b, s);  
  
    //先序序列和中序序列输入二叉树  
    //b = createBT_PreIn(pre, in, 4);  
  
    //中序序列和后序序列输入二叉树  
    b = createBT_InPost(in, post, 4);  
  
    printf("\n先序序列："); preOrder(b);   
    printf("\n中序序列："); inOrder(b);  
    printf("\n后序序列："); postOrder(b);  
    printf("\n括号表示法："); dispBT(b);  
    printf("\n深度：%d" , BT_depth(b));   
    printf("\n叶子数：%d\n", leafNum(b));  
    destroyBT(b);  
}