c语言二叉树

1. 实验1：实现二叉树的各种基本运算的算法

实验内容： 编写一个程序btree.cpp,实现二叉树的各种基本运算，并在次基础上设计一个程序exp3-1.cpp，完成以下功能。

（1）由图7.34所示（教材P243）的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。

（2）输出二叉树b。

（3）输出‘H’结点的左、右孩子结点值。

（4）输出二叉树b的高度。

（5）释放二叉树b。

#include <stdio.h>
#include "malloc.h"
#define MaxSize 25
typedef int ElemType;
typedef ElemType SqBinTree[MaxSize];
typedef struct node{
    ElemType data;
    struct node * lchild;
    struct node * rchild;
} BTNode;
void CreateBTree(BTNode *& b,char * str){
    BTNode * St[MaxSize],* p;
    int top=-1,k,j=0;
    char ch;
    b=NULL;
    ch=str[j];
    while (ch!='\0'){
        switch (ch) {
            case '(':top++;St[top]=p;k=1;
                break;
            case ')':top--;
                break;
            case ',':k=2;
                break;
            default:p=(BTNode *) malloc(sizeof (BTNode));
                    p->data=ch;
                    p->lchild=NULL,p->rchild=NULL;
                    if (b==NULL)
                    b=p;
                    else{
                    switch (k) {
                    case 1:St[top]->lchild=p;break;
                    case 2:St[top]->rchild=p;break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}
//消耗二叉树
void DestroyBTree(BTNode *& b){
    if (b!=NULL){
        DestroyBTree(b->rchild);
        DestroyBTree(b->lchild);
        free(b);
    }
}
//查找节点
BTNode * FindNode(BTNode *b,ElemType x){
    BTNode *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);
    }
}
//找孩子节点
BTNode *LchildNode(BTNode *p){
    return p->lchild;
}
BTNode *RchildNode(BTNode *p){
    return p->rchild;
}
//求高度
int BTHeight(BTNode *b){
    int lchild,rchild;
    if (b==NULL)return (0);
    else{
        lchild= BTHeight(b->lchild);
        rchild= BTHeight(b->rchild);
        return (lchild>rchild)?(lchild+1):(rchild+1);
        }
}
//输出二叉数
void DispBTree(BTNode *b){
    if (b!=NULL){
        printf("%c",b->data);
        if (b->lchild!=NULL || b->rchild!=NULL){
            printf("(");
            DispBTree(b->lchild);
            if (b->rchild!=NULL)printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}
int main(){
    BTNode *b;
    printf("（1）由图7.34所示（教材P243）的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。\n");
    CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("（2）输出二叉树b。\n");
    DispBTree(b);
    printf("\n");
    printf("（3）输出‘H’结点的左、右孩子结点值。\n");
    BTNode *k=FindNode(b,'H');
    printf("%c\n", LchildNode(k)->data);
    printf("%c\n", RchildNode(k)->data);
    printf("（4）输出二叉树b的高度。\n");
    printf("%d\n", BTHeight(b));
    printf("（5）释放二叉树b。\n");
    DestroyBTree(b);
    DestroyBTree(k);
    return 0;
}