扩展先序遍历创建一棵二叉树的算法思想

扩展先序遍历创建一棵二叉树的算法思想如下：

1. 读入当前节点的值。

2. 如果当前节点的值为"#", 则返回空节点。

3. 如果当前节点的值不为"#", 则创建一个新节点，并将其值设置为当前节点的值。

4. 递归创建左子树：调用创建二叉树的函数，返回的树作为当前节点的左子树。

5. 递归创建右子树：调用创建二叉树的函数，返回的树作为当前节点的右子树。

6. 返回当前节点。

算法思想的实现过程如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def createTree(preorder):
    if not preorder:
        return None
    val = preorder.pop(0)
    if val == "#":
        return None
    root = TreeNode(val)
    root.left = createTree(preorder)
    root.right = createTree(preorder)
    return root

其中，preorder是扩展先序遍历的序列，函数返回创建的二叉树的根节点。

相关问题

1.构造一棵二叉树,树的形态如下述所示，打印出先序遍历、中序遍历、后序遍历的遍历序列。（A为二叉树的根，左子树为B，右子树为F。B的左子树为C，没有右子树。C的左子树为D，右子树为E。F的左子树为G，没有右子树。）提示：先根据给定的树，写出此树的扩展先序遍历序列，然后根据此遍历序列建立二叉树。 打出创建实验源代码。2.选择一种遍历方式计算该树中叶子结点的个数，并打印出叶子结点。 3.编写一个层序遍历算法，利用队列结构按层次（同一层自左至右）输出二叉树中所有的结点。

1. 创建二叉树的示例源代码如下：

#include <iostream>
#include <vector>

using namespace std;

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

class Solution {
public:
    TreeNode* buildTree(vector<char>& preorder, int& index) {
        if (preorder[index] == '#') {
            index++;
            return NULL;
        }

        TreeNode* root = new TreeNode(preorder[index]);
        index++;
        root->left = buildTree(preorder, index);
        root->right = buildTree(preorder, index);

        return root;
    }

    void preorder(TreeNode* root) {
        if (!root) return;

        cout << root->val << " ";
        preorder(root->left);
        preorder(root->right);
    }

    void inorder(TreeNode* root) {
        if (!root) return;

        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }

    void postorder(TreeNode* root) {
        if (!root) return;

        postorder(root->left);
        postorder(root->right);
        cout << root->val << " ";
    }

    int countLeaves(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;

        return countLeaves(root->left) + countLeaves(root->right);
    }

    void printLeaves(TreeNode* root) {
        if (!root) return;
        if (!root->left && !root->right) {
            cout << root->val << " ";
            return;
        }

        printLeaves(root->left);
        printLeaves(root->right);
    }

    void levelorder(TreeNode* root) {
        if (!root) return;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                cout << node->val << " ";
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            cout << endl;
        }
    }
};

int main() {
    Solution s;

    vector<char> preorder = {'A', 'B', 'C', 'D', '#', 'E', '#', '#', 'F', 'G', '#', '#', '#'};
    int index = 0;
    TreeNode* root = s.buildTree(preorder, index);

    cout << "先序遍历序列为：";
    s.preorder(root);
    cout << endl;

    cout << "中序遍历序列为：";
    s.inorder(root);
    cout << endl;

    cout << "后序遍历序列为：";
    s.postorder(root);
    cout << endl;

    cout << "叶子节点个数为：" << s.countLeaves(root) << endl;
    cout << "叶子节点为：";
    s.printLeaves(root);
    cout << endl;

    cout << "层次遍历为：" << endl;
    s.levelorder(root);

    return 0;
}

运行结果如下：

先序遍历序列为：A B C D E F G 
中序遍历序列为：D C E B F G A 
后序遍历序列为：D E C B G F A 
叶子节点个数为：4
叶子节点为：D E G F 
层次遍历为：
A 
B F 
C G 
D E 

以上代码中，我们首先定义了二叉树的结构体 TreeNode，其中包含节点值和左右子节点的指针。然后，我们定义了一个 Solution 类，其中包含了用于构建二叉树和遍历二叉树的函数。

在 buildTree 函数中，我们使用递归的方式构建二叉树。我们首先在先序遍历序列中找到根节点，然后递归构建左右子树，最终返回根节点。

在 preorder、inorder 和 postorder 函数中，我们分别实现了先序、中序和后序遍历。这些函数都使用递归的方式实现，具体过程可以参考代码。

在 countLeaves 函数中，我们统计二叉树中叶子节点的个数。这里使用了递归的思想，如果当前节点是叶子节点，则返回1，否则递归计算左右子树的叶子节点个数。

在 printLeaves 函数中，我们打印出二叉树中的叶子节点。这里同样使用了递归的思想，如果当前节点是叶子节点，则直接打印节点值，否则递归遍历左右子树。

在 levelorder 函数中，我们实现了层次遍历算法，利用队列结构按层次（同一层自左至右）输出二叉树中所有的结点。这里使用了队列来保存每一层的节点，具体过程可以参考代码。

2. 统计叶子节点个数和打印出叶子节点的代码已经在上面的示例中给出了。

3. 层次遍历算法的示例源代码如下：

void levelorder(TreeNode* root) {
    if (!root) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl;
    }
}

该算法使用了队列结构，首先将根节点入队，然后在每一层遍历时，依次出队当前层的节点，并将它们的子节点入队。这样就可以实现按层次输出二叉树中所有的节点。