您當前位置：首頁 > 數據庫 > 數據庫應用 > 數據結構 - 二叉樹的存儲結構

數據結構 - 二叉樹的存儲結構

來源：程序員人生發布時間：2015-05-25 09:01:28 閱讀次數：2997次

順序存儲結構

2叉樹存儲結構的類型定義：

＃define MAX_SIZE  100
 typedef telemtype sqbitree[MAX_SIZE];

用1組地址連續的存儲單元順次“自上而下、自左至右”存儲完全2叉樹的數據元素。
對完全2叉樹上編號為i的結點元素存儲在1維數組的下標值為i⑴的份量中，如圖6⑹(c)所示。
對1般的2叉樹，將其每一個結點與完全2叉樹上的結點相對比，存儲在1維數組中，

鏈式存儲結構

設計不同的結點結構可構成不同的鏈式存儲結構。

(1) 結點的類型及其定義
① 2叉鏈表結點。有3個域：1個數據域，兩個分別指向左右子結點的指針域

typedef struct BTNode
{  ElemType  data ;
struct BTNode  *Lchild , *Rchild ;
}BTNode ;

② 3叉鏈表結點。除2叉鏈表的3個域外，再增加1個指針域，用來指向結點的父結點

typedef struct BTNode_3
{  ElemType  data ;
struct BTNode_3  *Lchild , *Rchild , *parent ;
}BTNode_3 ;

遍歷2叉樹(Traversing Binary Tree)

遍歷2叉樹(Traversing Binary Tree)：是指按指定的次序（規律）順次訪問2叉樹中所有結點，使得每一個結點被訪問1次且僅被訪問1次。
訪問：指對結點做某種處理。如：輸出信息、修改結點的值等。
次序（規律）：2叉樹是1種非線性結構，每一個結點都可能有左、右兩棵子樹，所以在訪問完1個結點以后，下1個被訪問的結點面臨著不同的選擇。因此，需要尋覓1種次序（規律），使2叉樹上的結點能排列在1個線性隊列上，從而便于遍歷。
2叉樹的基本組成：根結點、左子樹、右子樹。若能順次遍歷這3部份，就是遍歷了2叉樹。

若以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，則有6種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。
   若規定先左后右，則只有前3種情況3種情況，分別是：

DLR――先(根)序遍歷。
LDR――中(根)序遍歷。
LRD――后(根)序遍歷。
已知2叉樹，寫出先序序列、中序序列、后序序列
已知先序序列和中序序列，肯定2叉樹
已知后序序列和中序序列，肯定2叉樹

遍歷算法

對2叉樹的遍歷，分別討論遞歸遍歷算法和非遞歸遍歷算法。
遞歸遍歷算法具有非常清晰的結構，但初學者常常難以接受或懷疑，不敢使用。實際上，遞歸算法是由系統通過使用堆棧來實現控制的。
非遞歸算法中的控制是由設計者定義和使用堆棧來實現的。

先序遍歷2叉樹

1 遞歸算法
算法的遞歸定義是：
若2叉樹為空，則遍歷結束；否則
⑴ 訪問根結點；
⑵ 先序遍歷左子樹(遞歸調用本算法)；
⑶ 先序遍歷右子樹(遞歸調用本算法)。

先序遍歷的遞歸算法
void  PreorderTraverse(BTNode  *T)
     {    if  (T==NULL) 
                return;
    visit(T->data) ;       /*  訪問根結點  */
PreorderTraverse(T->Lchild) ; //再先序遍歷左子樹
PreorderTraverse(T->Rchild) ; //再先序遍歷右子樹
}
說明：1、visit()函數是訪問結點的數據域，其要求視具體問題而定,可以是最簡單的打印輸出。
      2、樹采取2叉鏈表的存儲結構，用指針變量T來指向。

2 非遞歸算法
設T是指向2叉樹根結點的指針變量，非遞歸算法是：
若2叉樹為空，則返回；否則，令p=T；
⑴ 訪問p所指向的結點；
⑵ q=p->Rchild ，若q不為空，則q進棧；
⑶ p=p->Lchild ，若p不為空，轉(1)，否則轉(4)；
⑷ 退棧到p ，轉(1)，直到棧空為止。
算法實現：

#define  MAX_STACK_SIZE  50
void  PreorderTraverse( BTNode  *T)
{  BTNode  *Stack[MAX_STACK_SIZE ] ,*p=T, *q ;
int  top=0 ;
if  (T==NULL)  printf(“ Binary Tree is Empty!
”) ;
else {  do
      {  visit( p-> data ) ;   q=p->Rchild ; 
          if  ( q!=NULL )  stack[top++]=q ;
          p=p->Lchild ; 
          if (p==NULL&& top!=0) 
             {top-- ；p=stack[top] ; }
      }
   while (p!=NULL) ;
}
}