1115 Counting Nodes in a BST （30 分）建立二叉搜索树，求每层结点数目-白红宇

1115 Counting Nodes in a BST （30 分）建立二叉搜索树，求每层结点数目

阅读量：4681 次

发布时间：2019-06-09

本文共 2162 字，大约阅读时间需要 7 分钟。

1115 Counting Nodes in a BST （30 分）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:

925 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6 思路： 　　通过先序遍历建立二叉树，然后使用先序遍历求每层结点数。

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                using namespace std;struct Node{ int data; Node *lchild,*rchild;};void insertBST(Node *&root,int key){ if(root==nullptr) { root=new Node; root->data=key; root->lchild=root->rchild=nullptr; return; } if(key>root->data) insertBST(root->rchild,key); else insertBST(root->lchild,key);}int level[1001];int maxLevel=0;void dfs(int depth,Node *root){ if(root==nullptr) return; level[depth]++; maxLevel=max(depth,maxLevel); dfs(depth+1,root->lchild); dfs(depth+1,root->rchild);}int main(){ int n; cin>>n; //int a[n+1]; Node *root=nullptr; for(int i=0;i
                
                 >temp; insertBST(root,temp); } dfs(1,root);// for(int i=1;i<=maxLevel;i++)// cout<
                 
                  <<" ";// cout<