資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++二叉樹中節點的先序前驅
在這個問題中，我們給定一個二叉樹和一個節點值。我們的任務是列印該節點的先序前驅。
二叉樹是一種特殊的樹，其中每個根節點最多可以有兩個子節點。
先序遍歷是一種遍歷樹節點的方法。在這種方法中，我們將首先遍歷根節點，然後是左子節點，最後是右子節點。
先序前驅節點是在節點的先序遍歷中出現在該節點之前的節點。
讓我們來看一個例子來理解這個問題
Input: 1 Output: 9
為了解決這個問題，一種簡單的方法是找到二叉樹的先序遍歷，然後打印出現在給定數字之後的元素。
一個更有效的方法將涉及檢查給定數字的位置，然後根據位置搜尋其前驅。如果節點是根節點，則返回NULL，沒有前驅。如果節點是右子節點，則左子節點將是前驅。
程式展示瞭解決方案的實現
示例
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
struct Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->left == NULL || parent->left == n)
return parent;
Node* curr = parent->left;
while (curr->right != NULL)
curr = curr->right;
return curr;
}
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* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
if (preOrderPredecessor)
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
else
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
return 0;
}輸出
Preorder Predecessor of 50 is 18
更新於：2020年2月3日
345 次瀏覽
廣告