国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

　　二叉樹還有一種叫雙親鏈表的存儲(chǔ)結(jié)構(gòu)，它只存儲(chǔ)結(jié)點(diǎn)的雙親信息而不存儲(chǔ)孩子信息，由于二叉樹是一種有序樹，一個(gè)結(jié)點(diǎn)的兩個(gè)孩子有左右之分，因此結(jié)點(diǎn)中除了存放雙新信息外，還必須指明這個(gè)結(jié)點(diǎn)是左孩子還是右孩子。由于結(jié)點(diǎn)不存放孩子信息，無法通過頭指針出發(fā)遍歷所有結(jié)點(diǎn)，因此需要借助數(shù)組來存放結(jié)點(diǎn)信息。圖6.10(a)所示的二叉樹使用雙親鏈表進(jìn)行存儲(chǔ)將得到圖6.11所示的結(jié)果。由于根節(jié)點(diǎn)沒有雙新，所以它的parent指針的值設(shè)為-1。

　　雙親鏈表中元素存放的順序是根據(jù)結(jié)點(diǎn)的添加順序來決定的，也就是說把各個(gè)元素的存放位置進(jìn)行調(diào)換不會(huì)影響結(jié)點(diǎn)的邏輯結(jié)構(gòu)。由圖6.11可知，雙親鏈表在物理上是一種順序存儲(chǔ)結(jié)構(gòu)。

　　二叉樹存在多種存儲(chǔ)結(jié)構(gòu)，選用何種方法進(jìn)行存儲(chǔ)主要依賴于對(duì)二叉樹進(jìn)行什么操作來確定。而二叉鏈表是二叉樹最常用的存儲(chǔ)結(jié)構(gòu)，下面幾節(jié)給出的有關(guān)二叉樹的算法大多基于二叉鏈表存儲(chǔ)結(jié)構(gòu)。

　　6.3 二叉樹的遍歷

　　二叉樹遍歷（Traversal）就是按某種順序?qū)渲忻總€(gè)結(jié)點(diǎn)訪問且只能訪問一次的過程。訪問的含義很廣，如查詢、計(jì)算、修改、輸出結(jié)點(diǎn)的值。樹遍歷本質(zhì)上是將非線性結(jié)構(gòu)線性化，它是二叉樹各種運(yùn)算和操作的實(shí)現(xiàn)基礎(chǔ)，需要高度重視。

　　6.3.1二叉樹的深度優(yōu)先遍歷

　　先左后右　 先右后左

　　先序　　　 DLR　　　 DRL

　　中序　　　 LDR　　　 RDL

　　后序　　　 LRD　　　 RLD

　　這里只討論先左后右的三種遍歷算法。

　　如圖6.13所示，在沿著箭頭方向所指的路徑對(duì)二叉樹進(jìn)行遍歷時(shí)，每個(gè)節(jié)點(diǎn)會(huì)在這條搜索路徑上會(huì)出現(xiàn)三次，而訪問操作只能進(jìn)行一次，這時(shí)就需要決定在搜索路徑上第幾次出現(xiàn)的結(jié)點(diǎn)進(jìn)行訪問操作，由此就引出了三種不同的遍歷算法。

　　1.　　　先序遍歷

　　若二叉樹為非空，則過程為：

　　（1）訪問根節(jié)點(diǎn)。

　　（2）先序遍歷左子樹。

　?。?）先序遍歷右子樹。

　　圖6.13中，先序遍歷就是把標(biāo)號(hào)為(1)的結(jié)點(diǎn)按搜索路徑訪問的先后次序連接起來，得出結(jié)果為：ABDECF。

　　2.　　　中序遍歷

　　若二叉樹為非空，則過程為：

　　（1）按中序遍歷左子樹。

　?。?）訪問根結(jié)點(diǎn)。

　?。?）按中序遍歷右子樹。

　　圖6.13中，先序遍歷就是把標(biāo)號(hào)為(2)的結(jié)點(diǎn)按搜索路徑訪問的先后次序連接起來，得出結(jié)果為：DBEACF。

　　3.　　　后序遍歷

　　若二叉樹為非空，則過程為：

　　（1）按后序遍歷左子樹。

　?。?）按后序遍歷右子樹

　?。?）訪問根結(jié)點(diǎn)。

　　圖6.13中，先序遍歷就是把標(biāo)號(hào)為(3)的結(jié)點(diǎn)按搜索路徑訪問的先后次序連接起來，得出結(jié)果為：DEBFCA。

　　【例6-1BinaryTreeNode.cs】二叉樹結(jié)點(diǎn)類

1usingSystem;
2publicclassNode
3{
4　　//成員變量
5　　privateobject_data;//數(shù)據(jù)
6　　privateNode_left;//左孩子
7　　privateNode_right;//右孩子
8　　publicobjectData
9　　{
10　　　　get{return_data;}
11　　}
12　　publicNodeLeft//左孩子
13　　{
14　　　　get{return_left;}
15　　　　set{_left=value;}
16　　}
17　　publicNodeRight//右孩子
18　　{
19　　　　get{return_right;}
20　　　　set{_right=value;}
21　　}
22　　//構(gòu)造方法
23　　publicNode(objectdata)
24　　{
25　　　　_data=data;
26　　}
27　　publicoverridestringToString()
28　　{
29　　　　return_data.ToString();
30　　}
31}
32

　　Node類專門用于表示二叉樹中的一個(gè)結(jié)點(diǎn)，它很簡(jiǎn)單，只有三個(gè)屬性：Data表示結(jié)點(diǎn)中的數(shù)據(jù)；Left表示這個(gè)結(jié)點(diǎn)的左孩子，它是Node類型；Right表示這個(gè)結(jié)點(diǎn)的右孩子，它也是Node類型。

　　【例6-1BinaryTree.cs】二叉樹集合類

1usingSystem;
2publicclassBinaryTree
3{　　//成員變量
4　　privateNode_head;//頭指針
5　　privatestringcStr;//用于構(gòu)造二叉樹的字符串
6　　publicNodeHead//頭指針
7　　{
8　　　　get{return_head;}
9　　}
10　　//構(gòu)造方法
11　　publicBinaryTree(stringconstructStr)
12　　{
13　　　　cStr=constructStr;
14　　　　_head=newNode(cStr[0]);//添加頭結(jié)點(diǎn)
15　　　　Add(_head,0);//給頭結(jié)點(diǎn)添加孩子結(jié)點(diǎn)
16　　}
17　　privatevoidAdd(Nodeparent,intindex)
18　　{
19　　　　intleftIndex=2*index+1;//計(jì)算左孩子索引
20　　　　if(leftIndex<cStr.Length)//如果索引沒超過字符串長(zhǎng)度
21　　　　{
22　　　　　　if(cStr[leftIndex]!='#')//'#'表示空結(jié)點(diǎn)
23　　　　　　{　//添加左孩子
24　　　　　　　　parent.Left=newNode(cStr[leftIndex]);
25　　　　　　　　//遞歸調(diào)用Add方法給左孩子添加孩子節(jié)點(diǎn)
26　　　　　　　　Add(parent.Left,leftIndex);
27　　　　　　}
28　　　　}
29　　　　intrightIndex=2*index+2;
30　　　　if(rightIndex<cStr.Length)
31　　　　{
32　　　　　　if(cStr[rightIndex]!='#')
33　　　　　　{　//添加右孩子
34　　　　　　　　parent.Right=newNode(cStr[rightIndex]);
35　　　　　　　　//遞歸調(diào)用Add方法給右孩子添加孩子節(jié)點(diǎn)
36　　　　　　　　Add(parent.Right,rightIndex);
37　　　　　　}
38　　　　}
39　　}
40　　publicvoidPreOrder(Nodenode)//先序遍歷
41　　{
42　　　　if(node!=null)
43　　　　{
44　　　　　　Console.Write(node.ToString());//打印字符
45　　　　　　PreOrder(node.Left);//遞歸
46　　　　　　PreOrder(node.Right);//遞歸
47　　　　}
48　　}
49　　publicvoidMidOrder(Nodenode)//中序遍歷
50　　{
51　　　　if(node!=null)
52　　　　{
53　　　　　　MidOrder(node.Left);//遞歸
54　　　　　　Console.Write(node.ToString());//打印字符
55　　　　　　MidOrder(node.Right);//遞歸
56　　　　}
57　　}
58　　publicvoidAfterOrder(Nodenode)//后繼遍歷
59　　{
60　　　　if(node!=null)
61　　　　{
62　　　　　　AfterOrder(node.Left);//遞歸
63　　　　　　AfterOrder(node.Right);//遞歸
64　　　　　　Console.Write(node.ToString());//打印字符
65　　　　}
66　　}
67}
68

　　BinaryTree是一個(gè)二叉樹的集合類，它屬于二叉鏈表，實(shí)際存儲(chǔ)的信息只有一個(gè)頭結(jié)點(diǎn)指針（Head），由于是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以由Head指針出發(fā)遍歷整個(gè)二叉樹。為了便于測(cè)試及添加結(jié)點(diǎn)，假設(shè)BinaryTree類中存放的數(shù)據(jù)是字符類型，第5行聲明了一個(gè)字符串類型成員cStr，它用于存放結(jié)點(diǎn)中所有的字符。字符串由滿二叉樹的方式進(jìn)行構(gòu)造，空結(jié)點(diǎn)用‘#’號(hào)表示（參考本章“二叉樹存儲(chǔ)結(jié)構(gòu)”這一小節(jié)中的“順序存儲(chǔ)結(jié)構(gòu)”）。圖6.13所示的二叉樹可表示為：“ABCDE#F”。

　　11～16行的構(gòu)造方法傳入一個(gè)構(gòu)造字符串，并在Add()方法中根據(jù)這個(gè)字符串來構(gòu)造二叉樹中相應(yīng)的結(jié)點(diǎn)。需要注意，這個(gè)構(gòu)造方法只用于測(cè)試。

　　17～39行的Add()方法用于添加結(jié)點(diǎn)，它的第一個(gè)參數(shù)parent表示需要添加孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)，第二個(gè)參數(shù)index表示這個(gè)雙親結(jié)點(diǎn)的編號(hào)（編號(hào)表示使用順序存儲(chǔ)結(jié)構(gòu)時(shí)它在數(shù)組中的索引，請(qǐng)參考本章“二叉樹存儲(chǔ)結(jié)構(gòu)”這一小節(jié)中的“順序存儲(chǔ)結(jié)構(gòu)”）。添加孩子結(jié)點(diǎn)的方法是先計(jì)算孩子結(jié)點(diǎn)的編號(hào)，然后通過這個(gè)編號(hào)在cStr中取出相應(yīng)的字符，并構(gòu)造新的孩子結(jié)點(diǎn)用于存放這個(gè)字符，接下來遞歸調(diào)用Add()方法給孩子結(jié)點(diǎn)添加它們的孩子結(jié)點(diǎn)。注意，這個(gè)方法只用于測(cè)試。

　　40～48行代碼的PreOrder()方法用于先序遍歷，它的代碼跟之前所講解的先序遍歷過程完全一樣。

　　49～57行代碼的MidOrder()方法用于中序遍歷。

　　58～66行代碼的AfterOrder()方法用于后序遍歷。

　　以上三個(gè)方法都使用了遞歸來完成遍歷，這符合二叉樹的定義。

　　【例6-1Demo6-1.cs】二叉樹深度優(yōu)先遍歷測(cè)試

1usingSystem;
2classDemo6_1
3{
4　　staticvoidMain(string[]args)
5　　{　//使用字符串構(gòu)造二叉樹
6　　　　BinaryTreebTree=newBinaryTree("ABCDE#F");
7　　　　bTree.PreOrder(bTree.Head);//先序遍
8　　　　Console.WriteLine();
9　　　　bTree.MidOrder(bTree.Head);//中序遍
10　　　　Console.WriteLine();
11　　　　bTree.AfterOrder(bTree.Head);//后序遍
12　　　　Console.WriteLine();
13　　}
14}
15

　　運(yùn)行結(jié)果：

　　ABDECF

　　DBEACF

　　DEBFCA

　　6.3.2二叉樹的寬度優(yōu)先遍歷

　　之前所講述的二叉樹的深度優(yōu)先遍歷的搜索路徑是首先搜索一個(gè)結(jié)點(diǎn)的所有子孫結(jié)點(diǎn)，再搜索這個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。是否可以先搜索所有兄弟和堂兄弟結(jié)點(diǎn)再搜索子孫結(jié)點(diǎn)呢？

　　由于二叉樹結(jié)點(diǎn)分屬不同的層次，因此可以從上到下、從左到右依次按層訪問每個(gè)結(jié)點(diǎn)。它的訪問順序正好和之前所述二叉樹順序存儲(chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)在數(shù)組中的存放順序相吻合。如圖6.13中的二叉樹使用寬度優(yōu)先遍歷訪問的順序?yàn)椋篈BCDEF。

　　這個(gè)搜索過程不再需要使用遞歸，但需要借助隊(duì)列來完成。

　?。?）將根結(jié)點(diǎn)壓入隊(duì)列之中，開始執(zhí)行步驟(2)。

　　（2）若隊(duì)列為空，則結(jié)束遍歷操作，否則取隊(duì)頭結(jié)點(diǎn)D。

　?。?）若結(jié)點(diǎn)D的左孩子結(jié)點(diǎn)存在，則將其左孩子結(jié)點(diǎn)壓入隊(duì)列。

　?。?）若結(jié)點(diǎn)D的右孩子結(jié)點(diǎn)存在，則將其右孩子結(jié)點(diǎn)壓入隊(duì)列，并重復(fù)步驟(2)。

　　【例6-2BinaryTreeNode.cs.cs】二叉樹結(jié)點(diǎn)類，使用例6-1同名文件。

　　【例6-2LevelOrderBinaryTree.cs】包含寬度優(yōu)先遍歷方法的二叉樹集合類

　　打開例6-1的【BinaryTree.cs】文件，在BinaryTree類中添加如入方法后另存為L(zhǎng)evelOrderBinaryTree.cs文件。

1　　publicvoidLevelOrder()//寬度優(yōu)先遍歷
2　　{
3　　　　Queuequeue=newQueue();//聲明一個(gè)隊(duì)例
4　　　　queue.Enqueue(_head);//把根結(jié)點(diǎn)壓入隊(duì)列
5　　　　while(queue.Count>0)//只要隊(duì)列不為空
6　　　　{
7　　　　　　Nodenode=(Node)queue.Dequeue();//出隊(duì)
8　　　　　　Console.Write(node.ToString());//訪問結(jié)點(diǎn)
9　　　　　　if(node.Left!=null)//如果結(jié)點(diǎn)左孩子不為空
10　　　　　　{　//把左孩子壓入隊(duì)列
11　　　　　　　　queue.Enqueue(node.Left);
12　　　　　　}
13　　　　　　if(node.Right!=null)//如果結(jié)點(diǎn)右孩子不為熔
14　　　　　　{　//把右孩子壓入隊(duì)列
15　　　　　　　　queue.Enqueue(node.Right);
16　　　　　　}
17　　　　}
18　　}

　　【例6-2Demo6-2.cs】二叉樹寬度優(yōu)先遍歷測(cè)試

1usingSystem;
2classDemo6_2
3{
4　　staticvoidMain(string[]args)
5　　{　//使用字符串構(gòu)造二叉樹
6　　　　BinaryTreebTree=newBinaryTree("ABCDE#F");
7　　　　bTree.LevelOrder();
8　　}
9}