代码拉取完成,页面将自动刷新
/**
* @file 1102.cpp
* @author Shuang Hu <hsmath@ubuntu>
* @date Sun May 9 03:35:26 2021
*
* @brief PAT 1102:Invert a Binary-Tree: Another way to store a tree
*
*
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
bool isroot[10];
class TNode{
public:
int left;//Mark the index,-1 means NULL.
int right;
};
class BinaryTree{
private:
vector<TNode> Nodes;
int nodenum;
int root;
public:
BinaryTree(int nodenum);
void Level_order();
void In_order();
void inordertraverse(int index);
};
int change(char c){
if(c=='-'){
return -1;
}else{
return c-'0';
}
}
BinaryTree::BinaryTree(int nodenum){
this->nodenum=nodenum;
for(int i=0;i<nodenum;i++){
isroot[i]=true;
}
for(int i=0;i<nodenum;i++){
TNode T;
char c1,c2;
cin>>c1>>c2;
int d1,d2;
d1=change(c1);
d2=change(c2);
T.left=d2;
T.right=d1;
if(d1!=-1){
isroot[d1]=false;
}
if(d2!=-1){
isroot[d2]=false;
}
Nodes.push_back(T);
}
for(int i=0;i<nodenum;i++){
if(isroot[i]==true){
root=i;
break;
}
}
}
void BinaryTree::Level_order(){
int d=root;
queue<int> Q;
Q.push(d);
bool isfirst=true;
while(Q.empty()==false){
int r=Q.front();
Q.pop();
if(isfirst==true){
cout<<r;
isfirst=false;
}else{
cout<<" "<<r;
}
if(Nodes[r].left!=-1){
Q.push(Nodes[r].left);
}
if(Nodes[r].right!=-1){
Q.push(Nodes[r].right);
}
}
cout<<endl;
}
void BinaryTree::In_order(){
inordertraverse(root);
cout<<endl;
}
void BinaryTree::inordertraverse(int index){
static bool isfirst=true;
if(index==-1){
return;
}
inordertraverse(Nodes[index].left);
if(isfirst==true){
cout<<index;
isfirst=false;
}else{
cout<<" "<<index;
}
inordertraverse(Nodes[index].right);
return;
}
int main(){
int nodes;
cin>>nodes;
BinaryTree BT(nodes);
BT.Level_order();
BT.In_order();
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。