日本极品一区,天天天操

作者：llhthinker

個(gè)人博客：http://www.cnblogs.com/llhthinker/

往期回顧：

Stanford機(jī)器學(xué)習(xí)筆記-1.線(xiàn)性回歸

Stanford機(jī)器學(xué)習(xí)筆記-2.Logistic Regression

Stanford機(jī)器學(xué)習(xí)筆記-3.Bayesian statistics and Regularization

Stanford機(jī)器學(xué)習(xí)筆記-4. 神經(jīng)網(wǎng)絡(luò)Neural Networks (part one)

Stanford機(jī)器學(xué)習(xí)筆記-5.神經(jīng)網(wǎng)絡(luò)Neural Networks (part two)

Stanford機(jī)器學(xué)習(xí)筆記-6. 學(xué)習(xí)模型的評(píng)估和選擇

Stanford機(jī)器學(xué)習(xí)筆記-7. Machine Learning System Design

Stanford機(jī)器學(xué)習(xí)筆記-8. 支持向量機(jī)(SVMs)概述

Stanford機(jī)器學(xué)習(xí)筆記-9. 聚類(lèi)(Clustering)

Stanford機(jī)器學(xué)習(xí)筆記-10. 降維(Dimensionality Reduction)

對(duì)于一種數(shù)據(jù)結(jié)構(gòu)而言，遍歷是常見(jiàn)操作。二叉樹(shù)是一種基本的數(shù)據(jù)結(jié)構(gòu)，是一種每個(gè)節(jié)點(diǎn)的兒子數(shù)目都不多于2的樹(shù)。二叉樹(shù)的節(jié)點(diǎn)聲明如下：

typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *BinTree;

struct TreeNode
{
int Data; //為簡(jiǎn)單起見(jiàn)，不妨假設(shè)樹(shù)節(jié)點(diǎn)的元素為int型
BinTree Left;
BinTree Right;
};

二叉樹(shù)的遍歷主要有先序遍歷，中序遍歷，后序遍歷，層序遍歷四種方式，下面一一介紹。

1. 先序遍歷

在先序遍歷中，對(duì)節(jié)點(diǎn)的訪問(wèn)工作是在它的左右兒子被訪問(wèn)之前進(jìn)行的。換言之，先序遍歷訪問(wèn)節(jié)點(diǎn)的順序是根節(jié)點(diǎn)-左兒子-右兒子。由于樹(shù)可以通過(guò)遞歸來(lái)定義，所以樹(shù)的常見(jiàn)操作用遞歸實(shí)現(xiàn)常常是方便清晰的。遞歸實(shí)現(xiàn)的代碼如下：

void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //對(duì)節(jié)點(diǎn)做些訪問(wèn)比如打印
PreOrderTraversal(BT->Left); //訪問(wèn)左兒子
PreOrderTraversal(BT->Right); //訪問(wèn)右兒子
}
}

由遞歸代碼可以看出，該遞歸為尾遞歸（尾遞歸即遞歸形式在函數(shù)末尾或者說(shuō)在函數(shù)即將返回前）。尾遞歸的遞歸調(diào)用需要用棧存儲(chǔ)調(diào)用的信息，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)容易越出?？臻g。雖然現(xiàn)在大部分的編譯器能夠自動(dòng)去除尾遞歸，但是即使如此，我們不妨自己去除。非遞歸先序遍歷算法基本思路：使用堆棧

　　a. 遇到一個(gè)節(jié)點(diǎn)，訪問(wèn)它，然后把它壓棧，并去遍歷它的左子樹(shù)；

　　b. 當(dāng)左子樹(shù)遍歷結(jié)束后，從棧頂彈出該節(jié)點(diǎn)并將其指向右兒子，繼續(xù)a步驟；

　　c. 當(dāng)所有節(jié)點(diǎn)訪問(wèn)完即最后訪問(wèn)的樹(shù)節(jié)點(diǎn)為空且棧空時(shí)，停止。

　　實(shí)現(xiàn)代碼如下：

void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S
while(T || !IsEmpty(S))
{
while(T) //一直向左并將沿途節(jié)點(diǎn)訪問(wèn)（打?。┖髩喝攵褩?nbsp;
{
printf('%d\n', T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //節(jié)點(diǎn)彈出堆棧
T = T->Right; //轉(zhuǎn)向右子樹(shù)
}
}
}

2. 中序遍歷

中序遍歷的遍歷路徑與先序遍歷完全一樣。其實(shí)現(xiàn)的思路也與先序遍歷非常相似。其主要的不同點(diǎn)是訪問(wèn)節(jié)點(diǎn)順序不同：中序遍歷是訪問(wèn)完所有左兒子后再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右兒子，即為左兒子-根節(jié)點(diǎn)-右兒子。

遞歸實(shí)現(xiàn)的代碼如下:

void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf('%d\n', BT->Data);
InOrderTraversal(BT->Right);
}
}

　　非遞歸輔助棧實(shí)現(xiàn)代碼如下:

void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MaxSize); //創(chuàng)建并初始化堆棧S
while(T || !IsEmpty(S))
　　{
　　while(T) //一直向左并將沿途節(jié)點(diǎn)壓入堆棧
　　{
　　 Push(S,T);
　　T = T->Left;
　　}
　　if(!IsEmpty(S))
　　{
　　 T = Pop(S); //節(jié)點(diǎn)彈出堆棧
　　 printf('%d\n', T->Data); //（訪問(wèn)）打印結(jié)點(diǎn)
　　 T = T->Right; //轉(zhuǎn)向右子樹(shù)
　　}
　　}
}

非遞歸不用輔助棧實(shí)現(xiàn)中序遍歷：

試設(shè)計(jì)一個(gè)非遞歸算法，按中根順序遍歷非線(xiàn)索二叉樹(shù)，但不得用任何輔助棧。在執(zhí)行算法期間，允許改變左孩子指針和右孩子指針的值。

算法：右線(xiàn)索化+回溯

若當(dāng)前樹(shù)的根節(jié)點(diǎn)p有左孩子且未被線(xiàn)索化：將其左孩子的最右結(jié)點(diǎn)（可為左孩子本身）指向p，即右線(xiàn)索化，然后p = p->lChild；

若p有左孩子但已被線(xiàn)索化，說(shuō)明該p是回溯上來(lái)的，即左孩子已經(jīng)被訪問(wèn)了，則釋放線(xiàn)索化的指針；

若p無(wú)左孩子，打印p，向上回溯(即p = p->rChild)。

代碼如下：

/*
輸入：ABDH##I##E##CF#J##G##
*/
#include

typedef struct BTNode* Position;
typedef Position BTree;
typedef char ElementType;
struct BTNode {
ElementType data;
Position lChild, rChild;
};

BTree CreateBTree(void);
void Inorder(BTree bt);

int main()
{
BTree bt = CreateBTree();
Inorder(bt);
return 0;
}

void Inorder(BTree bt)
{
Position p = bt;
while (p)
{
Position pLeft = p->lChild;
if (pLeft)
{
while (pLeft->rChild && pLeft->rChild != p) //找到以p為根結(jié)點(diǎn)的樹(shù)的最右孩子
pLeft = pLeft->rChild;
if (pLeft->rChild == NULL) //線(xiàn)索化
{
pLeft->rChild = p;
p = p->lChild;
continue;
}
else //線(xiàn)索化后已被訪問(wèn)
{
pLeft->rChild = NULL; //釋放指向根節(jié)點(diǎn)(祖先)的指針
}
}
printf('%c ', p->data); //打印
p = p->rChild; //向上回溯或者轉(zhuǎn)向右子樹(shù)
}
printf('\n');
}

BTree CreateBTree() //按照先序序列建立二叉樹(shù)
{
BTree bt = NULL;
char ch;
scanf('%c', &ch);
if (ch != '#') //'#'代表空節(jié)點(diǎn)
{
bt = new BTNode;
bt->data = ch;
bt->lChild = CreateBTree();
bt->rChild = CreateBTree();
}
return bt;
}

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

參考博客：http://m.blog.csdn.net/blog/Raito__/40618257

3. 后序遍歷

后序遍歷與中序遍歷，先序遍歷的路徑也完全一樣。主要的不同點(diǎn)是后序遍歷訪問(wèn)節(jié)點(diǎn)的順序是先訪問(wèn)左兒子和右兒子，最后訪問(wèn)節(jié)點(diǎn)，即左兒子-右兒子-根節(jié)點(diǎn)。

遞歸實(shí)現(xiàn)思路與中序遍歷和先序遍歷相似，代碼如下:

void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf('%d\n', BT->Data);
}
}

后序遍歷的非遞歸實(shí)現(xiàn)

思路一：

對(duì)于一個(gè)節(jié)點(diǎn)而言，要實(shí)現(xiàn)訪問(wèn)順序?yàn)樽髢鹤?右兒子-根節(jié)點(diǎn)，可以利用后進(jìn)先出的棧，在節(jié)點(diǎn)不為空的前提下，依次將根節(jié)點(diǎn)，右兒子，左兒子壓棧。故我們需要按照根節(jié)點(diǎn)-右兒子-左兒子的順序遍歷樹(shù)，而我們已經(jīng)知道先序遍歷的順序是根節(jié)點(diǎn)-左兒子-右兒子，故只需將先序遍歷的左右調(diào)換并把訪問(wèn)方式打印改為壓入另一個(gè)棧即可。最后一起打印棧中的元素。代碼如下：

void PostOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S1 = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S1
Stack S2 = CreatStack(MAX_SIZE); //創(chuàng)建并初始化堆棧S2
while(T || !IsEmpty(S1))
{
while(T) //一直向右并將沿途節(jié)點(diǎn)訪問(wèn)（壓入S2）后壓入堆棧S1
{
Push(S2, T);
Push(S1, T);
T = T->Right;
}
if (!IsEmpty(S1))
{
T = Pop(S1); //節(jié)點(diǎn)彈出堆棧
T = T->Left; //轉(zhuǎn)向左子樹(shù)
}
}
while(!IsEmpty(S2)) //訪問(wèn)（打?。㏒2中元素
{
T = Pop(S2);
printf('%d\n', T->Data);
}
}

思路一的優(yōu)點(diǎn)是由于利用了先序遍歷的思想，代碼較簡(jiǎn)潔，思路較清晰。缺點(diǎn)是需要用一個(gè)棧來(lái)存儲(chǔ)樹(shù)的所有節(jié)點(diǎn)，空間占用較大?！　?/p>

思路二：

要訪問(wèn)一個(gè)節(jié)點(diǎn)的條件上一個(gè)訪問(wèn)的節(jié)點(diǎn)是右兒子。我們可以增加一個(gè)變量Prev來(lái)判斷當(dāng)前節(jié)點(diǎn)Curr的上一個(gè)節(jié)點(diǎn)與它的關(guān)系來(lái)執(zhí)行相應(yīng)的操作。
若Prev為空(Curr節(jié)點(diǎn)是根節(jié)點(diǎn))或者Prev是Curr的父節(jié)點(diǎn)，將Curr節(jié)點(diǎn)的左孩子和右孩子分別壓入棧；
若Prev是Curr的左兒子，則將Curr的右兒子壓入棧；
否則Prev是Curr的右兒子，訪問(wèn)Curr;

代碼如下:

void PostOrderTraversal(BinTree BT)
{
if(BT == NULL)
return ;
Stack S = CreatStack(MAX_SIZE);
BinTree Prev = NULL , Curr = NULL; //初始化
s.push(BT);
while(!IsEmpty(S))
{
Curr = Top(S); //將棧頂元素賦給Curr
if(Prev == NULL || Prev->Left == Curr || Prev->Right == Curr) //若Prev為NULL或是Curr的父節(jié)點(diǎn)
{
if(Curr->Left != NULL)
Push(S, Curr->Left);
else if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else if(Curr->Left == Prev) //若Prev是Curr的左兒子
{
if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else
{
printf('%d\n', Curr->Data); //訪問(wèn)當(dāng)前節(jié)點(diǎn)
Pop(S); //訪問(wèn)后彈出
}
Prev = Curr; //處理完當(dāng)前節(jié)點(diǎn)后將Curr節(jié)點(diǎn)變?yōu)镻rev節(jié)點(diǎn)
}
}

4. 層序遍歷

二叉樹(shù)遍歷的核心問(wèn)題是二維結(jié)構(gòu)的線(xiàn)性化。我們通過(guò)節(jié)點(diǎn)訪問(wèn)其左右兒子時(shí)，存在的問(wèn)題是訪問(wèn)左兒子后，右兒子怎么訪問(wèn)。因此我們需要一個(gè)存儲(chǔ)結(jié)構(gòu)保存暫時(shí)不訪問(wèn)的節(jié)點(diǎn)。前面三種遍歷方式的非遞歸實(shí)現(xiàn)，我們是通過(guò)堆棧來(lái)保存。事實(shí)上也可以通過(guò)隊(duì)列來(lái)保存。

隊(duì)列實(shí)現(xiàn)的基本思路：遍歷從根節(jié)點(diǎn)開(kāi)始，首先將根節(jié)點(diǎn)入隊(duì)，然后執(zhí)行循環(huán)：節(jié)點(diǎn)出隊(duì)，訪問(wèn)（訪問(wèn)）根節(jié)點(diǎn)，將左兒子入隊(duì)，將右兒子入隊(duì)，直到隊(duì)列為空停止。

這種遍歷方式的結(jié)果是將二叉樹(shù)從上到下，從左至右一層一層的遍歷，即層序遍歷，代碼實(shí)現(xiàn)如下:

void LevelOrderTraversal(BinTree BT)
{
BinTree T;
Queue Q; //聲明一個(gè)隊(duì)列
if (BT == NULL)
return; //如果樹(shù)為空，直接返回
Q = CreatQueue(MAX_SIZE); //創(chuàng)建并初始化隊(duì)列
AddQ(Q, BT); //將根節(jié)點(diǎn)入隊(duì)
while (!IsEmpty(Q))
{
T = DeleteQ(Q); 　　　　　　　　　　//節(jié)點(diǎn)出隊(duì)
printf('%d\n', T->Data); 　　　　 //訪問(wèn)出隊(duì)的節(jié)點(diǎn)
if (T->Left) AddQ(Q, T->Left); //若左兒子不為空，將其入隊(duì)
if (T->Right) AddQ(Q, T->Right) //若右兒子不為空，將其入隊(duì)
}
}

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶(hù)發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。

免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版