1 Star 0 Fork 0

hsmath/PAT advanced

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
1102.cpp 1.95 KB
一键复制 编辑 原始数据 按行查看 历史
hsmath 提交于 2021-05-09 04:00 . 1102
/**
* @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();
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/hsmath/pat-advanced.git
git@gitee.com:hsmath/pat-advanced.git
hsmath
pat-advanced
PAT advanced
master

搜索帮助