二叉樹的遞歸、非遞歸、線索化、層序周遊

周遊的思路

1. 遞歸周遊（先序、中序、後序）
2. 利用棧實作非遞歸（先序、中序、後序）
3. 二叉樹的線索化（中序）
4. 層序周遊

遞歸周遊

遞歸代碼簡潔，下列出先序遞歸

void preorder(bitnode *t)
{
 if(t)
 {
  printf("%d ",t->ch);
  preorder(t->lchild);
  preorder(t->rchild);
 }
 else
 return ;
}
           

中序與後序類似，不再贅述

棧結構實作非遞歸周遊

三種周遊的周遊路徑都相同，隻是通路的順序不同

（一）先序周遊

思路：

1.周遊輸出左子結點，并入棧。（通路根，并周遊通路左子結點）

2.節點彈出棧，轉向周遊每個彈出節點的右子結點（回溯周遊右子結點）

void preorder2(bitnode *t)
{
 seqstack s;
 s.top=0;//初始化棧
 while(s.top||t)
 {
  while(t) //輸出根結點并周遊輸出左子樹
  {
   printf("%d ",t->ch);
   pushstack(&s,t);
   t=t->lchild;
  }
  if(s.top)//回溯通路右子樹
  {
   t=popstack(&s);
   t=t->rchild;
  }
 }
}
           

（二）中序周遊

思路：

1.周遊左子結點，并入棧。（周遊左子結點）

2.節點彈出棧并通路，轉向周遊每個彈出節點的右子結點（通路左結點，并回溯 周遊根和右子樹）

void inorder2(bitnode *t)
 {
  seqstack s;
  s.top=0;
  while(s.top||t)
  {
   while(t)
   {
    pushstack(&s,t);
    t=t->lchild;
   }
   if(s.top)
   {
    t=popstack(&s);
    printf("%c ",t->data);  
    t=t->rchild;
   }
  }
 }
           

（三）後序周遊

注意要記錄通路過的右節點。

思路：

1.周遊左子結點，并入棧。（周遊左子結點）

2.節點彈出棧并通路，轉向周遊每個彈出節點的右子樹（通路左結點，并回溯通路右子樹）

細節：周遊右子樹，若右子結點已通路，通路根結點，否則，遞歸通路右結點

void postorder2(bitnode *t)
{
 bitnode *q;  //标記已通路 
 seqstack s;
 s.top=0;
 while(s.top||t)
 {
  while(t)
  {
   pushstack(&s,t);
   t=t->lchild;
  }
  if(s.top)
  {
   t=popstack(&s);
   if(t->rchild==NULL || t->rchild==q) //如果是 無右節點節點 或  右子節點已經通路過 
   {
    q=t;
    printf("%d ",t->data);
    t=NULL;
   }
   else  //周遊到無右節點為止 
   t=t->rchild;
  }
 }
 } 
           

線索二叉樹（中序）

二叉樹複雜的非線性結構在周遊時難以确定前驅和後繼結點。

n個結點的二叉樹有n+1個空指針，将這些空指針域來存放前驅或後繼結點來實作線索化，便于周遊。

typedef struct TREE
{
 int data;
 int ltag,rtag;
 struct TREE *lchild,*rchild;
}bitnode;
           

線索化的

1. 建立一個root節點（友善我們循環周遊）

   root 結構如下

root=(bitnode*)malloc(sizeof(bitnode));
 root->ltag=0; //左子結點為根節點
 root->rtag=1; 
 if(!t)
 root->lchild=root;
 else
 {
  root->lchild=t;
 }
 pre=root; 
 inthread(t); 
 pre->rchild = root;
 root->rtag=1;
 root->rchild=pre;
           

1. 在中序周遊的過程中線索化

   我們使用 pre 與 p 指針進行周遊，隻能擷取 前驅結點 和 目前結點 的資訊。

   （1）前驅線索化：p->lchild = pre;

   （2）後繼線索化：pre->rchild = p;(即後繼線索要延遲到下一次線索化的過程)

   線索化代碼如下

void inthread(bitnode *p)  //更新 *p 
{
 if(p)
 {
//在左子樹周遊過程中線索化
  inthread(p->lchild);        //左子樹線索化 
//根結點線索化
  if(p->lchild==NULL)         //前驅線索化 
  {
   p->ltag=1;
   p->lchild = pre; 
  }
  if(pre->rchild==NULL)      //後繼線索化 
  {
   pre->rtag = 1;
   pre->rchild = p;
  }
  pre = p;                 //更新 *pre 
//在右子樹周遊過程中線索化  
  inthread(p->rchild);    //右子樹線索化 
 }
}
           

線索化過程的注意點

（1）. root結點的定義

（2）. pre為全局變量

（3）. 線索化過程類似于遞歸中序周遊二叉樹，隻是将通路的過程改為了線索化的過程

（4）.注意前驅化在目前疊代過程，而後繼化在下一個疊代過程。（了解這個便于我們判斷 p 和 pre 指針的位置）

線索化之後便于我們查找下一個結點和上一個結點

層序周遊

使用隊列的資料結構來實作層序周遊

代碼如下

void levelorder(bitnode *t)
{
 seqque q;
 bitnode *pre,*p;
 q.flag=0;
 q.front=q.rear=0;
 enqueue(&q,t);
 while(q.front!=q.rear||q.flag!=0)
//如果t有左右孩子節點，t出隊，左右孩子節點入隊列。否則，t出隊 
 {
  t=dequeue(&q);
  printf("%d ",t->data);
  if(t->lchild)
  enqueue(&q,t->lchild);
  if(t->rchild)
  enqueue(&q,t->rchild);
 }
}