資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中找到給定鍵的下一個右節點
在這個題目中，我們得到一棵二叉樹 BT 和一個鍵值。我們的任務是找到給定鍵的下一個右節點。
二叉樹是一種特殊的資料結構，用於儲存資料。
我們透過一個例子來理解這個問題，
輸入
key = 4
輸出
5
解釋
節點 4 旁邊的元素是 5。
解決方案方法
解決這個問題的一個簡單方法是使用 層次遍歷 遍歷二叉樹。對於給定的鍵值，我們將檢查在遍歷中是否存在節點旁邊存在節點。如果存在，則返回下一個節點，否則返回 NULL。
程式展示了我們解決方案的工作原理，
示例
#include <iostream>
#include <queue>
using namespace std;
struct node {
struct node *left, *right;
int key;
};
node* newNode(int key) {
node *temp = new node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
node* findNextRightNodeBT(node *root, int k) {
if (root == NULL)
return 0;
queue<node *> nodeVal;
queue<int> nodeLevel;
int level = 0;
nodeVal.push(root);
nodeLevel.push(level);
while (nodeVal.size()) {
node *node = nodeVal.front();
level = nodeLevel.front();
nodeVal.pop();
nodeLevel.pop();
if (node->key == k) {
if (nodeLevel.size() == 0 || nodeLevel.front() != level)
return NULL;
return nodeVal.front();
}
if (node->left != NULL) {
nodeVal.push(node->left);
nodeLevel.push(level+1);
}
if (node->right != NULL) {
nodeVal.push(node->right);
nodeLevel.push(level+1);
}
}
return NULL;
}
int main() {
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int key = 4;
cout<<"The next right node of the node "<<key<<" is ";
node *nextNode = findNextRightNodeBT(root, key);
if(nextNode != NULL)
cout<<nextNode->key;
else
cout<<"not available";
return 0;
}輸出
The next right node of the node 4 is 5
更新於：2021-03-13
184 次檢視
廣告