数据结构
网络
关系数据库管理系统(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 次浏览
广告