数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现二叉树的后序遍历（无递归、无栈）
在本问题中，我们给定一棵二叉树。我们的任务是不使用递归和栈来打印二叉树的后序遍历。
二叉树是一种特殊的树，其中每个节点最多可以有两个子节点。
后序遍历是一种树遍历技术，其中首先遍历左子树，然后遍历右子树，最后遍历根节点。
上述树的后序遍历为：8 4 2 7 9 6
为了在不使用递归和栈的情况下遍历树，我们将使用基于深度优先搜索的技术，并将数据存储在哈希表中。
示例
展示此解决方案实现的程序：
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void postOrderTraversal(struct Node* head) {
struct Node* temp = head;
unordered_set<Node*> visited;
while (temp && visited.find(temp) == visited.end()) {
if (temp->left &&
visited.find(temp->left) == visited.end())
temp = temp->left;
else if (temp->right &&
visited.find(temp->right) == visited.end())
temp = temp->right;
else {
cout<<temp->data<<"\t";
visited.insert(temp);
temp = head;
}
}
}
struct Node* insertNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main(){
struct Node* root = insertNode(6);
root->left = insertNode(2);
root->right = insertNode(9);
root->left->left = insertNode(8);
root->left->right = insertNode(4);
root->right->left = insertNode(7);
root->right->left->left = insertNode(13);
cout<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
}输出
Post Order Traversal of the binary tree : 8 4 2 13 7 9 6
可以更新相同的解决方案，并消除哈希表的用法。因为它的作用是存储已访问的节点。我们将为树本身的每个节点添加一个已访问标志以减少系统负载，这将使我们的算法更好。
一个更有效的解决方案是使用无序映射，这将减少回溯到头的开销。
示例
展示此解决方案实现的程序：
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
bool visited;
};
void postOrderTraversal(Node* root) {
Node* n = root;
unordered_map<Node*, Node*> postorder;
postorder.insert(pair<Node*, Node*>(root, nullptr));
while (n) {
if (n->left && postorder.find(n->left) == postorder.end()) {
postorder.insert(pair<Node*, Node*>(n->left, n));
n = n->left;
}
else if (n->right && postorder.find(n->right) == postorder.end()) {
postorder.insert(pair<Node*, Node*>(n->right, n));
n = n->right;
}
else {
cout<<n->data<<"\t";
n = (postorder.find(n))->second;
}
}
}
struct Node* insertNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = false;
return (node);
}
int main() {
struct Node* root = insertNode(6);
root->left = insertNode(2);
root->right = insertNode(9);
root->left->left = insertNode(8);
root->left->right = insertNode(4);
root->right->left = insertNode(7);
root->right->left->left = insertNode(13);
cout<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
}输出
Post Order Traversal of the binary tree : 8 4 2 13 7 9 6
更新于：2020年4月17日
浏览量：353
广告