/* 二叉链表就是以链表为存储结构存储二叉树 ,我么要像编号 完全二叉树一样 存储 普通的二叉树 。 节点的声明如下 node     */ #include <iostream> using namespace std ; typedef struct node {   int data ;  node* lChild ;  node* rChild ; }BTreeNode,*LinkTree ;   

void CreateTree(LinkTree*pTree,int nIndex[],char ch[])   //nIndex是二叉树的节点编号数组  ch是节点数据 每个编号对应一个字符  nIndex 等于0时候结束   ch='#'结束 {   int   i =1 ;//用作下标   int   j ;//当前双亲节点的下标   LinkTree temNode[50] ;//辅助建立二叉链表  BTreeNode *newNode =NULL;//用来指向新分配的节点空间  while(nIndex[i]!=0&&ch[i]!='#')  //如果没有到达最后一个节点  {   newNode=new BTreeNode ;   newNode->data=ch[i]  ;  //为节点赋值   newNode->lChild=newNode->rChild=NULL ;//lChild=rChild=NULL   temNode[nIndex[i]]=newNode ;//将这个新节点保存在辅助节点数组的指定编号为下标的元素中。   if(nIndex[i]==1)  //如果是根节点的话那么我们将这个节点的地址保存在pTree中。   {    *pTree=newNode  ;   }   else   {       j=nIndex[i]/2 ;//获得双亲节点的编号 也就是数组下标    if(nIndex[i]%2==0)       temNode[j]->lChild=newNode ;  //编号基数那么是左子树    else     temNode[j]->rChild=newNode ;  //编号是偶数那么是右子树   }      i++ ;   //索引自加1  }   } void Preorder(LinkTree pTree)  //递归方式实现先序遍历 {     if(pTree!=NULL)  {   cout<<pTree->data<<" " ;   Preorder(pTree->lChild) ;   Preorder(pTree->rChild) ;  }   } void Inorder(LinkTree pTree) //中序遍历 {     if(pTree!=NULL)  {   Inorder(pTree->lChild) ;   cout<<pTree->data<<" " ;   Inorder(pTree->rChild) ;  }   } void Postorder(LinkTree pTree) //后序遍历 {  if(pTree!=NULL)  {   Postorder(pTree->lChild) ;   Postorder(pTree->rChild) ;   cout<<pTree->data<<" ";  } }

void Postorder(LinkTree pTree) //后序遍历 {  if(pTree!=NULL)  {   Postorder(pTree->lChild) ;   Postorder(pTree->rChild) ;   cout<<pTree->data<<" ";  } } 

/*     按照层次进行遍历 需要用到队列     循环队列  思想是把所有的节点进队列  进入队列的节点输出data  然后将这个节点的lChild rChild 不为NULL的孩子节点进入队列 。  进行一个 Rear!=Front的while循环 */ void  Traverse(BTreeNode*pTree) {    BTreeNode* queue[MAX_SIZE] ;   //指针队列数组保存遍历过的节点的指针    BTreeNode*tem=NULL; //临时指针保存出队列的节点    int Front = 0;    int Rear  = 0;    if(pTree!=NULL)  //初始化队尾为树的第一个节点    {    Rear=(Rear+1)%MAX_SIZE;     //队尾+1    queue[Rear]=pTree ;  //节点指针进队尾    }    while(Rear!=Front)    {        Front=(Front+1)%MAX_SIZE ;     tem=queue[Front] ;     cout<<tem->data<<" " ;     if(tem->lChild!=NULL)  //如果出队列的lChild不为空的话 那么进队列     {       Rear=(Rear+1)%MAX_SIZE ;  //lChild进队列      queue[Rear]=tem->lChild ;

    }     if(tem->rChild!=NULL ) //如果出队列的节点的rChild不为空的话 那么进队列     {

           Rear=(Rear+1)%MAX_SIZE ;  //rChild进队列      queue[Rear]=tem->rChild;     }    

   }  

}

void main() {     LinkTree pTree ;     int  nIndex[]={9999,1,2,3,4,5,6,7,8,9,0} ;        char ch[]={'?',1,2,3,4,5,6,7,8,9,'#'};     CreateTree(&pTree,nIndex,ch);     cout<<"先序遍历结果:"<<endl ;     Preorder(pTree) ;     cout<<endl ;     cout<<"中序遍历结果:"<<endl ;     Inorder(pTree) ;     cout<<endl ;     cout<<"后续遍历结果:"<<endl ;        Postorder(pTree) ;     cout<<endl ;

ClearTree(&pTree) ;

}