使用C ++程序实现后序遍历
在后序遍历中，左子树首先是右子树，然后是根，即按照LRN（左右节点）的顺序，其中Node是当前节点。
在此，
L（递归遍历左子树）
R（递归遍历右子树）
N（过程节点，即当前根）
后遍历可以通过两种方式完成：
1.递归
算法：
postorder(root)
a. Traverse the left subtree (inorder(root->left))
b. Traverse the right subtree (inorder(root->right))
c. visit the root2.通过非递归方法
通过使用堆栈来实现此方法。
a. push root into the ‘post’ (first stack)
b. repeat while ‘post’ is not empty
1. pop the node from ‘post’ and push it to ‘pout’ (second stack)
2. push the left and right child of the node to ‘post’
c. print the elements of ‘pout’C++代码实现后遍历
#include<iostream>
#include<stack>
using namespace std;
/*structure to store a BST*/
struct node
{
int info;
node *left,*right;
};
/*Method to create a newNode if a tree does not exist*/
node *newNode(int n)
{
node *ptr=new node;
ptr->info=n;
ptr->left=ptr->right=NULL;
return ptr;
}
/*Method to insert given node in the BST */
node *insert(node* node,int info)
{
if(node==NULL)
{
return newNode(info);
}
if(info < node->info)
{
node->left=insert(node->left,info);
}
else
{
node->right=insert(node->right,info);
}
return node;
}
/*Method to print postorder traversal of a BST*/
void postorder(node *root)
{
stack<node*> post;
post.push(root);
stack<int> pout;
while(!post.empty())
{
node *curr=post.top();
post.pop();
pout.push(curr->info);
if(curr->left)
{
post.push(curr->left);
}
if(curr->right)
{
post.push(curr->right);
}
}
cout<<"PostOrder traversal :";
while(!pout.empty())
{
cout<<pout.top()<<" ";
pout.pop();
}
}
//主程序
int main(){
node* root=newNode(60);
insert(root,50);
insert(root,70);
insert(root,40);
insert(root,30);
insert(root,80);
insert(root,75);
insert(root,65);
insert(root,45);
insert(root,55);
insert(root,90);
insert(root,67);
/*Call/invoke statement for postorder method*/
postorder(root);
cout<<endl;
return 0;
}输出结果
PostOrder traversal :30 45 40 55 50 67 65 90 80 75 70 60