二叉树遍历题解：整段输入如何传参？全局变量解答_P1161

shiv15832

TA的个人主页 >

文章

粉丝

获赞

147

访问

3.6k

二叉树遍历题解：整段输入如何传参？全局变量解答

shiv15832

P1161 清华大学/南京大学机试题

发布于2025年3月18日 17:53

阅读数 278

先序遍历如何构建二叉树可以看题目1109题解：https://noobdream.com/post/377728/

本题的问题是如何整个字符串输入的情况下传递参数，如果能将一整段的输入转化为单个的字符放到我们构建二叉树的函数里就很简单了。但经典的for循环能做到吗？显然不行，因为树的构建一般是基于递归，递归本身在循环那么如何将递归套在for循环里面？这条路显然是不可取的。那么我们设置一个全局变量i指向字符串的下标，每次构建节点之后i++不就可以了吗。

代码：#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
   char data;
   struct Node* lchild;
   struct Node* rchild;
}node,*Bitree;
int i = 0;//每次输入需要重置
string s;
Bitree Create(char c){
   if(s[i] == '\0')   return nullptr;
   if(c == '#'){
       i++;//本层i也需要自增，不然错误，很重要！
       return nullptr;
   }
   else{
       Bitree T = new node;
       T->data = c;
       i++;
       T->l...

登录查看完整内容

登录后发布评论

1 条评论

S0meb0dy3

2025年3月19日 10:39

和我想法一样，贴一个我的

#include <bits/stdc++.h>
using namespace std;

string str;
int idx;
struct TreeNode {
	char val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x) {
		val =x;
		left=nullptr;
		right=nullptr;
	}
};
void create(TreeNode *& root) {
	char c=str[idx];
	if(str[idx] == '\0')    return;
	idx++;
	if(c=='#') {
		root=nullptr;
	} else {
		root=new TreeNode(c);
		root->val=c;
		create(root->left);
		create(root->right);
	}
}
void inOrder(TreeNode * root) {
	if(root==nullptr) return;

	inOrder(root->left);
	cout<<root->val<<' ';
	inOrder(root->right);
}

int main() {
	while(cin>>str) {
		idx=0;
		TreeNode * root=nullptr;
		create(root);
		inOrder(root);
		cout<<endl;
	}
	return 0;
}