利用二叉链表递归和非递归算法求叶子结点的数量

这是我的博客的第一篇文章，是学校里布置的一道作业题。

之后有时间的话我会发布更多有意思的博客

 

#include<iostream>
#include<stack>
using namespace std;
int cnt1=0,cnt2=0;
struct BTNode
{
 int data;
 BTNode *l,*r;
 BTNode(const int item=0,BTNode* lptr=NULL,BTNode* rptr=NULL):data(item),l(lptr),r(rptr){}
};
BTNode bt[10000];

inline void add(int a,int b,int c)
{
 bt[a].data=a;
 bt[b].data=b;
 bt[c].data=c;
 bt[a].l=&bt[b];
 bt[a].r=&bt[c];
}

void solve1(int root)                    //递归dfs
{
 if((!bt[root].l||bt[root].l->data==0)&&(!bt[root].r||bt[root].r->data==0))
 {
  cnt1++;
  //cout<<root<<endl;
  return;
 }
 if(bt[root].l&&bt[root].l->data!=0)
 {
  solve1(bt[root].l->data);
 }
 if(bt[root].r&&bt[root].r->data!=0)
 {
  solve1(bt[root].r->data);
 }
}

void solve2(int root)                    //非递归dfs
{
 stack<BTNode> bs;
 bs.push(bt[root]);
 while(!bs.empty())
 {
  BTNode temp=bs.top();
  bs.pop();
  if(temp.l!=NULL&&temp.l->data!=0)
  {
   bs.push(*temp.l);
  }
  if(temp.r!=NULL&&temp.r->data!=0)
  {
   bs.push(*temp.r);
  }
  if((temp.l==NULL||temp.l->data==0)&&(temp.r==NULL||temp.r->data==0))
  {
   cnt2++;
  }
 }
}

int main()
{
 ios::sync_with_stdio(false);
 int t;
 cout<<"输入测试用例数: ";
 cin>>t;
 while(t--)
 {
  memset(bt,0,sizeof(bt));
  cnt1=0;
  cnt2=0;
  int n,a,b,c;
  cout<<"输入结点数: ";
  cin>>n;
  while(1)
  {
   cout<<"输入父节点和其所有子节点: ";      //分别输入父结点，左子结点，右子结点
   cin>>a>>b>>c;
   if(!a&&!b&&!c)                           //输入 0 0 0 结束输入
    break;
   add(a,b,c);
  }
  solve1(1);
  solve2(1);
  cout<<"叶子结点(递归)="<<cnt1<<endl;
  cout<<"叶子结点(非递归)="<<cnt2<<endl;
 }
 return 0;
}

//https://paste.ubuntu.com/p/yZsj5s5f4c/