使用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
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短