嘉定都市网

.pNode;
delete [] sk2;

return top;
}


template <class TElem>
long TBinTree<TElem>::ClusterAncestors(TBinTreeNode0<TElem>* pNode, TBinTreeNode0<TElem>** pNodes)
{
long top, hei;

TBinTreeNode<TElem> *p, *rt;

struct TTraverseStackNode
{
   TBinTreeNode<TElem> *pNode;
   long levelNo;
   char isFirst;
} ;

TTraverseStackNode *sk2;

rt =(TBinTreeNode<TElem>*) GetRoot();
hei=GetHeight(rt);
if (hei<=0) return 0;
sk2 =new TTraverseStackNode[hei+1];
if (sk2==NULL) throw TExcepComm(3);

p  = rt;
top=0;
while (p!=NULL || top!=0)
{
  if (p!=NULL)
  {
   top++;
   sk2[top].pNode=p;
   sk2[top].isFirst = 1;
   if (p==pNode) break;
   p = (TBinTreeNode<TElem> *)p->GetSon(1);
  }
  else
  if (sk2[top].isFirst)
  {
    sk2[top].isFirst = 0;
    p = (TBinTreeNode<TElem> *)(sk2[top].pNode->GetSon(2));
  }
  else
  {
   p = sk2[top].pNode;
   top--;
   p=NULL;
  }
} //while

for (long i=1; i<=top; i++)
   pNodes[i-1]=sk2.pNode;
delete [] sk2;

return top;

}

template <class TElem>
long TBinTree<TElem>::ClusterAncestors(TBinTreeNode0<TElem>* pNode, TElem **e)
{
long top, hei;

TBinTreeNode<TElem> *p, *rt;

struct TTraverseStackNode
{
   TBinTreeNode<TElem> *pNode;
   long levelNo;
   char isFirst;
} ;

TTraverseStackNode *sk2;

rt =(TBinTreeNode<TElem>*) GetRoot();
hei=GetHeight(rt);
if (hei<=0) return 0;
sk2 =new TTraverseStackNode[hei+1];
if (sk2==NULL) throw TExcepComm(3);

p  = rt;
top=0;
while (p!=NULL || top!=0)
{
  if (p!=NULL)
  {
   top++;
   sk2[top].pNode=p;
   sk2[top].isFirst = 1;
   if (p==pNode) break;
   p = (TBinTreeNode<TElem> *)p->GetSon(1);
  }
  else
  if (sk2[top].isFirst)
  {
    sk2[top].isFirst = 0;
    p = (TBinTreeNode<TElem> *)(sk2[top].pNode->GetSon(2));
  }
  else
  {
   p = sk2[top].pNode;
   top--;
   p=NULL;
  }
} //while

for (long i=1; i<=top; i++)
   e[i-1]=&(sk2.pNode->GetElem());
delete [] sk2;

return top;

}

template <class TElem>
long TBinTree<TElem>::ClusterJuniors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,
TTraverseMode tm,
int startLevel,
int endLevel)
{
long levelNo, hei;

TBinTreeNode<TElem> *rt;
rt =(TBinTreeNode<TElem> *) GetRoot();

if (startLevel<0 || endLevel<0)
   hei = GetHeight(rt);
if (startLevel<0) startLevel = hei+startLevel+1;
if (endLevel<0) endLevel = hei+endLevel+1;

levelNo = GetLevel(pNode);
if (levelNo<=0) return 0;

startLevel = levelNo+startLevel-1;
endLevel = levelNo+endLevel-1;

return  ClusterDescendants(rt, pe, tm, startLevel, endLevel );

}

template <class TElem>
long TBinTree<TElem>::ClusterSeniors(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem> **pe,TTraverseMode tm,
                           int startLevel, int endLevel)
{
long levelNo, hei;

TBinTreeNode<TElem> *rt;
rt =(TBinTreeNode<TElem> *) GetRoot();

if (startLevel<0 || endLevel<0)
   hei = GetHeight(rt);
if (startLevel<0) startLevel = hei+startLevel+1;
if (endLevel<0) endLevel = hei+endLevel+1;

levelNo = GetLevel(pNode);
if (levelNo<=0) return 0;

startLevel = levelNo-endLevel+1;
endLevel = levelNo-startLevel+1;

return  ClusterDescendants(rt, pe, tm, startLevel, endLevel );

}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:eleteSubTree(TBinTreeNode0<TElem>* pNode,char sonNo)
{
TBinTreeNode0<TElem> *p;
if (pNode==NULL) return NULL;
p = pNode->GetSon(sonNo);
pNode->SetSon(sonNo, NULL);
return p;
}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:ocate(TBinTreeNode0<TElem>* pNode,TElem *e)
{
TBinTreeNode0<TElem> *p;
if (pNode==NULL) return  NULL;
if (pNode->GetElem()==*e) return pNode;
p =Locate(pNode->GetSon(1), e);
if (p!=NULL) return p;
return Locate(pNode->GetSon(2), e);
}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>img]images/smile/5.gif[/img]nPreToTree(TElem *pa, TElem *ia,
                     long p1, long p2, long i1, long i2)
{
long k;
TBinTreeNode<TElem> *p;

if (i1>i2) return NULL;

k=0;
while (pa[p1]!=ia[i1+k]) k++;

p= new TBinTreeNode<TElem>;
p->SetElem(&pa[p1]);
p->SetSon(1, InPreToTree(pa, ia, p1+1, p1+k, i1, i1+k-1) );
p->SetSon(2, InPreToTree(pa, ia, p1+k+1, p2, i1+k+1, i2) );

if (p->GetSon(1)!=NULL) p->GetSon(1)->SetFather(1,p);
if (p->GetSon(2)!=NULL) p->GetSon(2)->SetFather(2,p);

numNodes=p2-p1+1;
return p;

}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>::GListToTree(long *gListExp, TElem *es, long numElem)
{
TBinTreeNode<TElem> *p, *rt, **s;
long top, i;

if (numElem<2) return NULL;

s = new TBinTreeNode<TElem> *[numElem+1];
if (s==NULL) throw TExcepComm(3);

p = new TBinTreeNode<TElem>;
if (p==NULL)
{
  delete [] s;
  throw TExcepComm(3);
}

top=0; i=1;
rt = p;
p->SetElem(&es[gListExp]);
s[++top] = p;
do
{
  i++;
  if (gListExp=='(') continue;
  if (gListExp==',' || gListExp==')') top--;
  else
  {
   if (gListExp=='*') p = NULL;
   else
   {
    p = new TBinTreeNode<TElem>;
    if (p==NULL)
    {
     delete [] s;
     throw TExcepComm(3);
    }
    p->SetElem(&es[gListExp]);
   }

   if (gListExp[i-1] == '(' )
   {
    s[top]->SetSon(1, p);
    if (p!=NULL) p->SetFather(1, s[top]);
   }
   else
   {
    s[top]->SetSon(2, p);
    if (p!=NULL) p->SetFather(2, s[top]);
   }

   s[++top] = p;

  }

} while (top!=0);


delete [] s;
return rt;

}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:reOrderExToTree(TElem *nodes, int numElem)
{
int i, top;
TBinTreeNode<TElem> *p, *rt;
struct TPreOrderExToTreeStackRec
{ TBinTreeNode<TElem> *pNode;
          char tag;
};

TPreOrderExToTreeStackRec *sk;
if (nodes[0]==-1) return NULL;

sk = new TPreOrderExToTreeStackRec[numElem];
if (sk==NULL) throw TExcepComm(3);

rt = new TBinTreeNode<TElem>;
if (rt==NULL) goto ClearUp;


rt->SetElem(&nodes[0]);

top=0;
top++; sk[top].pNode=rt;
sk[top].tag=0;

i=1;
do
{
  if (nodes==-1)  p=NULL;
  else
  {
   p = new TBinTreeNode<TElem>;
   if (p==NULL) goto ClearUp;

   p->SetElem(&nodes);
  }
  i++;

  if (!sk[top].tag)
    { sk[top].pNode->SetSon(1,p);
      sk[top].tag=1;
    }
  else
    {
     sk[top].pNode->SetSon(2,p);
     top--;
    }
  if (p!=NULL)
  {top++; sk[top].pNode=p;
   sk[top].tag=0;
  }

} while (top!=0);

return rt;

ClearUp:
    delete [] sk;
    throw TExcepComm(3);
}

template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:reOrderExToTree(TElem *nodes)
{
TBinTreeNode<TElem> *rt;
static long start=0;

if (nodes[start]==-1)
{
   start++;
   return NULL;
}
rt = new TBinTreeNode<TElem>;
rt->SetElem(&nodes[start]);
start++;
rt->SetSon(1,PreOrderExToTree(nodes));
rt->SetSon(2,PreOrderExToTree(nodes));

return rt;
}

template <class TElem>
long TBinTree<TElem>::TreeToGList(TBinTreeNode0<TElem> *rt, TElem *e)
{
static long cnt=0;

if (rt==NULL) e[cnt++]='*';
else
{
  e[cnt++] = rt->GetElem();
  if (!rt->IsLeaf())
  {
   e[cnt++] = '(';
   TreeToGList(rt->GetSon(1), e);
   e[cnt++] = ',';
   TreeToGList(rt->GetSon(2), e);
   e[cnt++] = ')';
  }
}
return cnt;
}

template <class TElem>
void TBinTree<TElem>:rint(TBinTreeNode0<TElem> *rt, char mode)
{
switch (mode)
{
  case 1:
    if (rt==NULL) return ;
    cout<<" "<<rt->GetElem();
    Print(rt->GetSon(1),mode);
    Print(rt->GetSon(2),mode);
    break;
  case 2:
    if (rt==NULL) return ;
    Print(rt->GetSon(1),mode);
    cout<<" "<<rt->GetElem();
    Print(rt->GetSon(2),mode);
    break;
  case 3:
    if (rt==NULL) return ;
    Print(rt->GetSon(1),mode);
    Print(rt->GetSon(2),mode);
    cout<<" "<<rt->GetElem();
    break;

}
}

//////////////////Test//////////////////
main()
{
  int pa[]={1, 2, 4, 6, 3, 5, 7, 8};
  int ia[]={2, 6, 4, 1, 3, 7, 5, 8};
  TBinTree<int> t1;

  t1.SetRoot(t1.InPreToTree(pa, ia, 0, 7, 0, 7));
  cout<<"\n";
  t1.Print(t1.GetRoot(),1);

  cout<<"\n";
  t1.Print(t1.GetRoot(),2);

  cout<<"\nTotal number of nodes:"<<t1.GetNumSubNodes(t1.GetRoot());
  cout<<"\nTotal number of leaves:"<<t1.GetNumLeaves(t1.GetRoot());
  cout<<"\nHeight: "<<t1.GetHeight(t1.GetRoot());

  TBinTreeNode<int>* pNodes[10], *p;
  int n, i;
  int **es;

  es = new int*[10];

  n=t1.Cluster(t1.GetRoot(), es, PostOrder);
  cout<<"\n ClusterostOrder";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<*es;
  }

  n=t1.Cluster2(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes, PreOrder);
  cout<<"\nPreOrder: ";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }
  n=t1.Cluster2(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes, InOrder);
  cout<<"\nInOrder:  ";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }
  n=t1.Cluster2(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes, PostOrder);
  cout<<"\nPostOrder:";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }

  n=t1.ClusterDescendants(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes,PreOrder,-2, -1);
  cout<<"\n Clusterevel PreOrder";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }
  n=t1.ClusterDescendants(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes,InOrder,-2, -1);
  cout<<"\n Clusterevel InOrder";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }
  n=t1.ClusterDescendants(t1.GetRoot(), (TBinTreeNode0<int> **)pNodes,PostOrder,-2, -1);
  cout<<"\n Clusterevel PostOrder";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }

  i=7;
  n=t1.ClusterAncestors(i, (TBinTreeNode0<int> **)pNodes);
  cout<<"\n Cluster:Ancestor:";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }

  i=3;
  p=(TBinTreeNode<int> *)t1.Locate(t1.GetRoot(), &i);
  cout<<"\n"<<p->GetElem();

  n=t1.ClusterJuniors(p, (TBinTreeNode0<int> **)pNodes, PreOrder, 1, 2);
  cout<<"\n Cluster:Juniors:";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }
  n=t1.ClusterSeniors(p, (TBinTreeNode0<int> **)pNodes, PreOrder, 1, 2);
  cout<<"\n Cluster:Seniors:";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes->GetElem()<<":"<<t1.GetLevel(pNodes);
  }

  TBinTree<int> t2, t3, t4;
  long listExp[]={'(', 1, '(', 2, '(', '*',',', 4, '(', 6, ',','*',')',')',',',
                  3,'(','*',',',5,'(',7,',',8,')',')',')',')' };
  int es2[]={0,1,2,3,4,5,6,7,8};
  t2.SetRoot(t2.GListToTree(listExp, es2, 8));
  cout<<"\nGListToTree: ";
  t2.Print(t2.GetRoot(),1);

  int nodes[]={1,2,-1, 3, 5, -1, 6, -1, -1, -1, 4, -1, -1};
  t3.SetRoot(t3.PreOrderExToTree(nodes, 6));
  cout<<"\nPreOrderExToTree: ";
  t3.Print(t3.GetRoot(),1);
  cout<<"\n";
  t3.Print(t3.GetRoot(),2);

  t4.SetRoot(t4.PreOrderExToTree(nodes));
  cout<<"\nPreOrderExToTree2: ";
  t4.Print(t4.GetRoot(),1);
  cout<<"\n";
  t4.Print(t4.GetRoot(),2);

  n=t4.TreeToGList(t4.GetRoot(),nodes);
  cout<<"\n";
  for (i=0; i<n; i++)
  {
   if (nodes>=0 && nodes<=9)
     printf(" %d", (char)nodes);
   else printf(" %c", (char)nodes);
  }

  getchar();
}

//---------------------------------------------------------------------------

---

作者: 行云流水    时间: 2002-11-17 21:48
不会这么难吧？？
我们老师真抠！

---

作者: FIGO    时间: 2002-11-18 19:46
小子够懒的啊．

---

作者: 酒狐    时间: 2002-11-19 09:53
谢了！

---

欢迎光临 嘉定都市网 (http://www.jiading.com.cn/)

Powered by Discuz! X3.1