构建二叉树的二叉链表存储结构，实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计各类结点的个数、先序/中序非递归遍历、层序遍历等运算。

二叉树的二叉链表存储结构定义如下：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

其中，data 表示结点的数据项，lchild 和 rchild 分别指向左右子树。

二叉树的创建可以采用递归方式，先输入根结点，然后递归输入左右子树。

void createBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = data;
        createBiTree(&((*T)->lchild));
        createBiTree(&((*T)->rchild));
    }
}

二叉树的先序/中序/后序递归遍历可以采用类似的递归方式，分别先遍历根结点，然后递归遍历左右子树。

// 先序遍历
void preOrder(BiTree T) {
    if (T != NULL) {
        printf("%d ", T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

// 中序遍历
void inOrder(BiTree T) {
    if (T != NULL) {
        inOrder(T->lchild);
        printf("%d ", T->data);
        inOrder(T->rchild);
    }
}

// 后序遍历
void postOrder(BiTree T) {
    if (T != NULL) {
        postOrder(T->lchild);
        postOrder(T->rchild);
        printf("%d ", T->data);
    }
}

统计二叉树的高度可以采用递归方式，左右子树的高度取最大值并加 1。

int getDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        int leftDepth = getDepth(T->lchild);
        int rightDepth = getDepth(T->rchild);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

统计各类结点的个数同样可以采用递归方式，分别统计根结点、左子树、右子树的结点个数。

int getNodeNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        return getNodeNum(T->lchild) + getNodeNum(T->rchild) + 1;
    }
}

int getLeafNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    } else {
        return getLeafNum(T->lchild) + getLeafNum(T->rchild);
    }
}

int getSingleNum(BiTree T) {
    if (T == NULL) {
        return 0;
    } else if ((T->lchild == NULL && T->rchild != NULL) || (T->lchild != NULL && T->rchild == NULL)) {
        return getSingleNum(T->lchild) + getSingleNum(T->rchild) + 1;
    } else {
        return getSingleNum(T->lchild) + getSingleNum(T->rchild);
    }
}

先序/中序非递归遍历采用栈来实现。先序遍历时，先将根结点入栈，然后弹出栈顶结点并输出其值，如果该结点有右子树，则将其右子树入栈；如果该结点有左子树，则将其左子树入栈。中序遍历时，先将根结点入栈，然后将其左子树全部入栈，再弹出栈顶结点并输出其值，最后将其右子树入栈。

// 先序非递归遍历
void preOrderNonRecursive(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree stack[MAXSIZE];
    int top = -1;
    stack[++top] = T;
    while (top != -1) {
        BiTree node = stack[top--];
        printf("%d ", node->data);
        if (node->rchild != NULL) {
            stack[++top] = node->rchild;
        }
        if (node->lchild != NULL) {
            stack[++top] = node->lchild;
        }
    }
}

// 中序非递归遍历
void inOrderNonRecursive(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree stack[MAXSIZE];
    int top = -1;
    BiTree node = T;
    while (node != NULL || top != -1) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->lchild;
        }
        if (top != -1) {
            node = stack[top--];
            printf("%d ", node->data);
            node = node->rchild;
        }
    }
}

层序遍历采用队列来实现。先将根结点入队，然后每次弹出队首结点并输出其值，如果该结点有左子树，则将其左子树入队；如果该结点有右子树，则将其右子树入队。

void levelOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = T;
    while (front != rear) {
        BiTree node = queue[front++];
        printf("%d ", node->data);
        if (node->lchild != NULL) {
            queue[rear++] = node->lchild;
        }
        if (node->rchild != NULL) {
            queue[rear++] = node->rchild;
        }
    }
}