编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： abc##de#g##f### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

### 回答1： 以下是Python代码实现： class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def buildTree(preorder): if not preorder: return None val = preorder.pop() if val == '#': return None root = TreeNode(val) root.left = buildTree(preorder) root.right = buildTree(preorder) return root def inorderTraversal(root): if not root: return [] res = [] stack = [] while root or stack: while root: stack.append(root) root = root.left root = stack.pop() res.append(root.val) root = root.right return res preorder = input("请输入先序遍历字符串：") root = buildTree(list(preorder)) print("中序遍历结果为：", inorderTraversal(root)) ### 回答2： 建立二叉树的过程涉及树的遍历技巧和指针操作技术。具体实现思路如下： 首先，用户输入的先序遍历字符串要被按照字符一个一个的读入。读入的字符一般是字符指针类型。所以需要声明一个字符指针类型的变量来存储用户输入的字符，并且需要一个while循环来不停的读取用户的输入，直到用户结束。 接着，根据用户输入的先序遍历字符串构建一个二叉树。二叉树是由节点构成的，所以需要声明一个节点数据结构类型的变量来存储每一个节点的数据（这里我们假设节点内存储的是字符类型数据）。节点还需要存储指向左右子节点的指针，这里我们声明两个节点类型的指针变量，分别指向左右子节点。 接下来，需要使用递归的方式来构建二叉树。首先读入一个字符，作为当前节点的数据值，并在内存中为该节点开辟空间。然后将左子节点的指针指向递归构建的左子树，右子节点的指针指向递归构建的右子树。当读取到空字符‘\0’时，递归结束，返回空指针。 最后，将根节点返回给主函数，完成二叉树的构建。实现代码如下： ```C #include <stdio.h> #include <stdlib.h> typedef struct node{ char data; //节点存储的数据 struct node *leftchild; //指向左子节点 struct node *rightchild; //指向右子节点 }TreeNode; TreeNode *pTree = NULL; //递归构建二叉树 TreeNode *createBinaryTree() { char ch; TreeNode *p; scanf("%c", &ch); if (ch == '#') //读到“#”表示该节点为空节点，返回NULL return NULL; p = (TreeNode*) malloc(sizeof(TreeNode)); //为当前节点分配内存 p->data = ch; //存储节点数据 p->leftchild = createBinaryTree(); //递归构建左子树 p->rightchild = createBinaryTree(); //递归构建右子树 return p; //返回当前节点指针 } //先序遍历输出二叉树 void printBinaryTree(TreeNode *pTree) { if (pTree == NULL) return; printf("%c ", pTree->data); //先访问根节点 printBinaryTree(pTree->leftchild); //递归访问左子树 printBinaryTree(pTree->rightchild); //递归访问右子树 } int main() { printf("请输入先序遍历二叉树字符串：\n"); pTree = createBinaryTree(); printf("先序遍历输出该二叉树的值："); printBinaryTree(pTree); return 0; } ``` 总之，面试官在考察此类编程题的时候，不仅注重代码实现，还包括思路、算法优化、错误处理等方面。最重要的是，程序员在编程过程中应注重思维的飞跃，比如如何描述复杂的概念、如何利用递归的思路求解问题，这些都是关键。 ### 回答3： 要建立二叉树，需要按照先序遍历的顺序来读入字符串，并且要根据先序遍历的规则构建出二叉树。 具体的建立过程如下： 首先，读入字符串，并将其存储在一个字符数组中。 接着，定义一个指向二叉树结点的指针，初始化为NULL（空树）。 然后，用一个循环遍历字符串的每一个字符，遇到字符就根据先序遍历的规则构建相应的二叉树结点。 具体来说，遍历到一个字符时，首先为该字符构建一个新的二叉树结点，并为其赋值；然后，根据先序遍历的规则，将该结点作为上一个结点的左儿子（如果上一个结点没有左儿子），或者右儿子（如果上一个结点没有右儿子）。 最后，返回指向根结点的指针，这个指针就是我们建立的二叉树的根。 具体实现过程中，可以定义一个递归函数来遍历字符串和构建二叉树结点。每次递归时，都将下一个字符作为参数传入，并根据先序遍历的规则构建出相应的二叉树结点。当字符串读完后，递归就结束了，返回对应子树的根指针。 例如，针对先序遍历字符串abc，可以写出如下的伪代码： ``` // 定义二叉树结点 struct node { char val; node* left; node* right; }; // 递归函数，用于构建二叉树 node* build(char* s, int& pos) { if (s[pos] == '\0') { return NULL; // 字符串读完，返回空指针 } node* root = new node; // 创建新结点 root->val = s[pos]; // 节点值为当前字符 root->left = NULL; // 初始化左右指针 root->right = NULL; pos++; // 指针指向下一个字符 root->left = build(s, pos); // 递归构建左子树 pos++; // 指针指向下一个字符 root->right = build(s, pos); // 递归构建右子树 return root; // 返回当前子树的根指针 } // 主函数 int main() { char s[100]; cin >> s; // 读入字符串 int pos = 0; node* root = build(s, pos); // 构建二叉树 // 对树进行操作，如打印节点值等 return 0; } ``` 以上是一个简单的实现方法，可以根据需要进行修改和优化。总的来说，建立一个二叉树需要把先序遍历的顺序考虑清楚，加以实现。在实现过程中，可以用递归函数来遍历字符串和构建二叉树结点，方便又容易理解。