二叉树第k层节点数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef int ElemType; 
 4 
 5 typedef struct Node{
 6     ElemType data;
 7     Node* lson;
 8     Node* rson;     
 9     Node(ElemType data, Node* lson, Node* rson) {
10         this->data = data;
11         this->lson = lson;
12         this->rson = rson;
13     }   
14 }*Tree;
15 
16 int get_kth_number(Tree T,int k){
17     queue<Tree>q;
18     q.push(T);
19     int h=1,ans=0;
20     Tree r=T;
21     while(!q.empty()){
22         Tree p=q.front();
23         q.pop();
24         if(p->lson)q.push(p->lson);
25         if(p->rson)q.push(p->rson);
26         if(h==k)ans++;
27         if(p==r){
28             if(h==k)break;
29             r=q.back();
30             h++;
31             ans=0;
32         }
33     }
34     return ans;
35 }
36 
37 
38 int main(){
39     Node* v7 = new Node(7, NULL, NULL);
40     Node* v1 = new Node(1, NULL, NULL);
41     Node* v3 = new Node(3, NULL, NULL);
42     Node* v2 = new Node(2, v1, v3);
43     Node* v5 = new Node(5, NULL, NULL);
44     Node* v6 = new Node(6, v5, v7);
45     Node* v4 = new Node(4, v2, v6);
46 
47     Tree T=v4;
48     printf("%d",get_kth_number(T,4));
49 }