您當(dāng)前位置：首頁 > 數(shù)據(jù)庫 > 數(shù)據(jù)庫應(yīng)用 > 數(shù)據(jù)結(jié)構(gòu) - 二叉樹的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu) - 二叉樹的存儲(chǔ)結(jié)構(gòu)

來源：程序員人生發(fā)布時(shí)間：2015-05-25 09:01:28 閱讀次數(shù)：2988次

順序存儲(chǔ)結(jié)構(gòu)

2叉樹存儲(chǔ)結(jié)構(gòu)的類型定義：

＃define MAX_SIZE  100
 typedef telemtype sqbitree[MAX_SIZE];

用1組地址連續(xù)的存儲(chǔ)單元順次“自上而下、自左至右”存儲(chǔ)完全2叉樹的數(shù)據(jù)元素。
對(duì)完全2叉樹上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在1維數(shù)組的下標(biāo)值為i⑴的份量中，如圖6⑹(c)所示。
對(duì)1般的2叉樹，將其每一個(gè)結(jié)點(diǎn)與完全2叉樹上的結(jié)點(diǎn)相對(duì)比，存儲(chǔ)在1維數(shù)組中，

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

(1) 結(jié)點(diǎn)的類型及其定義
① 2叉鏈表結(jié)點(diǎn)。有3個(gè)域：1個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域

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

② 3叉鏈表結(jié)點(diǎn)。除2叉鏈表的3個(gè)域外，再增加1個(gè)指針域，用來指向結(jié)點(diǎn)的父結(jié)點(diǎn)

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

遍歷2叉樹(Traversing Binary Tree)

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

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

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

遍歷算法

對(duì)2叉樹的遍歷，分別討論遞歸遍歷算法和非遞歸遍歷算法。
遞歸遍歷算法具有非常清晰的結(jié)構(gòu)，但初學(xué)者常常難以接受或懷疑，不敢使用。實(shí)際上，遞歸算法是由系統(tǒng)通過使用堆棧來實(shí)現(xiàn)控制的。
非遞歸算法中的控制是由設(shè)計(jì)者定義和使用堆棧來實(shí)現(xiàn)的。

先序遍歷2叉樹

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

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

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

#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) ;
}
}