使用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
热门推荐
10 财运虎年祝福语简短语
11 单亲爸爸春节祝福语简短
12 狗狗上厕所训练
13 植物种植祝福语简短
14 翻译考试祝福语朋友简短
15 个人周年庆简短祝福语
16 狗狗怎么训练
17 分别祝福语简短搞笑英文
18 生日广州男生祝福语简短