1115 Counting Nodes in a BST (30 分) 二叉搜索树BST 输出层结点数

￡神魔★判官ぃ 2021-11-02 12:12 198阅读 0赞

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 N (≤1000) which is the size of the input sequence. Then given in the next line are the N integers in \[−10001000\] which are supposed to be inserted into an initially empty binary search tree.

### 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: ###

9
    25 30 42 16 20 20 35 -5 28

### Sample Output: ###

2 + 4 = 6

给一个有n个结点的搜索二叉树，输出最底层和倒数第二层的节点数。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct node
    {
    	int val;
    	node *l,*r;
    };
    node *insert(node* root,int val)
    {
    	if(root==NULL)
    	{
    		root=new node();
    		root->val=val;
    		root->l=root->r=NULL;
    	}
    	else if(val<=root->val)
    	root->l=insert(root->l,val);
    	else if(val>root->val)
    	root->r=insert(root->r,val);
    	return root;
    }
    int max_level,s[1005];
    void dfs(node *root,int h)
    {
    	//if(root==NULL) return;
    	max_level=max(max_level,h);
    	s[h]++;
    	if(root->l!=NULL) dfs(root->l,h+1);
    	if(root->r!=NULL) dfs(root->r,h+1);
    }
    int main()
    {
    	int n,i,j,x;
    	node *root=NULL;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		root=insert(root,x);
    	}
    	max_level=-1;
    	memset(s,0,sizeof s);
    	dfs(root,0);
    	printf("%d + %d = %d\n",s[max_level],s[max_level-1],s[max_level]+s[max_level-1]);
    }

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct Node
    {
    	int val;
    	struct Node *l,*r;
    	Node()
    	{
    		val=-1001;
    		l=r=NULL;
    	}
    };
    void insert(struct Node* root,int x)
    {
    	if(root->val==-1001)
    	{
    		root->val=x;
    		return;
    	}
        if(x<=root->val)
        {
        	if(root->l==NULL)root->l=new Node;
        	insert(root->l,x);
        }
        else
        {
        	if(root->r==NULL)root->r=new Node;
        	insert(root->r,x);
        }
        
    }
    int max_level;
    int s[1005];
    void dfs(Node *root,int level)
    {
    	max_level=max(max_level,level);
    	s[level]++;
    	if(root->l!=NULL)dfs(root->l,level+1);
    	if(root->r!=NULL)dfs(root->r,level+1);
    }
    int main()
    {
    	int n,k,i;
    	Node *root=new Node;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&k);
    		insert(root,k);
    	}
    	max_level=-1;
    	memset(s,0,sizeof s);
    	dfs(root,0);
    	printf("%d + %d = %d\n",s[max_level],s[max_level-1],s[max_level]+s[max_level-1]);
    }

也可以直接在插入结点的时候就计算层数

void insert(node *u,int val,int level)
    {
    	if(u->val==-1001)
    	{
    		u->val=val;
    		maxlevel=max(level,maxlevel);
    		sum[level]++;
    		return;
    	}
    	if(val<=u->val)
    	{
    		if(u->l==NULL)u->l=new node;
    		insert(u->l,val,level+1);
    	}
    	else
    	{
    		if(u->r==NULL)u->r=new node;
    		insert(u->r,val,level+1);
    	}
    }