欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树案例—列出叶结点

程序员文章站 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;
}