数据结构
网络
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 次查看
广告