亲，您未登录哦！ 登录 | 注册
首页  |  社区  |  工具箱  |  代码库  |  博客  |  招聘  |  文章  |  新闻  |  下载  |  读书
回 帖 发 新 帖 刷新版面

主题：有没人会二叉树的生成啊?????十万火急

Totao [专家分：30] 发布于 2002-11-15 08:38:00

题目是这样的~!用C语言或者PASCAL语言写出...
随机出的二叉树例如A,(B,C,(E, ),D)
根据给出的树用以上语言生成二叉树,要循环1000层.
给出先根,中根,后根,偏历的节结点序列....
我其实什么都不会,请各位高手指教~~!~!~!~!
本帖地址：  http://bbs.pfan.cn/post/4883.html

回复列表 （共8个回复）

沙发

lanjingquan [专家分：510] 发布于 2002-11-15 21:24:00

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

#include <iostream.h>

#include "tree.h"
#include "comm.h"
template <class TElem>
TBinTree<TElem>::TBinTree()
{
root=NULL;
numNodes=0;
}

template <class TElem>
TBinTree<TElem>::~TBinTree()
{
ReleaseSubs(root);
}

template <class TElem>
long TBinTree<TElem>::ReleaseSubs(TBinTreeNode0<TElem> *pRoot)
{
long cnt=0;

if (pRoot->GetSon(1)==NULL && pRoot->GetSon(2)==NULL)
{
  delete pRoot;
  return 1;
}
if (pRoot->GetSon(1)!=NULL) cnt=ReleaseSubs(pRoot->GetSon(1));
else cnt=ReleaseSubs(pRoot->GetSon(2));

delete pRoot;
return cnt+1;

}

template <class TElem>
long TBinTree<TElem>::GetLevel(TBinTreeNode0<TElem> *pRoot)
{
if (pRoot==NULL) return 0;
return GetLevel(pRoot->GetFather())+1;

}

template <class TElem>
long TBinTree<TElem>::GetHeight(TBinTreeNode0<TElem> *pRoot)
{
long m1, m2;

if (pRoot==NULL) return 0;
m1 = GetHeight(pRoot->GetSon(1));
m2 = GetHeight(pRoot->GetSon(2));
if (m1>m2) return m1+1;
else return m2+1;
}

template <class TElem>
long TBinTree<TElem>::GetNumSubNodes(TBinTreeNode0<TElem> *pRoot)
{
long m1, m2;

if (pRoot==NULL) return 0;
m1 = GetNumSubNodes(pRoot->GetSon(1));
m2 = GetNumSubNodes(pRoot->GetSon(2));
return m1+m2+1;
}

template <class TElem>
long TBinTree<TElem>::GetNumSubNodes(void)
{
return numNodes;
}

template <class TElem>
long TBinTree<TElem>::GetNumLeaves(TBinTreeNode0<TElem> *pRoot)
{
long m1, m2;

if (pRoot==NULL) return 0;
if (pRoot->IsLeaf()) return 1;
m1 = GetNumLeaves(pRoot->GetSon(1));
m2 = GetNumLeaves(pRoot->GetSon(2));
return m1+m2;
}

template <class TElem>
long TBinTree<TElem>::Cluster(TBinTreeNode0<TElem>* pNode, TElem ** e,TTraverseMode tm)
{
static long cnt=0;

if (pNode==NULL) return 0;

switch (tm)
{
  case PreOrder:
    e[cnt++]=&(pNode->GetElem());
    Cluster(pNode->GetSon(1), e,tm);
    Cluster(pNode->GetSon(2), e,tm);
    return cnt;

  case InOrder:
    Cluster(pNode->GetSon(1), e,tm);
    e[cnt++]=&(pNode->GetElem());
    Cluster(pNode->GetSon(2), e,tm);
    return cnt;

  case PostOrder:
    Cluster(pNode->GetSon(1), e,tm);
    Cluster(pNode->GetSon(2), e,tm);
    e[cnt++]=&(pNode->GetElem());
    return cnt;
}
return 0;
}

template <class TElem>
long TBinTree<TElem>::Cluster(TBinTreeNode0<TElem>* pNode, TBinTreeNode0<TElem> **pNodes,TTraverseMode tm)
{
static long cnt=0;

if (pNode==NULL) return 0;

switch (tm)
{
  case PreOrder:
    pNodes[cnt++]=pNode;
    Cluster(pNode->GetSon(1), pNodes,tm);
    Cluster(pNode->GetSon(2), pNodes,tm);
    return cnt;

  case InOrder:
    Cluster(pNode->GetSon(1), pNodes,tm);
    pNodes[cnt++]=pNode;
    Cluster(pNode->GetSon(2), pNodes,tm);
    return cnt;

  case PostOrder:
    Cluster(pNode->GetSon(1), pNodes,tm);
    Cluster(pNode->GetSon(2), pNodes,tm);
    pNodes[cnt++]=pNode;
    return cnt;
}
return 0;
}

template <class TElem>
long TBinTree<TElem>::Cluster2(TBinTreeNode0<TElem>* pNode, TBinTreeNode0<TElem> **pNodes,TTraverseMode tm)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>** sk;
TBinTreeNode<TElem>* p;

nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;

switch (tm)
{
  case PreOrder:

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

    p  =(TBinTreeNode<TElem> *) pNode;
    while (p!=NULL || top!=0)
    {
     if (p!=NULL)
     {
      pNodes[cnt++]= p;
       top++; sk[top]=p;
      p = (TBinTreeNode<TElem> *)p->GetSon(1);
     }
     else
     {
      p = sk[top]; top--;
      p = (TBinTreeNode<TElem> *)p->GetSon(2);
     }
    } //while
    delete[] sk;
    break;

  case InOrder:
    sk =new TBinTreeNode<TElem> *[nNodes+1];
    if (sk==NULL) throw TExcepComm(3);

    p  =(TBinTreeNode<TElem> *) pNode;
    while (p!=NULL || top!=0)
    {
     if (p!=NULL)
     {
      top++; sk[top]=p;
      p = (TBinTreeNode<TElem> *)p->GetSon(1);
     }
     else
     {
      p = sk[top]; top--;
      pNodes[cnt++]= p;
      p = (TBinTreeNode<TElem> *)p->GetSon(2);
     }
    } //while
    delete[] sk;
    break;

  case PostOrder:
    if (pNode==NULL) return 0;

    struct TPostTraverseStackNode
    {
      TBinTreeNode<TElem> *pNode;
      char isFirst;
    } ;

    TPostTraverseStackNode *sk2;

    sk2 =new TPostTraverseStackNode [nNodes+1];
    if (sk2==NULL) throw TExcepComm(3);

    p  =(TBinTreeNode<TElem> *) pNode;
    while (p!=NULL || top!=0)
    {
     if (p!=NULL)
     {
      top++;
      sk2[top].pNode=p;
      sk2[top].isFirst = 1;
      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--;
      pNodes[cnt++]= p;
      p=NULL;
     }
    } //while
  delete [] sk2;
  break;
}

return cnt;
}

template <class TElem>
long TBinTree<TElem>::ClusterDescendants(TBinTreeNode0<TElem>* pNode,
 TBinTreeNode0<TElem>** pNodes,
 TTraverseMode tm,
 int startLevel,
 int endLevel)
{
long cnt=0, levelNo=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>* p;

nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;

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

TTraverseStackNode *sk2;

sk2 =new TTraverseStackNode [nNodes+1];
if (sk2==NULL) throw TExcepComm(3);

if (startLevel<0) startLevel = nNodes+startLevel+1;
if (endLevel<0) endLevel = nNodes+endLevel+1;

switch (tm)
{
  case PreOrder:

    levelNo=1;
    p  =(TBinTreeNode<TElem> *) pNode;
    while (p!=NULL || top!=0)
    {
     if (p!=NULL)
     {
      top++;
      sk2[top].pNode=p;
      sk2[top].levelNo=levelNo;
      if (levelNo>=startLevel && levelNo<=endLevel)
         pNodes[cnt++]= p;
      p = (TBinTreeNode<TElem> *)p->GetSon(1);
      if (p!=NULL)  levelNo++;
     }
     else
     {
      p = sk2[top].pNode;
      levelNo=sk2[top].levelNo;
      top--;
      p = (TBinTreeNode<TElem> *)p->GetSon(2);
      if (p!=NULL) levelNo++;
     }
    } //while
    delete[] sk2;
    break;

  case InOrder:

    levelNo=1;
    p  =(TBinTreeNode<TElem> *) pNode;
    while (p!=NULL || top!=0)
    {
     if (p!=NULL)
     {
      top++;
      sk2[top].pNode=p;
      sk2[top].levelNo=levelNo;
      p = (TBinTreeNode<TElem> *)p->GetSon(1);
      if (p!=NULL)  levelNo++;
     }
     else
     {
      p = sk2[top].pNode;
      levelNo=sk2[top].levelNo;
      top--;
      if (levelNo>=startLevel && levelNo<=endLevel)
        pNodes[cnt++]= p;
      p = (TBinTreeNode<TElem> *)p->GetSon(2);
      if (p!=NULL) levelNo++;
     }
    } //while
    delete[] sk2;
    break;

  case PostOrder:

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

  delete[] sk2;
  break;
}

return cnt;
}


template <class TElem>
long TBinTree<TElem>::ClusterAncestors(TElem &e, 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->GetElem()==e) 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[i].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[i].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[i].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>::DeleteSubTree(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>::Locate(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>::InPreToTree(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[i]]);
s[++top] = p;
do
{
  i++;
  if (gListExp[i]=='(') continue;
  if (gListExp[i]==',' || gListExp[i]==')') top--;
  else
  {
   if (gListExp[i]=='*') p = NULL;
   else
   {
    p = new TBinTreeNode<TElem>;
    if (p==NULL)
    {
     delete [] s;
     throw TExcepComm(3);
    }
    p->SetElem(&es[gListExp[i]]);
   }

   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>::PreOrderExToTree(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[i]==-1)  p=NULL;
  else
  {
   p = new TBinTreeNode<TElem>;
   if (p==NULL) goto ClearUp;

   p->SetElem(&nodes[i]);
  }
  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>::PreOrderExToTree(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>::Print(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 Cluster:PostOrder";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<*es[i];
  }

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

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

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

  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[i]->GetElem()<<":"<<t1.GetLevel(pNodes[i]);
  }
  n=t1.ClusterSeniors(p, (TBinTreeNode0<int> **)pNodes, PreOrder, 1, 2);
  cout<<"\n Cluster:Seniors:";
  for (i=0; i<n; i++)
  {
   cout<<"  "<<pNodes[i]->GetElem()<<":"<<t1.GetLevel(pNodes[i]);
  }

  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[i]>=0 && nodes[i]<=9)
     printf(" %d", (char)nodes[i]);
   else printf(" %c", (char)nodes[i]);
  }

  getchar();
}

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

板凳

lanjingquan [专家分：510] 发布于 2002-11-15 21:26:00

具体方面可能有不同，不过思想应该差不多，你自己看看

3 楼

Totao [专家分：30] 发布于 2002-11-16 10:48:00

TOTAO万分感激上边那位高手~!~!需不能以身.....~!但还能请你吃糖可以吗? :)

4 楼

liminggg1218 [专家分：0] 发布于 2002-11-18 17:53:00

哇，果然是高手高手高高手  在下的景仰之情犹如滔滔江水，延绵不绝，又有如黄河泛滥，一发不可收拾................................

不过，呵呵，不过能不能有更简单一点的方法呀，小虾我实在是............

5 楼

Totao [专家分：30] 发布于 2002-11-23 16:08:00

你看不名白就是你的事咯....

6 楼

海纳百串 [专家分：0] 发布于 2004-05-12 17:34:00

#include "stdio.h"
#include "malloc.h"
typedef struct node    /*定义节点*/
{
char data;
struct node *lchild;
struct node *rchild;
}*btree;
btree jiantree()   /*建立树，采用先续遍立原理*/
{
char sk;
btree q,p,t,stack[30];
int top=0;
q=p=malloc(sizeof(struct node));
scanf("%c",&sk);
p->data=sk;
while((top>=0)||(p->data!=' '))
{
while(top==30)
{
printf("over\n");
return;
}
while(p->data!=' ')
{
stack[top++]=p;
t=malloc(sizeof(struct node));
p->lchild=t;
p=t;
scanf("%c",&sk);
p->data=sk;
}
if(p->data==' ')
{
p=stack[--top];
t=malloc(sizeof(struct node));
p->rchild=t;
p=t;
scanf("%c",&sk);
p->data=sk;
}
}
return (q);
}
void xx(btree BT)    /*先续遍历*/
{
btree stack1[30];
btree p;
int top=0;
p=BT;
while((p->data!=' ')||(top!=0))
{
while(p->data!=' ')
{if(top==30) printf("over\n");
stack1[top++]=p;
printf("%c",p->data);
p=p->lchild;
}
if(top!=0)
{
p=stack1[--top];
p=p->rchild;
}
}
printf("\n");
}
void zx(btree bt1)   /*中续遍历*/
{
btree stack2[30],p;
int top=0;
p=bt1;
while((p->data!=' ')||(top!=0))
{
while(p->data!=' ')
{
stack2[top++]=p;
p=p->lchild;
}
if(top!=0)
{p=stack2[--top];
printf("%c",p->data);
p=p->rchild;
}
}
printf("\n");
}
main()
{
btree head;
head=jiantree();
xx(head);
zx(head);
}

7 楼

andywang522 [专家分：10] 发布于 2004-05-12 21:25:00

程序写的不错,是这样的,上面那位写了那么多,怎么连数据结构都没有啊,不过仁兄好像英文太菜了,要不怎么连中序函数都不知道啊

8 楼

liangvictor [专家分：150] 发布于 2005-05-13 13:16:00

//创建二叉树函数
Status CreateBiTree(BiTree &T){
    char ch;
    if((ch=getchar())==' ')  T=NULL;
    else{
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        T->data=ch;
        CreateBiTree(T->lchild);  //创建左子树
        CreateBiTree(T->rchild);  //创建右子树
    }
    return OK;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

程序员工具箱 new

  • 更多工具

    • 代码片段

  • 模拟键盘（不可按）
  • 碰撞的唐三
  • 精彩奥运热点赛事的实时采集
  • 获取天气动态信息
  • 文件查找
  • python大数据抓取京东电脑销量数据
  • 爬虫技术不仅仅支持数据采集
  • 抓取脉脉APP上的职业信息
  • 爬虫中多线程的运用
  • 四则运算以及一元二次方程
  • 欢迎来共享你的NB代码

    • 本版新帖

  • 以前写的一个String类
  • 产生哈夫曼编码的源代码
  • 两极大数运算，源程序示例
  • 冰玉的原代码在这里，主要参考《电脑爱好者》及《c游戏编程从入门到精通》，没有时间，你可以参考！哈哈。
  • 那位高手指教如何用Turbo c调用.pcx图象文件
  • 24点中的不可能组合
  • 求任意多个整数的公倍数
  • 算24点全集之程序
  • TURBO C 2.0的汉化文件！
  • 10点半游戏
  • 高手心得（转载）！
  • 有没人会二叉树的生成啊?????十万火急
  • 广义表类
  • 树类
  • 一些有关递归回溯的程序