二叉树的存储结构主要有三种：顺序存储结构，链式存储结构和仿真指针存储结构。本文采用的是二叉树的链式存储结构。
二叉树的链式存储结构就是用指针建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链。每个结点包括三个域：数据域data、左子节点指针域left和右子节点指针域right.
二叉树的结构体定义如下（我们假设int为初始类型）：

typedef int Type;

// 定义二叉树
typedef struct Node {
    Type data;
    struct Node* left;
    struct Node* right;
}BiTreeNode;

初始化

// 初始化二叉树
void Initiate(BiTreeNode** root, Type x) {
    *root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    (*root)->data = x;
    (*root)->left = nullptr;
    (*root)->right = nullptr;
}

左插入结点

// 若当前结点curr非空，则再curr的左子树插入元素值为x的新结点
// 原curr所指结点的左子树成为新插入结点的左子树
// 若插入成功，则返回新插入结点的指针，否则返回空指针
BiTreeNode* InsertLeftNode(BiTreeNode* curr, Type x) {
    if (curr == nullptr) return nullptr;
    BiTreeNode *s, *t;
    s = curr->left;
    t = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    t->data = x;
    curr->left = t;
    t->left = s;
    t->right = nullptr;
    return t;
}

右插入结点

BiTreeNode* InsertRightNode(BiTreeNode* curr, Type x) {
    if (curr == nullptr) return nullptr;
    BiTreeNode* t;
    t = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    t->data = x;
    t->right = curr->right;
    t->left = nullptr;
    curr->right = t;
    return t;
}

// 销毁这个结点及其所有子树
void Destroy(BiTreeNode** root) {
    if (*root != nullptr && (*root)->left != nullptr)
        Destroy(&(*root)->left);
    if (*root != nullptr && (*root)->right != nullptr)
        Destroy(&(*root)->right);
    free(*root);
}

删除所指结点的左子树

void DeleteLeftTree(BiTreeNode* curr) {
    if (curr == nullptr || curr->left == nullptr) return;
    Destroy(&curr->left);
    curr->left = nullptr;
}

删除所指结点的右子树

void DeleteRightTree(BiTreeNode* curr) {
    if (curr == nullptr || curr->right == nullptr) return;
    Destroy(&curr->right);
    curr->right = nullptr;
}

打印二叉树

void PrintBiTree(BiTreeNode* root, int n) {
    // 逆时针旋转90°打印二叉树root，n为缩进层数，初始值为0
    if (root == nullptr) return;
    PrintBiTree(root->right, n+1);
    // visit root
    for (int i = 0; i < n-1; i++) printf("   ");
    if (n > 0) {
        printf("---");
        printf("%d\n", root->data);
    }

    PrintBiTree(root->left, n+1);
}

前序遍历二叉树并按访问顺序将其元素打印出来

void PreOrder(BiTreeNode* root) {
    if (root != nullptr) {
        printf("%d ", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

中序遍历二叉树

void InOrder(BiTreeNode* root) {
    if (root != nullptr) {
        InOrder(root->left);
        printf("%d ", root->data);
        InOrder(root->right);
    }
}

后序遍历二叉树

void PostOrder(BiTreeNode* root) {
    if (root != nullptr) {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%d ", root->data);
    }
}

查找指定元素

BiTreeNode* Search(BiTreeNode* root, Type x) {
    // 找到返回该节点指针，未找到返回空
    BiTreeNode* find = nullptr;
    if (root != nullptr) {
        if (root->data == x)
            find = root;
        else {
            find = Search(root->left, x);
            if (find == nullptr)
                Search(root->right, x);
        }
    }
    return find;
}