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程序算法设计的学习有一定的借鉴价值。