树案例—列出叶结点
程序员文章站
2022-06-07 20:53:35
...
基础实验4-2.2 列出叶结点 (25分)
建树+层序遍历
运行结果
代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define NUL -1
typedef struct TreeNode *Node;
struct TreeNode{
int data;
int Left;
int Right;
}s[50];
int flag=0;
queue<int>q;
void LevelSearch(int Tree){
q.push(Tree);
int temp;
while (!q.empty()){
temp=q.front();
if(s[temp].Left==NUL&&s[temp].Right==NUL){//没有左右子节点即为叶节点
if(flag)
cout<<' ';
cout<<temp;
flag=1;
}
if(s[temp].Left!=NUL)
q.push(s[temp].Left);
if(s[temp].Right!=NUL)
q.push(s[temp].Right);
q.pop();
}
}
int main()
{
int n;
cin>>n;
char a,b;
int mark[n];
memset(mark,0,sizeof(mark));
for(int i=0;i<n;i++){
s[i].Left=-1;
s[i].Right=-1;
}
int Root;
for (int i=0;i<n;i++){
s[i].data=i;
cin>>a>>b;
if(a!='-'){
s[i].Left=a-'0';
mark[a-'0']++;
}
if(b!='-'){
s[i].Right=b-'0';
mark[b-'0']++;
}
}
for (int i = 0; i < n; ++i) {
if(mark[i]==0)
Root=i;
}
LevelSearch(Root);
return 0;
}