设二叉树的结点的数据域的类型为char，请完成： (1) 根据带空的先缀串建立一棵二叉树 (2) 输出先序、中序和后序遍历的结果 (3) 输出叶子节点的数量 (4) 输出二叉树的深度 (5) 输出非递归中序遍历的结果

好的，下面是针对你的问题的回答：

(1) 根据带空的先缀串建立一棵二叉树

根据带空的先缀串建立一棵二叉树的算法如下：

1. 读入一个字符c
2. 如果c是空格，则返回空指针
3. 否则，创建一个新的节点，并将c保存到该节点的数据域中
4. 递归调用建立左子树
5. 递归调用建立右子树
6. 返回新建的节点

代码实现如下：

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

Node* buildTree() {
    char c;
    cin >> c;
    if (c == ' ') {
        return NULL;
    }
    Node* root = new Node;
    root->data = c;
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

(2) 输出先序、中序和后序遍历的结果

输出先序遍历的结果的算法如下：

1. 如果当前节点为空，则返回
2. 输出当前节点的数据域
3. 递归调用先序遍历左子树
4. 递归调用先序遍历右子树

代码实现如下：

void preOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

输出中序遍历的结果的算法如下：

1. 如果当前节点为空，则返回
2. 递归调用中序遍历左子树
3. 输出当前节点的数据域
4. 递归调用中序遍历右子树

代码实现如下：

void inOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    cout << root->data << " ";
    inOrder(root->right);
}

输出后序遍历的结果的算法如下：

1. 如果当前节点为空，则返回
2. 递归调用后序遍历左子树
3. 递归调用后序遍历右子树
4. 输出当前节点的数据域

代码实现如下：

void postOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << " ";
}

(3) 输出叶子节点的数量

输出叶子节点的数量的算法如下：

1. 如果当前节点为空，则返回0
2. 如果当前节点没有左子树和右子树，则返回1
3. 否则，递归调用左子树和右子树，并将它们的结果相加

代码实现如下：

int countLeaf(Node* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaf(root->left) + countLeaf(root->right);
}

(4) 输出二叉树的深度

输出二叉树的深度的算法如下：

1. 如果当前节点为空，则返回0
2. 否则，递归调用左子树和右子树，取它们的较大值，并加上1，即为当前节点所在子树的深度

代码实现如下：

int depth(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

(5) 输出非递归中序遍历的结果

输出非递归中序遍历的结果的算法如下：

1. 创建一个栈s和一个指针p，初始时p指向根节点
2. 当p非空或s非空时，执行以下步骤：
1. 如果p非空，则将p入栈，并将p指向p的左子节点
2. 否则，从栈中弹出一个节点，并输出该节点的数据域，并将p指向该节点的右子节点

代码实现如下：

void inOrderNonRec(Node* root) {
    stack<Node*> s;
    Node* p = root;
    while (p != NULL || !s.empty()) {
        if (p != NULL) {
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
}