C语言实现二叉树遍历的迭代算法
本文实例讲述了C语言实现二叉树遍历的迭代算法，是数据结构算法中非常经典的一类算法。分享给大家供大家参考。
具体实现方法如下：
二叉树中序遍历的迭代算法：
#include<iostream>
#include<stack>
usingnamespacestd;
structNode{
Node(inti,Node*l=NULL,Node*r=NULL):item(i),left(l),right(r){}
intitem;
Node*left;
Node*right;
};
Node*construct(){
Node*node6=newNode(16);
Node*node5=newNode(12);
Node*node4=newNode(8);
Node*node3=newNode(4);
Node*node2=newNode(14,node5,node6);
Node*node1=newNode(6,node3,node4);
Node*node0=newNode(10,node1,node2);
returnnode0;
}
//递归算法
voidinorder(Node*root)
{
if(root==NULL)
return;
inorder(root->left);
cout<<root->item<<"";
inorder(root->right);
}
voidpreorder(Node*root)
{
if(root==NULL)
return;
cout<<root->item<<"";
preorder(root->left);
preorder(root->right);
}
voidpostorder(Node*root)
{
if(root==NULL)
return;
postorder(root->left);
postorder(root->right);
cout<<root->item<<"";
}
voidpostorder2(Node*root)
{
if(root==NULL)
return;
stack<Node*>nstack;
Node*pre=NULL;
nstack.push(root);
Node*node=NULL;
while(!nstack.empty())
{
node=nstack.top();
if(pre!=node->left&&pre!=node->right)
{
if(node->right)
nstack.push(node->right);
if(node->left)
nstack.push(node->left);
}
if(node->left==NULL&&node->right==NULL
||pre==node->left||pre==node->right)
{
cout<<node->item<<"";
nstack.pop();
}
pre=node;
}
}
voidpreorder2(Node*root)
{
if(root==NULL)
return;
stack<Node*>nstack;
Node*node=root;
while(node!=NULL||!nstack.empty())
{
while(node!=NULL)
{
cout<<node->item<<"";
nstack.push(node);
node=node->left;
}
node=nstack.top();
nstack.pop();
node=node->right;
}
}
voidpreorder3(Node*root)
{
if(root==NULL)
return;
stack<Node*>nstack;
nstack.push(root);
Node*node=NULL;
while(!nstack.empty())
{
node=nstack.top();
nstack.pop();
cout<<node->item<<"";
if(node->right)
nstack.push(node->right);
if(node->left)
nstack.push(node->left);
}
}
//迭代算法
voidinorder2(Node*root)
{
if(root==NULL)
return;
stack<Node*>nstack;
nstack.push(root);
Node*next=root->left;
while(next!=NULL||!nstack.empty())
{
while(next!=NULL)
{
nstack.push(next);
next=next->left;
}
next=nstack.top();
nstack.pop();
cout<<next->item<<"";
next=next->right;
}
}
intmain()
{
Node*root=construct();
cout<<"---------中序遍历递归---------"<<endl;
inorder(root);
cout<<endl;
cout<<"---------中序遍历迭代---------"<<endl;
inorder2(root);
cout<<endl;
cout<<"---------先序遍历递归---------"<<endl;
preorder(root);
cout<<endl;
cout<<"---------先序遍历迭代1---------"<<endl;
preorder2(root);
cout<<endl;
cout<<"---------先序遍历迭代2---------"<<endl;
preorder3(root);
cout<<endl;
cout<<"---------后序遍历递归---------"<<endl;
postorder(root);
cout<<endl;
cout<<"---------后序遍历迭代---------"<<endl;
postorder2(root);
}
关于前序遍历，后来又写的算法如下，供大家参考：
voidpreOrderIterator(Node*root)
{
if(root==NULL)
return;
stack<Node*>nstack;
nstack.push(root);
while(!nstack.empty())
{
Node*top=nstack.top();
while(top!=NULL)
{
if(top->left)
nstack.push(top->left);
cout<<top->data<<"";
top=top->left;
}
while(top==NULL&&!nstack.empty())
{
top=nstack.top()->right;
nstack.pop();
}
if(top!=NULL)
nstack.push(top);
}
}
相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。