1. 递归前/中/后序遍历

void BTreePreOrder(BTreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->val);
    BTreePreOrder(root->left);
    BTreePreOrder(root->right);
}

void BTreeInOrder(BTreeNode* root) {
    if (root == NULL) {
        return;
    }

    BTreeInOrder(root->left);
    printf("%d ", root->val);
    BTreeInOrder(root->right);
}

void BTreePostOrder(BTreeNode* root) {
    if (root == NULL) {
        return;
    }

    BTreePostOrder(root->left);
    BTreePostOrder(root->right);
    printf("%d ", root->val);
}

2. 根据数组创建二叉树

-1表示空节点

// 返回一个新节点
BTreeNode* BTreeGetNode(int val) {
    BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
    if (node == NULL) {
        perror("malloc error");
        exit(-1);
    }

    node->val = val;
    node->left = node->right = NULL;

    return node;
}

// 根据数组建立二叉树，-1表示空节点
BTreeNode* BTreeCreate(int* arr, int size, int* usedSize) {
    if (*usedSize == size) {
        return NULL;
    }

    if (*(arr + *usedSize) == -1) {
        *usedSize += 1;
        return NULL;
    }

    BTreeNode* root = BTreeGetNode(*(arr + *usedSize));
    *usedSize += 1;

    root->left = BTreeCreate(arr, size, usedSize);
    root->right = BTreeCreate(arr, size, usedSize);

    return root;
}

3. 二叉树的拷贝

改写任意一种遍历方式即可。

BTreeNode* BTreeGetNode(int val) {
    BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
    if (node == NULL) {
        perror("malloc error");
        exit(-1);
    }

    node->val = val;
    node->left = node->right = NULL;

    return node;
}

BTreeNode* BTreeCopy(BTreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    BTreeNode* newRoot = BTreeGetNode(root->val);
    newRoot->left = BTreeCopy(root->left);
    newRoot->right = BTreeCopy(root->right);

    return newRoot;
}

4. 二叉树的销毁

void BTreeDestroy(BTreeNode* root) {
    if (root == NULL) {
        return;
    }

    BTreeDestroy(root->left);
    BTreeDestroy(root->right);
    free(root);
}

5. 层序遍历

要用到队列，这里省略队列的实现。

void BTreeLevelOrder(BTreeNode* root) {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);

    while (!QueueEmpty(&q)) {
        BTreeNode* cur = QueueHead(&q);
        printf("%d ", cur->val);
        QueuePop(&q);

        if(cur->left)
            QueuePush(&q, cur->left);
        if(cur->right)
            QueuePush(&q, cur->right);
    }
    printf("\n");
}

6. 获取二叉树结点个数

int BTreeNodeCount(BTreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    return 1 + BTreeNodeCount(root->left) + BTreeNodeCount(root->right);
}

7. 获取二叉树第K层节点个数

int BTreeLevelKNodeCount(BTreeNode* root, int k) {
    if (root == NULL || k < 1) {
        return 0;
    }

    if (k == 1) {
        return 1;
    }

    return BTreeLevelKNodeCount(root->left, k - 1) 
        + BTreeLevelKNodeCount(root->right, k - 1);
}

8. 获取二叉树叶子节点个数

int BTreeNodeLeafCount(BTreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    return BTreeNodeLeafCount(root->left) + BTreeNodeLeafCount(root->right);
}

9. 获取二叉树高度

int BTreeHeight(BTreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    int leftHeight = BTreeHeight(root->left);
    int rightHeight = BTreeHeight(root->right);

    return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
}

10. 检测值为x的节点是否在二叉树中

BTreeNode* BTreeFind(BTreeNode* root, int x) {
    if (root == NULL) {
        return NULL;
    }

    if (root->val == x) {
        return root;
    }

    BTreeNode* res;
    res = BTreeFind(root->left, x);
    if (res == NULL) {
        res = BTreeFind(root->right, x);
    }

    return res;
}

11. 二叉树的镜像

void BTreeMirror(BTreeNode* root) {
    if (root == NULL) {
        return;
    }

    BTreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    BTreeMirror(root->left);
    BTreeMirror(root->right);
}

12. 判断二叉树是否是完全二叉树

用层序遍历一遍二叉树，如果遇到过一次空节点后又遇到了非空节点，则是非完全二叉树。如果再没遇到非空节点，则是完全二叉树。

int BTreeIsComplete(BTreeNode* root) {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);

    int sign = 0;  // 标志是否出现了空节点
    while (!QueueEmpty(&q)) {
        if (QueueHead(&q)->val == NULL) {
            sign = 1;
            QueuePop(&q);
        }
        else {
            if (sign == 1) {
                return 0;
            }
            BTreeNode* cur = QueueHead(&q);
            QueuePush(&q, cur->left);
            QueuePush(&q, cur->right);
            QueuePop(&q);
        }
    }
    if (sign == 1) {
        return 1;
    }
}