bt_main.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include "bt.h"

template <class T> void printAncestors(Binary_tree<T> tree, T& x)   //打印x及其祖先结点
 { typedef  struct{ Binary_node<T>* ptr; int tag;  }StackNode;
   StackNode ST[100];  int i,top = -1 ,find=0; 
   Binary_node<T>* t=tree.GetRoot();	
   if(t->data==x){ cout<<x<<" is Root\n"; return; }  
   while(t && t->data!=x || top!=-1)
     { while(t && t->data != x)	                       //搜索左子树寻找值为x的结点
          {  ST[++top].ptr=t; ST[top].tag=0;t=t->left; } 
       if(t && t->data==x)                                //找到值为x的结点
	   { for(i=0; i<=top; i++) cout<<ST[i].ptr->data<<endl; 
	     cout<<x<<endl;  find=1;
	     break;
	   }
        else                                            //未找到值为x的结点
         { while(top!=-1 && ST[top].tag==1)top--;
           if(top!=-1)                                    //转向右子树
           { ST[top].tag=1;
             t=ST[top].ptr->right;
           }
       }
    } 
  if(!find)cout<<" search "<<x<<" not exists\n"; 
}      
void visit(int &i)
 { cout<<i<<' '; }
void visitchar(char &c)
 { cout<<c<<' '; }

void main(void)
{ Binary_tree<int> b;   int x;
  cout<<"input integer create Binary_tree(0_end!)  "; cin>>x;
  while(x)
   { b.insert(x); cin>>x; }
  cout<<"Binary_tree B Recursive PreOrder is\t";
  b.preorder(visit); cout<<endl;
  cout<<"Binary_tree B Recursive InOrder is\t";
  b.inorder(visit); cout<<endl;  
  cout<<"\ninput Search Node val ";  cin>>x;
  cout<<"\n Search Node && ancestors is :\n";
  printAncestors(b,x);
   
  Binary_tree<char> a('0');    char y;
  cout<<"\n\ninput char create Binary tree('0' empty subtree!)  "; 
  a.CreatBinary_tree();
  cout<<"Binary_tree  A Recursive InOrder is\t";
  a.inorder(visitchar); cout<<endl;
  cout<<"Binary_tree  A Recursive PostOrder is\t";
  a.postorder(visitchar); cout<<endl;
  cout<<"\ninput Search Node val ";  cin>>y;
  cout<<"\n Search Node && ancestors is :\n";
  printAncestors(a,y);

}