資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中 BST II 中的中序後繼
假設我們在二叉搜尋樹中有一個節點，我們必須找到 BST 中該節點的中序後繼。如果沒有中序後繼，則返回 null。我們知道，某個節點的後繼是鍵值大於該節點的值且最小的節點。
我們可以直接訪問該節點，但不能訪問該樹的根。這裡每個節點都將引用其父節點。以下是節點的定義 −
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}如果輸入為 −
且節點為 2，則輸出為 3。
為解決此問題，我們將遵循以下步驟 −
如果節點的右節點不為 null，則 −
node := node 的右節點
當 node 的左節點不為 null 時，執行該操作 −
node := node 的左節點
返回 node
當 (node 的父節點不為 null 且 node 不等於 node 的父節點的左節點) 時，執行該操作 −
node := node 的父節點
返回 node 的父節點
示例
讓我們檢視以下實現，以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
Node(int v, Node* par = NULL){
val = v;
left = NULL;
right = NULL;
parent = par;
}
};
class Solution {
public:
Node* inorderSuccessor(Node* node) {
if (node->right) {
node = node->right;
while (node->left)
node = node->left;
return node;
}
while (node->parent && node != node->parent->left) {
node = node->parent;
}
return node->parent;
}
};
main(){
Solution ob;
Node *root = new Node(5);
root->left = new Node(3, root);
root->right = new Node(6, root);
root->left->left = new Node(2, root->left);
root->left->right = new Node(4, root->left);
root->left->left->left = new Node(1, root->left->left);
cout << (ob.inorderSuccessor(root->left->left))->val;
}輸入
Node *root = new Node(5); root->left = new Node(3, root); root->right = new Node(6, root); root->left->left = new Node(2, root->left); root->left->right = new Node(4, root->left); root->left->left->left = new Node(1, root->left->left); (ob.inorderSuccessor(root->left->left))->val
輸出
3
更新於：19-Nov-2020
329 檢視
廣告