DS第5章学习小结-蒲公英云

DS第5章学习小结

一、谈谈你对本章的学习心得，或者任选本章一道题目，谈谈你解决该题的心得体会

　　谈谈我做　　第5章作业7-1 List Leaves　　的心得体会吧

　　简单讲，就是　　输入一棵树，然后从上到下、从左到右输出叶子结点。

　　这题其实跟老师在实验课上带我们写的那个　　第5章实践1第2题7-2 深入虎穴　　很像，都需要用到层次遍历，然后再稍作修改就差不多了。

附上我的代码：

1 #include<iostream>
  2 #include<queue>
  3 using namespace std;
  4 
  5 
  6 typedef struct
  7 {
  8     int data[2];
  9 }node;
 10 
 11 
 12 int input(node *&a);//按顺序依次输入每个结点的左右孩子，无孩子则用‘-’代替 
 13 void find(const node *a, const int root);//从上到下、从左到右输出叶子结点 
 14 
 15 
 16 
 17 
 18 int main()//List Leaves
 19 {
 20     node *a;
 21     
 22     
 23     int root=0;
 24     root=input(a);
 25     
 26     
 27     find(a,root);
 28     
 29     
 30 return 0;
 31 }
 32 
 33 
 34 
 35 
 36 int input(node *&a)//按顺序依次输入每个结点的左右孩子，无孩子则用‘-’代替 
 37 {
 38     int n=0;
 39     cin>>n;
 40     a=new node[n];
 41     
 42     
 43     bool *vi;
 44     vi=new bool[n];
 45     for(int i=0; i<n; i++)
 46     {
 47         vi[i]=false;
 48     }
 49     
 50     
 51     for(int i=0; i<n; i++)
 52     {
 53         char x;
 54         for(int j=0; j<2; j++)
 55         {
 56             cin>>x;//输入，若为正常的0~9数字则录入 
 57             if('0'<=x && x<='9')
 58             {
 59                 a[i].data[j]=x-'0';
 60                 vi[x-'0']=true;
 61             }
 62             else
 63             {
 64                 a[i].data[j]=-1;
 65             }
 66         }
 67     }
 68     
 69     
 70     for(int i=0; i<n; i++)
 71     {
 72         if(!vi[i])
 73         {
 74             return i;//返回根的下标 
 75         }
 76     }
 77 }
 78 
 79 
 80 void find(const node *a, const int root)//从上到下、从左到右输出叶子结点 
 81 {
 82     queue<int> q;
 83     q.push(root); 
 84     int x=0;//以下用于表示队头元素（当前结点） 
 85     bool flag=true;//以下用于判断是否为第一次输出
 86     bool empty=true;// 以下用于判断当前结点是否为叶子节点 
 87     
 88     
 89     while(!q.empty())
 90     {
 91         x=q.front();
 92         q.pop();
 93         
 94         
 95         empty=true;
 96         for(int i=0; i<2; i++)
 97         {
 98             if(a[x].data[i]!=-1)
 99             {
100                 empty=false;//若不是-1则该结点还有孩子结点，该结点为非叶子节点 
101                 break;
102             }
103         }
104         
105         
106         if(!flag && empty)
107         {
108             cout<<' '<<x;
109         }
110         else if(flag && empty)
111         {
112             cout<<x;
113             flag=0;
114         }
115         
116         
117         if(!empty)
118         {
119             for(int i=0; i<2; i++)
120             {
121                 if(a[x].data[i]!=-1)
122                 {
123                     q.push(a[x].data[i]);//将刚刚出队的结点(若该结点不为叶子节点)的孩子依次从左到右入队 
124                 }
125             }
126         }
127     }
128 }