要求是根据层序遍历输入,进行preorder输出
我的代码已经可以实现手动输入值,来进行输出了,其中null时为0
我想从字符串带空格输入时,也能进行同样的操作,该怎么办呢?
#include <vector>
#include <iostream>
#include <string>
#include<queue>
#include<sstream>
#include <string>
#include <iomanip>
#include <utility>
#include <iostream>
#include <stdexcept>
// include alg
#include<algorithm>
using namespace std;
typedef int type;
typedef struct treeNode {
type data;
treeNode* left;
treeNode* right;
}treeNode;
//按照层序遍历构造二叉树
//假设层序序列已经存进vector中,并且是一颗完全二叉树
treeNode* creatBinTree(vector<int> arr) {
queue<treeNode*> q;
//如果层序序列为空,返回空树
if (arr.empty()) {
return nullptr;
}
treeNode* head = new treeNode; //创建头节点
head->data = arr[0]; //存放数组首元素
q.push(head); //入队
treeNode* bt;
int i = 1;
while (!q.empty()) {
bt = q.front(); //取出头节点,准备给它安排左右孩子
q.pop(); //头节点出队,每一次新的循环,都让头出队
//先弄左孩子
//i只要不超过数组的有效长度,就有左孩子
if (i < arr.size()) {
if (arr[i]==0)
{
bt->left = nullptr;
i++;
}
else
{
bt->left = new treeNode;
bt->left->data = arr[i];
q.push(bt->left); //左孩子入队
i++; //数组后移
}
}
else {
bt->left = nullptr;
}
//再弄右孩子
if (i < arr.size()) {
if (arr[i]==0)
{
bt->right = nullptr;
i++;
}
else{
bt->right = new treeNode;
bt->right->data = arr[i];
q.push(bt->right); //右孩子入队
i++; //数组后移
}
}
else {
bt->right = nullptr;
}
}
return head; //最后队列为空就出while,返回头节点
}
void preorder(treeNode* head) //前序遍历 递归
{
if (head == NULL)
{
return;
}
cout << head->data << " ";
preorder(head->left);
preorder(head->right);
}
//层序遍历二叉树
int main() {
vector<int> a;
a.push_back(1);
a.push_back(0);
a.push_back(2);
a.push_back(4);
a.push_back(0);
a.push_back(3);
a.push_back(5);
a.push_back(6);
a.push_back(7);
treeNode* head = creatBinTree(a);
preorder(head);
}