(PAT 1115) Counting Nodes in a BST (二叉查找树-统计指定层元素个数)

﹏ヽ暗。殇╰゛Y 2022-04-23 08:16 133阅读 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

解题思路:

先建树,按照二叉查找树的规定插入元素即可

然后层序遍历二叉查找树,同时保留每个元素的层号,通过一个hash表统计每层元素的个数(每次元素出队就使该层数的元素数量+1),最后输出哈希表中最大层和倒数第二层元素的数量即可

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    const int MAXN = 1010;
    int TArray[MAXN];
    int N;
    int layerMap[MAXN] = { 0 };
    struct SBNode {
    	int data;
    	SBNode* lchild, *rchild;
    	SBNode(int _data) {
    		data = _data;
    		lchild = nullptr;
    		rchild = nullptr;
    	}
    };
    
    void SBInsert(SBNode* &root, int value) {
    	if (root == nullptr) {
    		root = new SBNode(value);
    		return;
    	}
    	if (value <= root->data) {   //注意看题
    		SBInsert(root->lchild, value);
    	}
    	else {
    		SBInsert(root->rchild, value);
    	}
    }
    
    
    SBNode* createTree(int dataArray[], int N) {
    	SBNode* root = nullptr;
    	for (int i = 0; i < N; ++i) {
    		SBInsert(root, dataArray[i]);
    	}
    	return root;
    }
    
    int curLayer = 0;
    void BFSTREE(SBNode* root) {
    	queue<SBNode*> bfs_queue;
    	queue<int> layer_queue;
    	layer_queue.push(0);
    	bfs_queue.push(root);
    	while (!bfs_queue.empty()) {
    		SBNode* curNode = bfs_queue.front();
    		int layer = layer_queue.front();
    		curLayer = layer;
    		layerMap[curLayer]++;
    		bfs_queue.pop();
    		layer_queue.pop();
    		if (curNode->lchild != nullptr) {
    			bfs_queue.push(curNode->lchild);
    			layer_queue.push(curLayer+1);
    		}
    		if (curNode->rchild != nullptr) {
    			bfs_queue.push(curNode->rchild);
    			layer_queue.push(curLayer+1);
    		}
    	}
    
    	printf("%d + %d = %d", layerMap[curLayer], layerMap[curLayer - 1], layerMap[curLayer] + layerMap[curLayer - 1]);
    }
    
    
    int main() {
    	scanf("%d", &N);
    	for (int i = 0; i < N; ++i) {
    		scanf("%d", &TArray[i]);
    	}
    
    	SBNode* root = createTree(TArray, N);
    	BFSTREE(root);
    	return 0;
    }