資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中計算落在給定範圍內的BST節點數
給定一個由節點組成的二叉搜尋樹和一個範圍，任務是計算落在給定範圍內的節點數並顯示結果。
二叉搜尋樹 (BST) 是一種樹，其中所有節點都遵循以下屬性：
節點的左子樹中的鍵小於或等於其父節點的鍵。
節點的右子樹中的鍵大於其父節點的鍵。
因此，BST 將其所有子樹劃分為兩個部分：左子樹和右子樹，可以定義為：
左子樹(鍵) ≤ 節點(鍵) ≤ 右子樹(鍵)
例如
輸入：
範圍：[11, 40]
輸出：計數為：5
解釋：在給定的二叉搜尋樹中，範圍[11, 40]之間的節點值為14、19、27、31和35，因此共有5個節點。
下面程式中使用的方法如下：
建立一個節點結構，包含資料、左指標、右指標，並建立一個範圍。
建立一個函式來插入使用者將輸入的新節點。
建立另一個函式來計算落在給定範圍內的節點數。
檢查根是否為NULL，如果是，則返回。
現在，檢查如果root->data = Start 且 root->data = End，則返回1。
現在，檢查如果root->data <= high && root->data >= low，則返回1 + getCount(root->left, End, Start) + 遞迴呼叫計數函式(root->right, End, Start)
否則如果，root->data < End，則返回遞迴呼叫計數函式(root->right, End, Start)
否則，返回遞迴呼叫計數函式(root->left, End, Start)
示例
#include<iostream>
using namespace std;
// A BST node
struct node{
int data;
struct node* left, *right;
};
// Utility function to create new node
node *newNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int findcount(node *root, int low, int high){
// Base case
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// If current node is in range, then include it in count and
// recur for left and right children of it
if (root->data <= high && root->data >= low){
return 1 + findcount(root->left, low, high) +
findcount(root->right, low, high);
}
else if (root->data < low){
return findcount(root->right, low, high);
}
// Else recur for left child
else{
return findcount(root->left, low, high);
}
}
// main function
int main(){
// Let us construct the BST shown in the above figure
node *root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10;
int high = 50;
cout << "Count of nodes between [" << low << ", " << high
<< "] is " << findcount(root, low, high);
return 0;
}輸出
如果執行以上程式碼，我們將得到以下輸出：
Count of nodes between [10, 50] is 7
更新於：2020年5月15日
204 次檢視
廣告