用递归的方法实现以下算法： 1）以二叉链表表示二叉树，建立一棵二叉树； 2）输出二叉树的中序遍历、前序遍历、后序遍历结果；3个函数 3）统计二叉树的深度、结点个数、统计二叉树的叶结点个数；3个函数 用非递归的方法实现：二叉树的非递归中序遍历；实验步骤

实验步骤如下：

1. 定义二叉树的结构体和建立二叉树的函数

typedef struct binary_tree_node {
    char data;
    struct binary_tree_node *left_child;
    struct binary_tree_node *right_child;
} BinaryTreeNode;

BinaryTreeNode* create_binary_tree() {
    BinaryTreeNode *root = NULL;
    char data;
    scanf("%c", &data);
    if (data == '#') { // '#'表示空节点
        root = NULL;
    } else {
        root = (BinaryTreeNode*) malloc(sizeof(BinaryTreeNode));
        root->data = data;
        root->left_child = create_binary_tree();
        root->right_child = create_binary_tree();
    }
    return root;
}

2. 实现二叉树的中序遍历、前序遍历、后序遍历函数

void inorder_traversal(BinaryTreeNode *root) {
    if (root != NULL) {
        inorder_traversal(root->left_child);
        printf("%c ", root->data);
        inorder_traversal(root->right_child);
    }
}

void preorder_traversal(BinaryTreeNode *root) {
    if (root != NULL) {
        printf("%c ", root->data);
        preorder_traversal(root->left_child);
        preorder_traversal(root->right_child);
    }
}

void postorder_traversal(BinaryTreeNode *root) {
    if (root != NULL) {
        postorder_traversal(root->left_child);
        postorder_traversal(root->right_child);
        printf("%c ", root->data);
    }
}

3. 实现统计二叉树的深度、结点个数、统计二叉树的叶结点个数函数

int get_depth(BinaryTreeNode *root) {
    if (root == NULL) {
        return 0;
    } else {
        int left_depth = get_depth(root->left_child);
        int right_depth = get_depth(root->right_child);
        return 1 + (left_depth > right_depth ? left_depth : right_depth);
    }
}

int get_node_count(BinaryTreeNode *root) {
    if (root == NULL) {
        return 0;
    } else {
        return 1 + get_node_count(root->left_child) + get_node_count(root->right_child);
    }
}

int get_leaf_count(BinaryTreeNode *root) {
    if (root == NULL) {
        return 0;
    } else if (root->left_child == NULL && root->right_child == NULL) {
        return 1;
    } else {
        return get_leaf_count(root->left_child) + get_leaf_count(root->right_child);
    }
}

4. 实现二叉树的非递归中序遍历函数

void inorder_traversal_non_recursive(BinaryTreeNode *root) {
    Stack *stack = create_stack();
    BinaryTreeNode *p = root;
    while (p != NULL || !is_empty(stack)) {
        while (p != NULL) {
            push(stack, p);
            p = p->left_child;
        }
        if (!is_empty(stack)) {
            p = pop(stack);
            printf("%c ", p->data);
            p = p->right_child;
        }
    }
}

完整代码如下：