~~~ /* 二叉链表就是以链表为存储结构存储二叉树 ,我么要像编号 完全二叉树一样 存储 普通的二叉树 。 节点的声明如下 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) ; } ~~~