資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告