二叉樹的建立以及利用疊代實作中序、先序、後序周遊、清空

/*

二叉連結清單就是以連結清單為存儲結構存儲二叉樹 ,我麼要像編号 完全二叉樹一樣 存儲 普通的二叉樹 。

節點的聲明如下 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) ;