編程中的樹的遍歷分為哪三種類型

A. 擴展先序遍歷序列擴展先序遍歷序列

在大學計算機基礎課程《數據結構與演算法 C語言描述》中，擴展先序遍歷序列是一個重要的知識點。它主要針對二叉樹的結構進行講解。二叉樹的遍歷方式有先序遍歷、中序遍歷和後序遍歷，對於每一個二叉樹，這三種遍歷方式分別得到的序列是唯一且對應的，它們能准確地反映出樹的結構信息。

然而，當我們需要在編程中直觀且高效地構建二叉樹時，層次遍歷和擴展先序遍歷就顯得尤為重要。層次遍歷，也稱為廣度優先遍歷，按照從上到下、從左到右的順序訪問二叉樹的節點，這種方式有助於我們理解樹的層次結構。而擴展先序遍歷則是先序遍歷的變種，它在序列中不僅包含根節點，還額外包含了根節點的子節點的先序遍歷序列，這種形式更便於我們在程序中構建出完整的二叉樹結構。

通過擴展先序遍歷，我們可以明確地按照特定順序排列節點，這對於理解和構建復雜二叉樹模型非常有幫助。總結來說，擴展先序遍歷序列是理解二叉樹遍歷和構建的有效工具，它結合了先序遍歷的直觀性和層次遍歷的高效性，是數據結構學習中的重要組成部分。

B. 什麼是二叉樹

二叉樹

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

二叉樹的每個結點至多隻有二棵子樹毀首好(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為log2n+1。深度為k的完全二叉樹，至少有2^（k-1)個節點，至多有2^k-1個節點。

一、定義

二叉樹在圖論中是這樣定義的：二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

二、基本概念

二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：

(1)空二叉樹——如圖(a)；

線索二叉樹的存儲結構

在中序線索樹找結點後繼的規律是：若其右標志為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標志為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。

在後序線索樹中找到結點的後繼分三種情況：

若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

數據結構定義為：

/*二叉線索存儲表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指針，Thread(1)：線索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指針*/PointerTag LTag,RTag;/* 左右標志 */}BiThrNode,*BiThrTree;

八、實現演示

範例二叉樹：

A

B C

D E

此樹的順序結構為：ABCD##E

intmain()
{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置.

intmain()

{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置。

voidcreat(node*p,stringstr,intr)

{

p->data=str[r];

if(str[r*2+1]=='#'||r*2+1>str.size()-1)p->lch=NULL;

else

{

p->lch=newnode;

creat(p->lch,str,r*2+1);

}

if(str[r*2+2]=='#'||r*2+2>str.size()-1)p->rch=NULL;

else

{

p->rch=newnode;

creat(p->rch,str,r*2+2);

}

}