数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中二叉树节点的前序后继
在这个问题中，我们给定一棵二叉树和一个节点值。我们的任务是打印该节点的前序后继。
二叉树是一种特殊的树，其中每个根节点最多可以有两个子节点。
前序遍历是一种遍历树节点的方式。在这种方式下，我们将首先遍历根节点，然后遍历左子节点，最后遍历右子节点。
前序后继节点是在节点的前序遍历中紧跟在该节点之后的节点。
让我们举一个例子来理解这个问题。
Input: 9 Output 0 Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.
为了解决这个问题，一种朴素的方法是找到二叉树的前序遍历，然后打印在给定数字之后出现的元素。
一个更有效的解决方案将涉及检查给定数字的位置，然后根据位置搜索其后继。因此，如果该位置有左子节点，则前序后继是左子节点。如果它是一个叶子节点，但它是左子节点，则其兄弟节点是前序后继。如果它是一个叶子节点，并且不是左子节点，则我们必须向上移动到其祖先节点，其子节点将成为前序后继。
程序将使解决方案更清晰。
示例
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
if (n->left)
return n->left;
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
if (parent == NULL)
return NULL;
return parent->right;
}
int main(){
Node* root = insertNode(99);
root->parent = NULL;
root->left = insertNode(4);
root->left->parent = root;
root->left->left = insertNode(18);
root->left->left->parent = root->left;
root->left->right = insertNode(50);
root->left->right->parent = root->left;
root->right = insertNode(26);
root->right->parent = root;
root->right->left = insertNode(5);
root->right->left->parent = root->right;
root->right->right = insertNode(10);
root->right->right->parent = root->right;
Node* preOrder = preOrderSuccessorNode(root, root->left->right);
if (preOrder) {
cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
} else {
cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
}
return 0;
}输出
Preorder successor of 50 is 26
更新于: 2020年2月3日
569 次浏览
广告