数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学习
法律研究用 C++ 为所有节点填充中序后继
此问题中，给定一棵树。结构包含指针 next。我们的任务是使用该节点的中序后继填充此指针。
struct node {
int value;
struct node* left;
struct node* right;
struct node* next;
}所有 next 指针都设置为 NULL，我们必须将指针设置为此节点的中序后继。
中序遍历 − 以以下形式进行遍历：
Left node -> root Node -> right node.
中序后继 − 中序后继是树的中序遍历中当前节点之后的节点。
让我们通过一个示例来理解问题：
中序遍历是 7 8 3 5 9 1
填充每个节点 −
Next of 5 is 9 Next of 8 is 3 Next of 7 is 8 Next of 3 is 5 Next of 9 is 1
为了解决此问题，我们将遍历树，但以相反的顺序形式进行。然后，我们将最后一个访问的元素放置到该数的 next 中。
示例
显示我们解决方案实现的程序：
#include<iostream>
using namespace std;
struct node {
int data;
node *left;
node *right;
node *next;
};
node* insertNode(int data){
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
Node->next = NULL;
return(Node);
}
void populateTree(node* pop){
static node *next = NULL;
if (pop){
populateTree(pop->right);
pop->next = next;
next = pop;
populateTree(pop->left);
}
}
void printNext(node * root) {
node *ptr = root->left->left;
while(ptr){
cout<<"Next of "<<ptr->data<<" is ";
cout<<(ptr->next? ptr->next->data: -1)<<endl;
ptr = ptr->next;
}
}
int main() {
node *root = insertNode(15);
root->left = insertNode(99);
root->right = insertNode(1);
root->left->left = insertNode(76);
root->left->right = insertNode(31);
cout<<"Populating the Tree by adding inorder successor to the next\n";
populateTree(root);
printNext(root);
return 0;
}输出
通过在 next 中添加中序后继来填充树
Next of 76 is 99 Next of 99 is 31 Next of 31 is 15 Next of 15 is 1 Next of 1 is -1
更新于： 17-4-2020
190 次浏览
广告