計算機網路實驗一層二叉樹

㈠ 將一棵有100個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1

編號為49的結點的左孩子編號為98，公式是2i，不是2i+1。

舉個簡單的例子就可以看出來的，比如7個節點時（也就是三層時），編號為1的左子樹編號是2，編號2的左子樹是4，編號3的左子樹編號為6，以此就可以看出來。

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同。

演算法思路

判斷一棵樹是否旦蔽是完全二叉敗敏樹的思路

如果樹為空，則直接返回錯

如果樹不為空：層序遍歷二叉樹

如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列；

如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；

以上內容參考：網路-完察遲枝全二叉樹

㈡ 假設一棵二叉樹的層次次序（按層次遞增順序排列，同 一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。

【答案】按液叢層次遍歷，第羨讓一個結點（若樹不空）為根，該
結點在中序序列中把序列分成左右兩部分：左子樹和右子
樹。若左子樹不空，層次序列中第二個結點為左子樹的根
；若右子樹為空，則層次序列中第三個結點為右子樹的根
。對右子樹也作類似的分析。層次序列的特點是，從左到
右每個結點或是當前情況下子樹的根或是葉子鬧派櫻。

㈢ 在計算機程序中，二叉樹是一種表示數據結構的方法．如圖，-層二叉樹的結點總數為1；二層二叉樹的結點的總

根消圓據題意分析可得：第掘橋罩n層的二叉樹判鬧的結點總數為2ⁿ-1；故七層二叉樹的結點總數為2⁷-1=127．

㈣ 請教各位一下

二叉樹T是有限個結點的集合，它或者是空集，或者由一個根結點u以及分別稱為左子樹和右子樹的兩棵互不相交的二叉樹u(1)和u(2)組成。若用n,n1和n2分別表示T，u(1)和u(2)的結點數，則有n=1+n1+n2 。u(1)和u(2)有時分別稱為T的第一和第二子樹。

因此，二叉樹的根可以有空的左子樹或空的右子樹，或者左、右子樹均為空。

二叉樹有5種基本形態，如圖1所示。

圖1 二叉樹的5種基本形態(其中□表示空)

在二叉樹中，每個結點至多有兩個兒子，並且有左、右之分。因此任一結點的兒子不外4種情況：沒有兒子；只有一個左兒子；只有一個右兒子；有一個左兒子並且有一個右兒子。

--------------------------------------------------------------------------------

注意：二叉樹與樹和有序樹的區別

--------------------------------------------------------------------------------

二叉樹與度數不超過2的樹不同，與度數不超過2的有序樹也不同。在有序樹中，雖然一個結點的兒子之間是有左右次序的，但若該結點只有一個兒子時，就無須區分其左右次序。而在二叉樹中，即使是一個兒子也有左右之分。例如圖2中(a)和(b)是兩棵不同的二叉樹。雖然它們與圖3中的普通樹(作為無序樹或有序樹)很相似，但它們卻不能等同於這棵普通的樹。若將這3棵樹均看作是有序樹，則它們就是相同的了。

圖2 兩棵不同的二叉樹

圖3 一棵普通的樹

由此可見，盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

二叉樹的數學性質
二叉樹具有以下的重要性質：

高度為h≥0的二叉樹至少有h+1個結點；
高度不超過h(≥0)的二叉樹至多有2h+1-1個結點；
含有n≥1個結點的二叉樹的高度至多為n-1；
含有n≥1個結點的二叉樹的高度至少為logn，因此其高度為Ω(logn)。
具有n個結點的不同形態的二叉樹的數目在一些涉及二叉樹的平均情況復雜性分析中是很有用的。設Bn是含有n個結點的不同二叉樹的數目。由於二叉樹是遞歸地定義的，所以我們很自然地得到關於Bn的下面的遞歸方程：
(1)

即一棵具有n>1個結點的二叉樹可以看成是由一個根結點、一棵具有i個結點的左子樹和一棵具有n-i-1個結點的右子樹所組成。

(1)式的解是

(2)

即所謂的Catalan數。因此，當n=3時,B3=5。於是，含有3個結點的不同的二叉樹有5棵，如圖4所示。

圖4 含有3個結點的不同二叉樹

特殊形態的二叉樹
滿二叉樹和近似滿二叉樹是二叉樹的兩種特殊情形。

一棵高度為h≥0且有2h+1-1個結點的二叉樹稱為滿二叉樹。

若一棵二叉樹至多隻有最下面的兩層結點的度數小於2，並且最下面一念慧層結點都集中在該層的核凳最左邊，則稱這種二叉樹為近似滿二叉樹(有時也稱為完全二叉樹)。

(a) 滿二叉樹

(b) 近似滿二叉樹

(c) 非近似滿二叉樹

圖5 特殊形態的二叉樹

例如圖5(a)是一棵高度為3的滿二叉樹。滿二叉樹的特點是每一層上的結點數都達到最大值，即對給定的高度，它是具有最多結點數的二叉樹。滿二叉樹中不存在度仔氏答數為1的結點，每個分枝結點均有兩棵高度相同的子樹，且葉結點都在最下面一層上。圖5(b)是一棵近似滿二叉樹。顯然滿二叉樹是近似滿二叉樹，但近似滿二叉樹不一定是滿二叉樹。在滿二叉樹的最下層上，從最右結點開始連續往左刪去若干個結點後得到的二叉樹是一棵近似滿二叉樹。因此，在近似滿二叉樹中，若某個結點沒有左兒子，則它一定沒有右兒子，即該結點是一個葉結點。圖5(c)中，結點F沒有左兒子而有右兒子L，故它不是一棵近似滿二叉樹。

二叉樹的操作
二叉樹的常用操作與樹的常用操作相似。

運算 含義
Parent(v,T) 這是一個求父結點的函數，函數值為樹T中結點v的父親。當v是根結點時，函數值為∧，表示結點v沒有父結點。
Left_Child(v,T) 這是一個求左兒子結點的函數。函數值為樹T中結點v的左兒子。當結點v沒有左兒子時，函數值為∧。
Right_Child(v,T) 這是一個求右兒子結點的函數。函數值為樹T中結點v的右兒子。當結點v沒有右兒子時，函數值為∧。
Create(x,Left,Right,T) 這是一個建樹過程。該函數生成一棵新的二叉樹T，T的根結點v的標號為x，v的左右兒子分別為Left和Right。
Label(v,T) 這時一個求標號的函數，函數值就是結點v的標號。
Root(T) 這是一個求樹根的函數，函數值為樹T的根結點。當T是空樹時，函數值為∧。
MakeNull(T) 這是一個過程，它使T成為一棵空樹。

二叉樹的實現
我們已經看到，雖然二叉樹與樹很相似，但它卻不是樹的特殊情形。在許多情況下，使用二叉樹具有結構簡單，操作方便的優點。另外我們也看到，在樹的左兒子右兄弟表示法中，實際上已將一棵一般的樹轉化為一棵二叉樹。在更一般的情形，我們還可以將果園或森林轉化為一棵等價的二叉樹。下面我們來討論幾種二叉樹的表示方法。

二叉樹的順序存儲結構
此結構是將二叉樹的所有結點，按照一定的次序，存儲到一片連續的存儲單元中。因此，必須將結點排成一個適當的線性序列，使得結點在這個序列中的相應位置能反映出結點之間的邏輯關系。這種結構特別適用於近似滿二叉樹。

在一棵具有n個結點的近似滿二叉樹中，我們從樹根起，自上層到下層，逐層從左到右給所有結點編號，就能得到一個足以反映整個二叉樹結構的線性序列，如圖6所示。其中每個結點的編號就作為結點的名稱。

圖6 近似滿二叉樹的結點編號

因此，我們可以對樹的類型作如下說明：

TPosition=integer;

TreeType=record

NodeCount:integer;

NodeList:array [1..MaxNodeCount] of LabelType;

end;

將數組下標作為結點名稱(編號)，就可將二叉樹中所有結點的標號存儲在一維數組中。例如，圖6中的二叉樹的順序存儲結構如圖7所示。

圖7 近似滿二叉樹的順序存儲結構

在二叉樹的這種表示方式下，各結點之間的邏輯關系是隱含表示的。近似滿二叉樹中，除最下面一層外，各層都充滿了結點。可能除最底層外，每一層的結點個數恰好是上一層結點個數的2倍。因此，從一個結點的編號就可推知其父親，左、右兒子，和兄弟等結點的編號。例如，對於結點i我們有：

僅當i=1時，結點i為根結點；

當i>1時，結點i的父結點為i/2；

結點i的左兒子結點為2i；

結點i的右兒子結點為2i+1；

當i為奇數且不為1時，結點i的左兄弟結點為i-1；

當i為偶數時，結點i的右兄弟結點為i+1。

由上述關系可知，近似滿二叉樹中結點的層次關系足以反映結點之間的邏輯關系。因此，對近似滿二叉樹而言，順序存儲結構既簡單又節省存儲空間。

對於一般的二叉樹，採用順序存儲時，為了能用結點在數組中的位置來表示結點之間的邏輯關系，也必須按近似滿二叉樹的形式來存儲樹中的結點。顯然，這將造成存儲空間的浪費。在最壞情況下，一個只有k個結點的右單枝樹卻需要2k-1個結點的存儲空間。例如，只有3個結點的右單枝樹，如圖8(a)所示，添上一些實際不存在的虛結點後，成為一棵近似滿二叉樹，相應的順序存儲結構如圖8(b)所示。

圖8 一般二叉樹的順序存儲結構

下面我們就用這種順序存儲結構來實現二叉樹的常用操作。在這種表示法中，整數0表示空結點∧。對於非近似滿二叉樹，我們將其補為近似滿二叉樹，並規定一個特殊的標號&，用來表示補充的結點，&要根據標號的具體類型來確定。

順序存儲結構實現ADT二叉樹的操作

函數 Parent(v,T);

功能

這是一個求父結點的函數，函數值為樹T中結點v的父親。當v是根結點時，函數值為∧，表示結點v沒有父結點。

實現

Function Parent(v:TPosition;var T:TreeType):TPosition;

begin

return(v div 2);

end;

說明

根據這種表示法，我們知道，當i>1時，結點i的父結點為i/2。

復雜性

顯然為O(1)。

函數 Left_Child(v,T);

功能

這是一個求左兒子結點的函數。函數值為樹T中結點v的左兒子。當結點v沒有左兒子時，函數值為∧。

實現

Function Left_Child(v:TPosition;var T:TreeType):TPosition;

begin

if (2*v>T.NodeCount)or(T.NodeList[2*v]=&) then return(0)

else return(2*v);

end;

說明

如果結點v的左兒子存在，則其下標為2*v。

復雜性

顯然為O(1)。

函數 Right_Child(v,T);

功能

這是一個求右兒子結點的函數。函數值為樹T中結點v的右兒子。當結點v沒有右兒子時，函數值為∧。

實現

Procere Right_Child(v:TPosition;var T:TreeType):TPosition;

begin

if (2*v+1>T.NodeCount)or(T.NodeList[2*v+1]=&) then return(0)

else return(2*v+1);

end;

說明

如果結點v的左兒子存在，則其下標為2*v+1。

復雜性

顯然為O(1)。

函數 Create(x,Left,Right,T);

功能

這是一個建樹過程。該函數生成一棵新的二叉樹T，T的根結點標號為x，左右兒子分別為Left和Right。

實現

Procere Create(x:LabelType;var Left,Right,T:TreeType);

begin

T.NodeList[1]:=x;

T.NodeCount:=Left.NodeCount+Right.NodeCount+1;

h_left:=cal(Left.NodeCount);

h_right:=cal(Right.NodeCount);

if h_left>h_Right then h:=h_left else h:=h_right;

for i:=Left.NodeCount+1 to (1 shl (h+1))-1 do Left.NodeList[i]:=&；

Left.NodeCount:=(1 shl (h+1))-1;

if h_right<h then

begin

for i:=Right.NodeCount+1 to (1 shl h)-1 do Right.NodeList[i]:=&；

Right.NodeCount:=(1 shl h)-1;

end;

{=======

對於Left中編號為i的結點v，它在新樹T中的編號為2h +i，其中h=log2(i+1)-1 ；對於Right中編號為i的結點v，它在新樹T中的編號為2h+1+i，其中h=log2(i+1)-1 。

=======}

for i:=1 to Left.NodeCount do

T.NodeList[(1 shl cal(i))+i]:=Left.NodeList[i];

for i:=1 to Right.NodeCount do

T.NodeList[(1 shl (cal(i)+1))+i]:=Right.NodeList[i];

end;

其中cal(i)用來計算含有i個結點的近似滿二叉樹T的高度，cal(i)=log2(i+1)-1,可以實現如下：

Function cal(i:integer;):integer;

var

x:real;

begin

x:=log2(i+1)-1;

if x=int(x) then return(x) else return(int(x)+1);

end;

其中log2(n)計算實數n以2為底的對數。

說明

在順序存儲的結構下，建立一棵新的二叉樹的過程比較復雜。我們首先給出以下幾個命題：

命題一

一棵高度為h的滿二叉樹有2h+1-1個結點。

證明：

滿二叉樹的第i層有2i個結點，i=0,1,2,...,h(樹根為第0層)，因此高度為h的滿二叉樹有20+21+..+2h = 2h+1-1個結點。

推論一

我們從樹根起，自上層到下層，逐層從左到右給二叉樹的所有結點編號，如圖6所示，則近似滿二叉樹的第h層的從左到右第k個結點的編號為2h+k-1。

證明：

由於是近似滿二叉樹，所以第0層到第h-1層是滿二叉樹，根據命題一知道共有2h-1個結點，因此第h層的從左到右第1個結點的編號為2h-1+1，第h層的從左到右第k個結點的編號為2h-1+k。

推論二

一棵有n個結點的近似滿二叉樹，高度為log2(n+1)-1 ,其中 是天花板符號， x表示大於等於x的最小整數。

證明：

有n個結點的近似滿二叉樹，若其高度為h，則滿足2h-1<n≤2h+1-1,化簡得 log2(n+1)-1 ≤ h < [log2(n+1)-1]+1，即h=log2(n+1)-1。

推論三

在近似滿二叉樹T中，設編號為i的結點處於T的第h層從左到右第k個位置上，則h=log2(i+1)-1 ，k=i-(2h-1)。

證明：

我們先不考慮編號大於i的結點，則前i個結點構成一棵近似滿二叉樹，根據推論二知其層數為h=log2(i+1)-1 ，又因為第0層到第h-1層是滿二叉樹，根據命題一知道共有2h-1個結點，所以編號為i的結點處於第h層的第k=i-(2h-1)個位置上。

我們用T(h,k)表示樹T的第h層的第k個結點，則有下列命題：

命題二

Left(h,k)=T(h+1,k)，Right(h,k)=T(h+1,k+2h)，其中Left和Right分別是樹T的根結點的左右子樹。

證明：

顯然。

我們用N(v,T)表示結點v在生成的新樹T中的編號，則有下列命題：

命題三

對於Left中編號為i的結點v，N(v,T)=2h +i，其中h=log2(i+1)-1 ；對於Right中編號為i的結點v，N(v,T)=2h+1+i，其中h=log2(i+1)-1 。

證明：

㈤ 計算二叉樹指定結點p的層數(設樹根為第一層)

int level(struct node *t,struct node *p) {
return t ? _level(t, p, 1) : 0;
}

int __level(struct node *cur, struct node *goal, int depth) {
if (cur == NULL) return 0;
if (cur == goal) return depth;
int l = __level(cur->left, goal, depth + 1);
if (l > 0) return l;
int r = __level(cur->right, goal, depth + 1);
if (r > 0) return r;
return -1
}

㈥ 二叉樹有哪些基本特性

1、節點:

二叉樹中每個元素都稱為節點。

2、度:

二叉樹的度代表某個節點的孩子或者說直接後繼的個數，1度是只有一個孩子或者說單子樹。2度是兩個孩子或者說左右子樹都有的二叉樹最大度為2。

3、葉子:

葉子是葉子節點的簡稱。葉子也就是leaf指在網路結構中某些計算機，它們從比較靠近中心的計算機處接收信號，而不把信號傳送至較遠的計算機。葉子節點就是樹中最底段的節點，葉子節點沒有子節點。格式化葉子節點的結構比中間節點的結構稍微復雜一點。為了能夠在一個格式化葉子節點中保存多個條目。

(6)計算機網路實驗一層二叉樹擴展閱讀

二叉樹：

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

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

具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個節點，至多有2k-1個嘩森節點。

㈦ 什麼是二叉樹，舉一個二叉樹的例子

樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構拍核在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。樹結構的特點是：它的每一個結點都可以有不止一個直接後繼，除根結點外的所有結點都有且只有一個直接前趨。以下具體地給出樹的定義及樹的數據結構表示。樹是由一個或多個結點組成的有限集合，其中：⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。2.樹的深度——組成該樹各結點的最大層次，如上圖，其深度為4；3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；4.有序樹——指樹中同層結點從左到右有次序排襲凳掘列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如上圖可寫成如下形式：二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。(1)完全二叉樹——只有最下面的兩層結點度小於2，並且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹；(2)滿二叉樹——除了葉結點外每一個結點都有左右子女且葉結點都處在最底層的二叉樹,。(1) 在二叉樹中，粗滲第i層的結點總數不超過2^(i-1)；(2) 深度為h的二叉樹最多有2h-1個結點(h>=1)，最少有h個結點；(3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：若I為結點編號則 如果I<>1，則其父結點的編號為I/2；如果2*I<=N，則其左兒子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N，則其右兒子的結點編號為2*I+1；若2*I+1>N，則無右兒子。(2)鏈表存儲方式，如：5.普通樹轉換成二叉樹：凡是兄弟就用線連起來，然後去掉父親到兒子的連線，只留下父母到其第一個子女的連線。二叉樹很象一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把數據聯系起來，這種數據結構就叫做樹結構，簡稱樹。樹中每個分叉點稱為結點，起始結點稱為樹根，任意兩個結點間的連接關系稱為樹枝，結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親"，結點的後趨結點稱為該結點的"子女"或"孩子"，同一結點的"子女"之間互稱"兄弟"。二、二叉樹：二叉樹是一種十分重要的樹型結構。它的特點是，樹中的每個結點最多隻有兩棵子樹，即樹中任何結點的度數不得大於2。二叉樹的子樹有左右之分，而且，子樹的左右次序是重要的，即使在只有一棵子樹的情況下，也應分清是左子樹還是右子樹。定義：二叉樹是結點的有限集合，這個集合或是空的，或是由一個根結點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。對滿二叉樹，從第一層的結點(即根)開始，由下而上，由左及右，按順序結點編號，便得到滿二叉樹的一個順序表示。據此編號，完全二叉樹定義如下：一棵具有n個結點，深度為K的二叉樹，當且僅當所有結點對應於深度為K的滿二叉樹中編號由1至n的那些結點時，該二叉樹便是完全二叉樹。圖4是一棵完全二叉樹。遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。

㈧ 求二叉樹每一層的結點數 C++，代碼加解釋，求大神幫助

假設二叉樹不會大於100層，可以採用如下演算法實現。如果層次不限定建議使用鏈表來存儲。
主函數直接調用TraversalTree(&root, 0)即可其中root為二叉樹的根空蠢節點對象。
調用完後nMax表示最大層數，而currentFloor記錄每層的結點個數。
const int MAX 100
int nMax = 0;
int nNumArray[MAX] = {0};
void TraversalTree(TreeNode *root, int currentFloor)
{
if (null != root)
{
nNumArray[currentFloor]++; //子二叉樹的根結點存在因此本層增加結點數加1
if(nMax < currentFloor)
{
nMax = currentFloor + 1; //記錄當前樹的最大棚激層次,currentFloor 從0開始，因此需鏈虧襪要加1
}
}
else
{
return;
}
TraversalTree(root->left,currentFloor+1); //遍歷左子數
TraversalTree(root->right,currentFloor+1);//遍歷右子數
}

㈨ 用VB編寫 二叉樹的建立與遍歷、二叉樹的排序

實驗四 二叉樹的建立和團空遍歷
一、 實驗名稱
二叉樹的建立和遍歷。
二、實驗目的
掌握二叉樹的二叉鏈表存儲結構及二叉樹的建立方法。熟悉二叉樹的遍歷方法。
三、實驗內容
（1） 根據先序遍歷和中序遍歷的序列，建立一棵二叉樹（二叉樹用二叉鏈表存儲）。
（2） 分別以先序和中序遍歷二叉樹，將假設結果與給定的先序和中序遍歷序列進行比較，以證明建立二叉樹的正確性。
（3）拍羨給出後序遍歷序列。
四、實驗步驟
（1）編寫一個過程，將給出的遍歷序列讀入一個數組；
（2）編寫一個過程，根據先序和中序遍歷的序列建立一棵二叉樹；
（3）編寫一個過程，進行先序遍歷，並將結果存入一個數組。
（4）編寫一個過程，進行中序遍歷，並將結果存入一個數組。
（5） 編寫一個函數，用以證明建立的二叉樹的正確性。
（6）編寫一個過程，進行後序遍歷，列印後序遍歷結果（前面函數為真時）；
（7）調試程序：
先序遍歷序列為：ABDECF；中序遍歷序列為：DBEACF；
（8）將實驗心得寫在程序後面，作為實驗報告進行文檔備份。
五、實驗數據處理
將原程序和實驗結果存入計算機室伺服器或軟盤後，交由指導老師或有關實驗人員保存。

實驗五 二叉樹的排序
一、 實驗名稱
二叉樹的排序。
二、實驗目的
通過該實驗，進一步熟悉二叉樹的建立方法，掌握二叉排序樹的建立和使用。
三、實驗內容
（1）根據中序遍歷，建立一棵二叉排序樹用二叉鏈表存儲；
（2）給出先序遍歷和後序遍歷序列。
四、實驗步驟
（1）編寫一個過程，將給定的待排序數據讀入一個數組；
（2）編寫一個過程，建立二叉排序樹；
（3）編寫一個函數，用中序遍歷以證明二叉排序樹的正確性；
（4）編寫一個過程，進行先序遍歷，並列印遍歷結果（第3步必須確保正確）；
（5）編寫一個過程，進行後序遍歷，並列印遍歷結果（第3步必須確保正確）；
（6）調試程序；
用以下數據塌賀瞎調試程序：（58、48、77、42、64）
（7）將實驗心得寫在程序後面，作為實驗報告進行文檔備份。
五、實驗數據處理
將原程序和實驗結果存入計算機室伺服器或軟盤後，交由指導老師或有關實驗人員保存。
jiuzheyang ban

㈩ 二叉樹相關演算法的實驗驗證 [ 實驗目的] 驗證二叉樹的鏈接存儲結構及其上的基本操作。（c++）

淺談數據結構-二叉樹

二叉樹是樹的特殊一種，具有如下特點：1、每個結點最多有兩顆子樹，結點的度最大為2。2、左子樹和右子樹是有順序的，次序不能顛倒。3、即使某結點只有一個子樹，也要區分左右子樹。

一、特殊的二叉樹及特點

1、斜樹

所有的結點都只有左子樹（左斜樹），或者只有右子樹（右斜樹）。這就是斜樹，應用較少

基本思想：先後序遍歷左子樹，然後再後序遍歷右子樹，最後再訪問根結點即左—右—根。

圖中後序遍歷結果是：4，8，7，5，2，6，3，1。

後序遞歸遍歷代碼實現，如下所示。

後序遍歷的非遞歸實現是三種遍歷方式中最難的一種。因為在後序遍歷中，要保證左孩子和右孩子都已被訪問，並且左孩子在右孩子之前訪問才能訪問根結點，這就為流程式控制制帶來了難題。下面介紹一種思路。

要保證根結點在左孩子和右孩子訪問之後才能訪問，因此對於任一結點p，先將其入棧。若p不存在左孩子和右孩子，則可以直接訪問它，或者p存在左孩子或右孩子，但是其左孩子和右孩子都已經被訪問過了，則同樣可以直接訪問該結點。若非上述兩種情況，則將p的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子之前別訪問，左孩子和右孩子都在根結點前面被訪問。

五、二叉樹的建立

其實而二叉樹的建立就是二叉樹的遍歷，只不過將輸入內容改為建立結點而已，比如，利用前序遍歷建立二叉樹