早学完了二叉树。也知道了前序，中序，后序，广度的非递归是怎么实现的。但是一直没有写出程序出来。今天周末就把他写出来了，我觉得这些程序都很容易理解。所有没写什么注释了，这是用C++实现的。在栈是用STL种的栈实现的。如果大家用C语言编写，就一定要记得把它的栈写出来才可以实现。在整个程序中比较难理解的就是找父亲结点的算法和后序非递归实现的A，B。仔细理解还是看的懂的。程序我在VC6.0中实现的。其他编译器就不能保证了。 程序如下： //                                        二叉树的建立。//前序，中序，后序，广度的非递归程序实现。#include <iostream>#include <stack>#include <queue> using namespace std; enum Tags{Left,Right};   template <class Elem>class TreeNode{ public:  TreeNode* left;  TreeNode* right;  Elem data;  TreeNode(Elem dataval,TreeNode* leftval=NULL,TreeNode* rightval=NULL)  {   data=dataval;   left=leftval;   right=rightval;  }  TreeNode(TreeNode* leftval=NULL,TreeNode* rightval=NULL)  {   left=leftval;   right=rightval;  }  ~TreeNode(){}}; template<class Elem>class StackElement{ public:  TreeNode<Elem>* pointer;  Tags tag;}; template<class Elem>class BinTree{ public:  BinTree()  {   init();  }  ~BinTree()  {   DeleteTree(root);  }  //初始化根结点。  void init();  //后序递归删除二叉树。  void DeleteTree(TreeNode<Elem>*);  //有前序递归创建二叉树。  TreeNode<Elem>* Create();  //前序非递归遍历。  void PreOrder(TreeNode<Elem>*);        //中序非递归遍历。  void PreOrderWithoutRecusion(TreeNode<Elem>*);  //后序非递归遍历。  void InOrderWithoutRecusion(TreeNode<Elem>*);  //后序非递归遍历。另一种版本     void PostOrderWithoutRecusion(TreeNode<Elem>*);  //广度优先遍历。  void LevelOrder(TreeNode<Elem>*);  //操作函数。     void Massage(TreeNode<Elem>*);  //查找父亲结点  TreeNode<Elem>* GetParent(TreeNode<Elem>* root,TreeNode<Elem>* current);  //返回父亲结点的指针。  TreeNode<Elem>* Parent(TreeNode<Elem>* current); private:  TreeNode<Elem>* root;}; template<class Elem>void BinTree<Elem>::init(){ root=new TreeNode<Elem>;} template<class Elem>void BinTree<Elem>::DeleteTree(TreeNode<Elem>* T){ if(T!=NULL) {  DeleteTree(T->left);  DeleteTree(T->right);  delete T; }} template<class Elem>TreeNode<Elem>* BinTree<Elem>:: Create(){ TreeNode<Elem>* T; char ch; cin>>ch; if(ch=='#')  T=NULL; else {  T=new TreeNode<Elem>(ch,NULL,NULL);  T->left=Create();  T->right=Create(); } return T;} template <class Elem>void BinTree<Elem>::Massage(TreeNode<Elem>* T){ cout<<T->data<<" ";} template<class Elem>void BinTree<Elem>::PreOrder(TreeNode<Elem>* T){ using std::stack; stack<TreeNode<Elem>*> aStack; TreeNode<Elem>* point=T; while(!aStack.empty()||point!=NULL) {  if(point!=NULL)  {   Massage(point);   aStack.push(point);   point=point->left;  }  else  {   point=aStack.top();   aStack.pop();   point=point->right;  }//end else }//end while} template<class Elem>void BinTree<Elem>::PreOrderWithoutRecusion(TreeNode<Elem>*T){ using std::stack; stack<TreeNode<Elem>*> aStack; TreeNode<Elem>* point=T; while(point!=NULL||!aStack.empty()) {  if(point!=NULL)  {      aStack.push(point);      point=point->left;  }     else  {   point=aStack.top();   Massage(point);   point=point->right;   aStack.pop();  }//end else }//end while} template<class Elem>void BinTree<Elem>::InOrderWithoutRecusion(TreeNode<Elem>* T){    using std::stack; StackElement<Elem> element; stack<StackElement<Elem> > aStack; TreeNode<Elem>* point; if(T==NULL)  return; else  point=T; while(true) {  //从左边进。  while(point!=NULL)  {   element.pointer=point;   element.tag=Left;   aStack.push(element);   point=point->left;  }  element=aStack.top();  aStack.pop();  point=element.pointer;  //从右边进。  while(element.tag==Right)  {   Massage(point);   if(aStack.empty())    return;   else   {    element=aStack.top();    aStack.pop();    point=element.pointer;   }//end else  }//end while  element.tag=Right;  aStack.push(element);  point=point->right; }//end while} template<class Elem>void BinTree<Elem>::PostOrderWithoutRecusion(TreeNode<Elem>* T){ using std::stack; stack<TreeNode<Elem>*> aStack; TreeNode<Elem> *p,*q; if(T==NULL)  return; p=T; do {  while(p!=NULL)  {   aStack.push(p);            p=p->left;  }  q=NULL;  while(!aStack.empty())  {   p=aStack.top();   aStack.pop();   if(p->right==q)         //右子树为空或刚刚访问过。   {    Massage(p);    q=p;   }//end if   else   {    aStack.push(p);    p=p->right;    break;   }//end else  }//end while }while(!aStack.empty());} template<class Elem>void BinTree<Elem>::LevelOrder(TreeNode<Elem>* T){ using std::queue; queue<TreeNode<Elem>*> aQueue; TreeNode<Elem>* point=T; if(point!=NULL)  aQueue.push(point); while(!aQueue.empty()) {  point=aQueue.front();  Massage(point);  aQueue.pop();  if(point->left!=NULL)   aQueue.push(point->left);  if(point->right!=NULL)   aQueue.push(point->right); }//end while} template<class Elem>TreeNode<Elem>* BinTree<Elem>::GetParent(TreeNode<Elem>* root,           TreeNode<Elem>* current){ TreeNode<Elem>* temp; if(root==NULL)  return NULL; //找到父结点。 if(root->left==current || root->right==current)  return root;    //用递归找父结点。 if((temp=GetParent(root->left,current))!=NULL)        return temp; else  return GetParent(root->right,current)} template<class Elem>TreeNode<Elem>* BinTree<Elem>::Parent(TreeNode<Elem>* T){ if(current==NULL||current==T)  return NULL; else  return GetParent(T,current);//递归调用函数找到父结点。} //主函数实现。int main(){ BinTree<char> A; TreeNode<char> *Troot; cout<<"输入字符串：#代表的是空树："<<endl; Troot=A.Create(); cout<<"前序遍历："; A.PreOrder(Troot); cout<<"\n中序遍历："; A.PreOrderWithoutRecusion(Troot); cout<<"\n后序遍历A："; A.InOrderWithoutRecusion(Troot); cout<<"\n后序遍历B: "; A.PostOrderWithoutRecusion(Troot); cout<<"\n广度优先遍历："; A.LevelOrder(Troot); cout<<endl; return 0;}//输入: // 输入字符串：#代表的是空树：// a// b// c// #// #// d// e// #// g// #// #// f// #// #// # //输出样例： //前序遍历：a b c d e g f//中序遍历：c b e g d f a//后序遍历A：c g e f d b a//后序遍历B: c g e f d b a//广度优先遍历：a b c d e f g //程序结束。 我这里写出来。对与那些还没有理解和不知道怎么编写整个程序的同学借鉴和学习。        

评论