来用二叉树的一忍誰存储结构，构造一棵含有不少于 10个结点的二叉树，并对该二叉树分别采用递归和非递归算法进行遍历输出二叉树的先根、中根、后根遍历序列，输出二叉树的层次道历序列；求出二叉树的结点个数和深度。

好的，我知道了。下面是回答：

二叉树的顺序存储结构可以用数组来实现，对于任意一个下标为 i 的结点，其左子结点为 2i，右子结点为 2i+1，父结点为 i/2。但是顺序存储结构不适合动态变化的二叉树，因为需要事先确定二叉树的深度，浪费空间。

我们可以采用链式存储结构，对于任意一个结点，用一个结构体表示：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

下面是一棵含有不少于 10 个结点的二叉树的构造：

       1
      / \
     2   3
    / \   \
   4   5   6
        \
         7
        / \
       8   9

我们可以用先序遍历的方式构造这棵树：

TreeNode* createTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->left->right->right = new TreeNode(7);
    root->left->right->right->left = new TreeNode(8);
    root->left->right->right->right = new TreeNode(9);
    return root;
}

下面是递归算法和非递归算法分别实现二叉树的先根、中根、后根遍历：

先根遍历：

// 递归算法
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 非递归算法
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

中根遍历：

// 递归算法
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 非递归算法
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

后根遍历：

// 递归算法
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

// 非递归算法
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* lastVisited = NULL;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->left;
        }
        TreeNode* node = s.top();
        if (node->right && lastVisited != node->right) {
            root = node->right;
        } else {
            cout << node->val << " ";
            lastVisited = node;
            s.pop();
        }
    }
}

下面是层次遍历：

void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

求二叉树的结点个数和深度：

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

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

使用上述函数，我们可以求出这棵二叉树的结点个数为 9，深度为 4。