使用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
热门推荐
3 祝福语简短的微信
10 幼儿祝福语大全简短贺卡
11 感谢教官文案祝福语简短
12 鼠年同事祝福语简短创意
13 元旦祝福语 简短独特群发
14 妈咪跟我生日祝福语简短
15 给儿子新婚祝福语简短
16 伴娘祝福语长文案简短
17 恭喜高考完祝福语简短
18 生日祝福语送老公简短