資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 在 BST 中查詢第二大元素
在二叉搜尋樹 (BST) 中，必須返回第二大元素。在二叉樹中，第二大元素是最大的元素。
根據給定的 BST，13 是第二大元素。現在我們使用 C++ 方法來解決這個問題。我們可以遍歷樹的中序遍歷，透過觀察，我們可以觀察到給定 BST 中的第二大元素是 13。樹的中序遍歷將是 1 3 4 6 7 8 10 13 14，我們可以觀察到元素位於排序陣列中。因此，我們返回第二大元素。
讓我們假設一些簡單的輸入和輸出場景
假設二叉樹中的元素如下所示。這裡二叉搜尋樹中只有兩個元素。透過比較節點的值，第二大的值為6。
Input = BST
11
/
6
Output = Second largest element in BST will be: 6
還可以考慮以下場景，因為下面有一個二叉搜尋樹，並且具有大量的節點。下面二叉樹的輸出將是
Input = BST 11 / \ 6 21 / \ 4 31 Output = Second largest element in BST will be: 21
演算法
以下步驟是解決問題的方法。
實現二叉搜尋樹 (BST)。
將節點的值插入 BST。
使用中序遍歷技術，左 -> 根 -> 右 (L-R-R)
然後使用[inorder.size()-2];在 BST 中找出第二大的節點值。
示例
以下是查詢二叉搜尋樹中第二大元素的 C++ 程式碼：
#include <iostream> #include <vector> using namespace std; class Node { public: int val; Node *left, *right; Node(int val) { this->val = val; left = right = NULL; } }; void solve(Node* root, vector<int>& inorder) { if(root == NULL) return; solve(root->left, inorder); inorder.push_back(root->val); solve(root->right, inorder); } int main() { Node* root = new Node(8); root->left = new Node(3); root->right = new Node(10); root->left->left = new Node(1); root->left->right = new Node(6); root->left->right->left = new Node(4); root->left->right->right = new Node(7); root->right->right = new Node(14); root->right->right->left = new Node(13); vector<int> inorder; solve(root, inorder); cout << "Second largest element of this BST is : " << inorder[inorder.size()- 2]; return 0; }
輸出
Second largest element of this BST is: 13
結論
這是一個純粹基於觀察的問題，我們需要觀察樹的中序遍歷的模式。此演算法的時間複雜度為中序遍歷的 O(n)。
更新於： 2022 年 8 月 10 日
630 次檢視
廣告