按照教材中关于二叉树的抽象数据类型定义，采用二叉链表存储结构，编程实现二叉树的各种基本操作，并通过主函数调用，简单测试各基本函数的正确性。 比如：二叉树的基本操作可包括： (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 <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct BTreeNode{
    ElemType data;
    struct BTreeNode *left;
    struct BTreeNode *right;
}BTreeNode, *BTree;

void InitBT(BTree &BT)
{
    BT = NULL;
}

void CreateBT(BTree &BT, char *a)
{
    if(*a == '\0')
        return;
    if(*a == '#')
    {
        BT = NULL;
    }
    else
    {
        BT = (BTreeNode *)malloc(sizeof(BTreeNode));
        BT->data = *a;
        CreateBT(BT->left, a + 1);
        CreateBT(BT->right, a + 2);
    }
}

int EmptyBT(BTree BT)
{
    if(BT == NULL)
        return 1;
    else
        return 0;
}

int DepthBT(BTree BT)
{
    if(BT == NULL)
        return 0;
    else
    {
        int left_depth = DepthBT(BT->left);
        int right_depth = DepthBT(BT->right);
        return (left_depth > right_depth) ? (left_depth + 1) : (right_depth + 1);
    }
}

int NodeCount(BTree BT)
{
    if(BT == NULL)
        return 0;
    else
        return (NodeCount(BT->left) + NodeCount(BT->right) + 1);
}

void PreOrder(BTree BT)
{
    if(BT)
    {
        printf("%c ", BT->data);
        PreOrder(BT->left);
        PreOrder(BT->right);
    }
}

void InOrder(BTree BT)
{
    if(BT)
    {
        InOrder(BT->left);
        printf("%c ", BT->data);
        InOrder(BT->right);
    }
}

void PostOrder(BTree BT)
{
    if(BT)
    {
        PostOrder(BT->left);
        PostOrder(BT->right);
        printf("%c ", BT->data);
    }
}

int FindBT(BTree BT, ElemType x)
{
    if(BT == NULL)
        return 0;
    else if(BT->data == x)
        return 1;
    else
        return (FindBT(BT->left, x) || FindBT(BT->right, x));
}

void DestroyBT(BTree &BT)
{
    if(BT)
    {
        DestroyBT(BT->left);
        DestroyBT(BT->right);
        free(BT);
        BT = NULL;
    }
}

以下是一个简单的测试：

int main()
{
    BTree BT;
    char a[] = "AB##C##D#E##";
    CreateBT(BT, a);

    printf("PreOrder: ");
    PreOrder(BT);
    printf("\n");

    printf("InOrder: ");
    InOrder(BT);
    printf("\n");

    printf("PostOrder: ");
    PostOrder(BT);
    printf("\n");

    printf("NodeCount: %d\n", NodeCount(BT));

    printf("Depth: %d\n", DepthBT(BT));

    printf("Find 'B': %d\n", FindBT(BT, 'B'));
    printf("Find 'F': %d\n", FindBT(BT, 'F'));

    DestroyBT(BT);

    return 0;
}