8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
4 1 5
#include<iostream>
//#include<malloc.h> //c malloc和free,C++ new和delete
using namespace std;
#define MAXSIZE 100
typedef int ElementType;//int
struct TreeNode{
ElementType data;
int left;
int right;
};
int CreateTree(TreeNode T[]){ //从根节点开始标下标，根节点标0，不存在的节点的标-1，就是Null,最后返回根节点的下标,
int n; cin>>n;
int check[MAXSIZE]={0};//无父节点指向它
char ldata,rdata;
int root=-1;//防止当n=0时，for循环不执行，root没有值
for(int i=0;i<n;i++){
T[i].data=i;
cin>>ldata>>rdata;//这3个都是char类型输进来的，后两个char是因为如果无对应的数据，就输'-'
if(ldata!='-'){
T[i].left=ldata-'0';
check[ T[i].left ]=1;
}else
T[i].left=-1;
if(rdata!='-'){
T[i].right=rdata-'0';
check[ T[i].right ]=1;
}else
T[i].right=-1;
}
for(int i=0;i<n;i++){
if( !check[i] ){
root=i;
break;
}
}
return root;
}
//利用层次遍历一层层地输出叶子结点
void LevelLeaf(TreeNode T[],int root){
if(root==-1) return ;
TreeNode queue[MAXSIZE], p;
int front,rear;
front=rear=0;
bool flag=false;//用于打印叶子结点时的空格
rear=(rear+1)%MAXSIZE;
queue[rear]=T[root];//根节点入队
while(front!=rear){
front=(front+1)%MAXSIZE;
p=queue[front];
if(p.left!=-1){
rear=(rear+1)%MAXSIZE;
queue[rear]=T[p.left];
}
if(p.right!=-1){
rear=(rear+1)%MAXSIZE;
queue[rear]=T[p.right];
}
if(p.left==-1 && p.right==-1){
if(!flag) flag=true;
else cout<<" ";
cout<<p.data;
}
}
}
int main(){
//freopen("input.txt","r",stdin);
TreeNode T[MAXSIZE];
int root;
root=CreateTree(T);
LevelLeaf(T,root);
return 0;
}
