数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++二叉树中节点的后序遍历后续节点
在这个问题中，我们给定一个二叉树和一个节点。我们的任务是打印该二叉树中节点的后序遍历后续节点。
二叉树是一种特殊的树，其中每个节点最多可以有两个子节点。
后序遍历是一种树遍历技术，其中首先遍历左子树，然后遍历右子树，最后遍历根节点。
上述树的后序遍历：8 4 2 7 9 6
让我们来看一个例子来理解这个问题。
输入 - 上例中的二叉树，节点 = 7
输出 - 9
解释 - 我们可以在二叉树的后序遍历中看到它。
为了解决这个问题，一个简单、容易且适合初学者的解决方案是简单地找到后序遍历，然后打印遍历中下一个数字。
但是我们需要学习更有效的解决方案，
有效的解决方案将涉及对后序遍历进行一些一般的观察。
由于根节点是后序遍历中的最后一个节点，因此它的后续节点是 NULL。
如果当前节点是右子节点，则父节点是后续节点。
如果当前节点是左子节点，则
如果缺少右兄弟节点，则后续节点是父节点
如果存在右兄弟节点，则该节点或其最左边的子节点是后续节点。
这种方法是有效的，时间复杂度为 O(h)，h 是树的高度。
示例
程序演示了我们解决方案的实现，
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int value;
};
struct Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main(){
struct Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2);
root->left->parent = root;
root->left->left = insertNode(8);
root->left->left->parent = root->left;
root->left->right = insertNode(4);
root->left->right->parent = root->left;
root->right = insertNode(9);
root->right->parent = root;
root->right->left = insertNode(7);
root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
}输出
Postorder successor of 4 is 2
更新于：2020年4月17日
595 次浏览
广告