二叉樹的存儲結構

順序存儲結構

二叉樹的順序存儲結構是指用一組地址連續的存儲單元依次自上而下、從左到右存儲完全二叉樹上的結點，即將完全二叉樹上編號為 i 的結點存儲在數組下標為 i?1的數組分量中，然后通過一定方式確定結點在邏輯上的父子或兄弟關系。
???
空間浪費比較大

鏈式存儲結構

二叉樹每個結點最多兩個孩子，所以設計二叉樹的結點結構時考慮兩個指針指向該結點的兩個孩子。

二叉樹結點結構：

typedef struct BiTNode{ElemType data; //定義數據域struct BiTNode *lchild, *rchild; //定義左、右指針 }BiTNode, *BiTree;

這種結構的鏈表由于有兩個指針，所以叫二叉鏈表
另外還可以增加指針指向該結點的雙親結點，那這時三個指針的鏈表就叫三叉鏈表

二叉樹的遍歷（遞歸）

遍歷，是指按照某條搜索路徑訪問樹中的每一個結點，使得每個結點均會被訪問一次，而且僅被訪問一次。

由二叉樹的遞歸定義可知，遍歷一棵二叉樹首先需要確定對根結點、左子樹和右子樹的訪問順序。常見的遍歷次序有先序遍歷 (NLR) 、中序遍歷 (LNR) 和后序遍歷 (LRN) 三種。

遞歸先序遍歷

若二叉樹為空，則不采取操作，否則：

訪問根結點；

先序遍歷左子樹；

先序遍歷右子樹。

對應的遞歸算法：

void PreOrder(BiTree T){if(T != NULL){visit(T); //訪問根結點PreOrder(T->lchild); //遞歸遍歷左子樹PreOrder(T->rchid); / /遞歸遍歷右子樹} }

遞歸中序遍歷

若二叉樹為空，則不進行操作，否則：

中序遍歷左子樹；

訪問根結點；

中序遍歷右子樹。

對應的遞歸算法：

void InOrder(BiTree T){if(T != NULL){InOrder(T->lchild); //遞歸訪問左子樹visit(T); //訪問根結點InOrder(T->rchild); //遞歸訪問右子樹} }

遞歸后序遍歷

若二叉樹為空，則不進行操作，否則：

后序遍歷左子樹；

后序遍歷右子樹；

訪問根結點。

對應的遞歸算法：

void PostOrder(BiTree T){if(T != NULL){PostOrder(T->lchild); //遞歸遍歷左子樹PostOrder(T->rchild); //遞歸遍歷右子樹visit(T); //訪問根結點} }

二叉樹的遍歷（非遞歸）

借助到棧

非遞歸先序遍歷

Void PreOrderTraverse(BiTree b){InitStack(S);BiTree p=b; //工作指針pwhile(p || !IsEmpty(S)){while(p){printf(“%c”,p->data); //先序先遍歷結點Push(S,p); //進棧保存p=p->lchild; //指向左孩子}if(!IsEmpty(S)){p=Pop(S); //出棧p=p->rchild; //指向右孩子}} }

例子：

過程： p指向A，打印A, A進棧， p指向B，打印B，B進棧， p指向D，打印D，D進棧 p指向NULL，棧不為空，彈出棧頂D，p指向D的右孩子G 打印G，G進棧， p指向NULL，棧不為空，彈出棧頂G， p指向NULL，棧不為空，彈出棧頂B， p指向NULL，棧不為空，彈出棧頂A， p指向C，打印C，C進棧， p指向E，打印E，E進棧 p指向NULL，棧不為空，彈出棧頂E p指向NULL,棧不為空，彈出棧頂C， p指向F，打印F，F進棧 p指向NULL，棧不為空，彈出棧頂F p指向NULL，棧空，結束 打印的序列為：A B D G C E F

非遞歸中序遍歷

Void PreOrderTraverse(BiTree b){InitStack(S);BiTree p=b; //工作指針pwhile(p || !IsEmpty(S)){while(p){ //中序先將結點進棧保存Push(S,p);p=p->lchild;}//遍歷到左下角盡頭再出棧訪問p=Pop(S);printf(“%c”,p->data);p=p->rchild; //遍歷右孩子} }

非遞歸后序遍歷

Void PostOrderTraverse(BiTree b){InitStack(S);BiTree p=b，r=NULL; //工作指針p 輔助指針rwhile(p || !IsEmpty(S)){//1.從根結點到最左下角的左子樹都入棧if(p){Push(S,p);p=p->lchild;}//2.返回棧頂的兩種情況else{GetTop(S,p); //取棧頂 注意不是出棧！//①右子樹還未訪問，而且右子樹不空，第一次棧頂if(p->rchild &&p->rchild !=r) p=p->rchild;//②右子樹已經訪問或為空，接下來出棧訪問結點else{Pop(S,p);printf(“%c”,p->data);r=p; //指向訪問過的右子樹根結點p=NULL; //使p為空從而繼續訪問棧頂}}} }

層序遍歷

如圖所示為二叉樹的層次遍歷，即按照箭頭所指方向，按照層次1，2，3，4的順序，橫向遍歷對二叉樹中的結點進行訪問。

進行層次遍歷需要借助隊列：先將二叉樹根結點入隊，然后出隊并訪問該結點，若有左子樹，則將左子樹根結點入隊；若有右子樹，則將右子樹根結點入隊。然后出隊并對出隊結點進行訪問，重復上述操作直到隊列為空。
思路：出隊→訪問→左右孩子入隊

二叉樹的層次遍歷算法：

void LevelOrder(BiTree T){InitQueue(Q); //創建空隊列 QBiTree p; //創建遍歷指針 pEnQueue(Q, T); //根結點入隊while(! IsEmpty Q){ //隊列非空則繼續循環進行遍歷DeQueue(Q, p); //隊頭元素出隊visit(p); //訪問出隊結點if(p->lchild != NULL) //若左子樹存在EnQueue(Q, p->Lchild); //左子樹根結點入隊if(p->child != NULL) //若右子樹存在EnQueue(Q, p->rchild); //右子樹根結點入隊} }

線索二叉樹

二叉鏈表表示的二叉樹存在大量空指針
N個結點的二叉鏈表，每個結點都有指向左右孩子的結點指針，所以一共有2N個指針，而N個結點的二叉樹一共有N-1條分支，也就是說存在2N-(N-1)=N+1個空指針。比如上圖二叉樹中有6個結點，那么就有7個空指針。

大量空余指針能否利用起來？

指向前驅和后繼的指針成為線索，加上線索的二叉鏈表就成為線索鏈表，相應的二叉樹被稱為線索二叉樹
對二叉樹以某種次序遍歷使其變為線索二叉樹的過程就叫做線索化

如何區分指針是指向左孩子還是前驅，或者指向右孩子還是后繼？

在二叉鏈表結點的結構基礎上增加兩個標志位ltag和rtag

typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; }ThreadNode,*ThreadTree; //線索鏈表 lchildltagdatartagrchild

ltag == 0 代表lchild指向該結點的左孩子
ltag ==1 代表lchild指向該結點的前驅

rtag == 0 代表rchild指向該結點的右孩子
rtag ==1 代表rchild指向該結點的后繼

void InThread(ThreadTree &p,ThreadTree &pre){ //中序遍歷對二叉樹線索化的遞歸算法if(p){InThread(p->lchild,pre);//修改前驅if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}//修改后繼if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;InThread(p->rchild,pre);} }

遍歷線索二叉樹

void InOrderTraverse(ThreadTree T){ThreadTree p=T；while(p){while(p->ltag==0)p=p->lchild;printf(“%c”,p->data);while(p->rtag==1&&p->rchild){p=p->rchild;printf(“%c”,p->data);}p=p->rchild;} }

參考資料

王道數據結構

總結

以上是生活随笔為你收集整理的【数据结构】二叉树的存储和遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。