按照教材中关于二叉树的抽象数据类型定义，采用二叉链表存储结构，编程实现二叉树的各种基本操作，并通过主函数调用，简单测试各基本函数的正确性。 比如：二叉树的基本操作可包括： (1) void InitBT( BTreeNode *&BT ) //初始化二叉树BT (2) void CreateBT( BTreeNode *&BT, char *a ) //根据字符串a所给出二叉树的描述，建立二叉链表存储结构 (3) int EmptyBT( BTreeNode *BT) //检查二叉树BT是否为空，空返回1，否则返回0 (4) int DepthBT( BTreeNode *BT) //求二叉树BT的深度并返回该值 (5) int NodeCount(BTreeNode *BT) //求二叉树BT的总结点个数 (6) void PreOrder( BTreeNode *BT) //先序遍历递归算法 (7) void InOrder( BTreeNode *BT) //中序遍历递归算法 (8) void PostOrder( BTreeNode *BT) //后序遍历递归算法 (9) int FindBT( BTreeNode *BT, ElemType x) //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 (10)void DestroyBT( BTreeNode *&BT ) //销毁二叉树BT

以下是二叉树的基本操作的代码实现：

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

typedef char ElemType;  // 二叉树结点元素类型

// 二叉树结点的结构体
struct BTreeNode {
    ElemType data;   // 结点数据
    BTreeNode *left, *right;  // 左右子树指针
};

// 初始化二叉树BT
void InitBT(BTreeNode *&BT) {
    BT = NULL;
}

// 根据字符串a所给出二叉树的描述，建立二叉链表存储结构
void CreateBT(BTreeNode *&BT, char *a) {
    if (*a == '\0') {  // 如果字符串为空，则返回
        return;
    }
    if (*a == '#') {  // 如果当前字符为#，则将当前结点置为空
        BT = NULL;
    } else {
        BT = new BTreeNode;  // 创建一个新的结点
        BT->data = *a;
        CreateBT(BT->left, a+1);  // 递归构建左子树
        CreateBT(BT->right, a+2);  // 递归构建右子树
    }
}

// 检查二叉树BT是否为空，空返回1，否则返回0
int EmptyBT(BTreeNode *BT) {
    return BT == NULL;
}

// 求二叉树BT的深度并返回该值
int DepthBT(BTreeNode *BT) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else {
        int left_depth = DepthBT(BT->left);   // 递归求左子树深度
        int right_depth = DepthBT(BT->right);  // 递归求右子树深度
        return max(left_depth, right_depth) + 1;  // 返回左右子树深度的最大值加1
    }
}

// 求二叉树BT的总结点个数
int NodeCount(BTreeNode *BT) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else {
        return NodeCount(BT->left) + NodeCount(BT->right) + 1;  // 返回左右子树结点数之和加1
    }
}

// 先序遍历递归算法
void PreOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        cout << BT->data << " ";   // 访问当前结点
        PreOrder(BT->left);   // 递归遍历左子树
        PreOrder(BT->right);  // 递归遍历右子树
    }
}

// 中序遍历递归算法
void InOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        InOrder(BT->left);   // 递归遍历左子树
        cout << BT->data << " ";   // 访问当前结点
        InOrder(BT->right);  // 递归遍历右子树
    }
}

// 后序遍历递归算法
void PostOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        PostOrder(BT->left);   // 递归遍历左子树
        PostOrder(BT->right);  // 递归遍历右子树
        cout << BT->data << " ";   // 访问当前结点
    }
}

// 查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
int FindBT(BTreeNode *BT, ElemType x) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else if (BT->data == x) {  // 如果当前结点的值为x，返回1
        return 1;
    } else {  // 否则在左右子树中进行查找
        return FindBT(BT->left, x) || FindBT(BT->right, x);
    }
}

// 销毁二叉树BT
void DestroyBT(BTreeNode *&BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        DestroyBT(BT->left);   // 递归销毁左子树
        DestroyBT(BT->right);  // 递归销毁右子树
        delete BT;   // 删除当前结点
        BT = NULL;
    }
}

int main() {
    BTreeNode *BT;
    InitBT(BT);

    char a[] = "A#B#C#D#E#F#G#";
    CreateBT(BT, a);

    cout << "先序遍历结果为：";
    PreOrder(BT);
    cout << endl;

    cout << "中序遍历结果为：";
    InOrder(BT);
    cout << endl;

    cout << "后序遍历结果为：";
    PostOrder(BT);
    cout << endl;

    cout << "二叉树的深度为：" << DepthBT(BT) << endl;

    cout << "二叉树的结点数为：" << NodeCount(BT) << endl;

    char x = 'D';
    if (FindBT(BT, x)) {
        cout << "值为" << x << "的结点存在" << endl;
    } else {
        cout << "值为" << x << "的结点不存在" << endl;
    }

    DestroyBT(BT);

    return 0;
}

运行结果如下：

先序遍历结果为：A B D E C F G 
中序遍历结果为：D B E A F C G 
后序遍历结果为：D E B F G C A 
二叉树的深度为：3
二叉树的结点数为：7
值为D的结点存在