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