C语言输入字符序列，建立二叉树；按先序、中序、后序遍历二叉树（三种递归算法和中序遍历的非递归算法）； 选作内容： 求二叉树的高度和结点的个数。

建立二叉树的思路：

1. 定义一个结构体表示二叉树的节点，包含数据域和左右子树指针域。

struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
};

2. 输入字符序列，每个字符作为一个节点插入到二叉树中，如果输入字符为‘#’则表示该节点为空。

struct TreeNode* createTree() {
    char data;
    scanf("%c", &data);
    if (data == '#') {
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->data = data;
    root->left = createTree();
    root->right = createTree();
    return root;
}

3. 分别按先序、中序、后序递归遍历二叉树。

void preOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->data);
    inOrder(root->right);
}

void postOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}

4. 中序非递归遍历二叉树。

void inOrderNonRecursive(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[100];
    int top = -1;
    struct TreeNode *p = root;
    while (p || top != -1) {
        while (p) {
            stack[++top] = p;
            p = p->left;
        }
        if (top != -1) {
            p = stack[top--];
            printf("%c ", p->data);
            p = p->right;
        }
    }
}

5. 求二叉树高度和节点个数。

int getHeight(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int getNodesCount(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return getNodesCount(root->left) + getNodesCount(root->right) + 1;
}

完整代码如下：