二叉树的创建以及利用迭代实现中序、先序、后序遍历、清空

/*

二叉链表就是以链表为存储结构存储二叉树 ,我么要像编号 完全二叉树一样 存储 普通的二叉树 。

节点的声明如下 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) //中序遍历

  Inorder(pTree->lChild) ;

  Inorder(pTree->rChild) ;

void Postorder(LinkTree pTree) //后序遍历

{

  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 ;

       Postorder(pTree) ;

ClearTree(&pTree) ;