1. 编写一个程序btree.cpp，实现二叉树的链式存储结构以及二叉树的各种基本运算：CreateBTree（根据顺序字符串表示创建二叉树，参考课本P232例7.19或课件）、DestroyBTree(销毁二叉树)、FindNode（查找结点）、BTHeight（求二叉树的高度）、DispBTree（用括号表示法输出二叉树）、PreOrder（先序遍历）、InOrder（中序遍历）、PostOrder（后序遍历），LevelOrder（层次遍历）并在此基础上设计一个程序exp5-1.cpp，完成以下功能： （1）二叉树顺序串表示为"ABCDEFG##H####I####JK####################LM"，根据此串创建二叉树b （2）输出二叉树b （3）输出二叉树b的高度 （4）先序遍历b （5）中序遍历b （6）后序遍历b （7）层次遍历b （8）查找'M'结点是否存在 （9）查找'N'结点是否存在 （10）释放二叉树b

好的，我已经记录下来了。以下是btree.cpp的代码实现，可以作为参考：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef struct BNode
{
    char data;
    struct BNode *lchild, *rchild;
} BNode, *BTree;

// 创建二叉树
void CreateBTree(BTree &T, char *s, int &i)
{
    if (s[i] == '#') // 如果是'#'说明该节点为空
    {
        T = NULL;
        i++;
    }
    else
    {
        T = new BNode;
        T->data = s[i];
        i++;
        CreateBTree(T->lchild, s, i); // 递归创建左子树
        CreateBTree(T->rchild, s, i); // 递归创建右子树
    }
}

// 销毁二叉树
void DestroyBTree(BTree &T)
{
    if (T != NULL)
    {
        DestroyBTree(T->lchild); // 递归销毁左子树
        DestroyBTree(T->rchild); // 递归销毁右子树
        delete T;
        T = NULL;
    }
}

// 查找结点
BNode* FindNode(BTree T, char x)
{
    if (T == NULL)
        return NULL;
    else if (T->data == x)
        return T;
    else
    {
        BNode* p = FindNode(T->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(T->rchild, x);
    }
}

// 求二叉树的高度
int BTHeight(BTree T)
{
    if (T == NULL)
        return 0;
    else
    {
        int leftHeight = BTHeight(T->lchild);
        int rightHeight = BTHeight(T->rchild);
        return max(leftHeight, rightHeight) + 1;
    }
}

// 用括号表示法输出二叉树
void DispBTree(BTree T)
{
    if (T != NULL)
    {
        cout << T->data;
        if (T->lchild != NULL || T->rchild != NULL)
        {
            cout << '(';
            DispBTree(T->lchild);
            if (T->rchild != NULL)
                cout << ',';
            DispBTree(T->rchild);
            cout << ')';
        }
    }
}

// 先序遍历
void PreOrder(BTree T)
{
    if (T != NULL)
    {
        cout << T->data << " ";
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 中序遍历
void InOrder(BTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        cout << T->data << " ";
        InOrder(T->rchild);
    }
}

// 后序遍历
void PostOrder(BTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data << " ";
    }
}

// 层次遍历
void LevelOrder(BTree T)
{
    if (T == NULL)
        return;
    queue<BNode*> q;
    q.push(T);
    while (!q.empty())
    {
        BNode* p = q.front();
        q.pop();
        cout << p->data << " ";
        if (p->lchild != NULL)
            q.push(p->lchild);
        if (p->rchild != NULL)
            q.push(p->rchild);
    }
}

int main()
{
    char s[] = "ABCDEFG##H####I####JK####################LM";
    BTree b = NULL;
    int i = 0;
    CreateBTree(b, s, i);

    cout << "二叉树b的括号表示法为: ";
    DispBTree(b);
    cout << endl;

    cout << "二叉树b的高度为: " << BTHeight(b) << endl;

    cout << "二叉树b的先序遍历为: ";
    PreOrder(b);
    cout << endl;

    cout << "二叉树b的中序遍历为: ";
    InOrder(b);
    cout << endl;

    cout << "二叉树b的后序遍历为: ";
    PostOrder(b);
    cout << endl;

    cout << "二叉树b的层次遍历为: ";
    LevelOrder(b);
    cout << endl;

    BNode* p = FindNode(b, 'M');
    if (p != NULL)
        cout << "找到了'M'结点" << endl;
    else
        cout << "没有找到'M'结点" << endl;

    p = FindNode(b, 'N');
    if (p != NULL)
        cout << "找到了'N'结点" << endl;
    else
        cout << "没有找到'N'结点" << endl;

    DestroyBTree(b);

    return 0;
}

接下来是exp5-1.cpp的代码实现，它直接调用了btree.cpp中的函数实现了题目中要求的功能：

#include <iostream>
#include "btree.cpp"
using namespace std;

int main()
{
    char s[] = "ABCDEFG##H####I####JK####################LM";
    BTree b = NULL;
    int i = 0;
    CreateBTree(b, s, i);

    cout << "二叉树b的括号表示法为: ";
    DispBTree(b);
    cout << endl;

    cout << "二叉树b的高度为: " << BTHeight(b) << endl;

    cout << "二叉树b的先序遍历为: ";
    PreOrder(b);
    cout << endl;

    cout << "二叉树b的中序遍历为: ";
    InOrder(b);
    cout << endl;

    cout << "二叉树b的后序遍历为: ";
    PostOrder(b);
    cout << endl;

    cout << "二叉树b的层次遍历为: ";
    LevelOrder(b);
    cout << endl;

    BNode* p = FindNode(b, 'M');
    if (p != NULL)
        cout << "找到了'M'结点" << endl;
    else
        cout << "没有找到'M'结点" << endl;

    p = FindNode(b, 'N');
    if (p != NULL)
        cout << "找到了'N'结点" << endl;
    else
        cout << "没有找到'N'结点" << endl;

    DestroyBTree(b);

    return 0;
}

希望能够帮到你！