二叉樹學(xué)結(jié)
今天學(xué)習(xí)了線索二叉樹，剛開始對(duì)這些線索該如何創(chuàng)建有些疑惑，后來(lái)仔細(xì)品讀書中的話語(yǔ)，再結(jié)合圖形，終于理解了。先將心得陳述如下：
首先，必須記住以下兩條規(guī)則：
1、當(dāng)某結(jié)點(diǎn)的左指針域?yàn)榭諘r(shí)，令其指向依據(jù)某種方式遍歷（前序、中序、后序）時(shí)所得到的該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；
2、當(dāng)某結(jié)點(diǎn)的右指針域?yàn)榭諘r(shí)，令其指向依據(jù)某種方式遍歷（前序、中序、后序）時(shí)所得到的該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。
下面，以一個(gè)實(shí)例進(jìn)行詳解：
一個(gè)中序線索二叉樹如下所示：
那么我們?cè)鯓拥玫饺鐖D所示的結(jié)果呢？
一、得出該二叉樹的中序（因?yàn)樵搱D式中序線索）遍歷結(jié)果；
二、根據(jù)該遍歷結(jié)果的順序，依次針對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行那兩條規(guī)則的分析；
三、根據(jù)分析的結(jié)果畫出虛線，即線索。
具體分析如下：
該二叉樹的中序遍歷結(jié)果是：c b d a f h g i e
1）、對(duì)結(jié)點(diǎn)c，因?yàn)槠涫侨~子結(jié)點(diǎn)，所以其左、右指針域都為空；由于其左指針域?yàn)榭眨�，�?yīng)該指向其序列中的前驅(qū)結(jié)點(diǎn)，但是因?yàn)閏結(jié)點(diǎn)已經(jīng)是序列中的第一個(gè)結(jié)點(diǎn)，所以它沒(méi)有前驅(qū)結(jié)點(diǎn)，只能指向null；由于其右指針域?yàn)榭�，所以，�?yīng)該指向其序列中的后繼結(jié)點(diǎn)b（如圖c指向b的虛線）。
2）、對(duì)結(jié)點(diǎn)b，因?yàn)槠渥�、右指針域均不為空，所以，不�?huì)對(duì)它畫出線索。
3）、對(duì)結(jié)點(diǎn)d，它的情況和c相同，所以，分別指向該序列中它的前驅(qū)結(jié)點(diǎn)b和后繼結(jié)點(diǎn)a。
4）、對(duì)結(jié)點(diǎn)a，其情況和b相同，所以，沒(méi)有線索。
5）、對(duì)結(jié)點(diǎn)f，因?yàn)槠渥笾羔樣驗(yàn)榭眨詰?yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)a。
6）、對(duì)結(jié)點(diǎn)h，其是葉子結(jié)點(diǎn)，所以應(yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)f和后繼結(jié)點(diǎn)g。
7）、對(duì)結(jié)點(diǎn)g，其情況和b相同，沒(méi)有線索。
8）、對(duì)結(jié)點(diǎn)i，其是葉子結(jié)點(diǎn)，所以應(yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)g和后繼結(jié)點(diǎn)e。
9）、對(duì)結(jié)點(diǎn)e，因?yàn)槠溆抑羔樣驗(yàn)榭�，所以�?yīng)該指向序列中它的后繼結(jié)點(diǎn)，但因?yàn)樗呀?jīng)是該序列中的最后一個(gè)結(jié)點(diǎn)，所以，指向null。
過(guò)程結(jié)束。就是這樣。
二叉樹學(xué)結(jié) [篇2]
以下是我總結(jié)的關(guān)于二叉樹的前、中、后序以及層次遍歷的非遞歸算法；闡述了基本思想，代碼均通過(guò)驗(yàn)證。(我去！sina博客有點(diǎn)low啊，我的類型顯示不出來(lái)，以下stack后面應(yīng)該是尖括號(hào)node*)
//兩個(gè)棧實(shí)現(xiàn)非遞歸后續(xù)遍歷樹
//算法步驟：
//（1）根節(jié)點(diǎn)壓入棧1，出棧并壓入第二個(gè)棧
//（2）將入棧2節(jié)點(diǎn)的左節(jié)點(diǎn)入棧（假如左節(jié)點(diǎn)非空），將其右節(jié)點(diǎn)入棧（非空），重復(fù)步驟一，直到�？�
//需要注意兩個(gè)地方，第一：將節(jié)點(diǎn)入棧時(shí)要判空；第二，因?yàn)槭褂脙蓚�(gè)棧，本來(lái)后續(xù)是先左后右，一個(gè)棧需
//要按照先右后左的方式入棧，兩個(gè)棧的話則“負(fù)負(fù)得正”，先左后右入棧。這與一個(gè)棧的順序是不同的。
void travel_postorder(node* &root)
{
if(root==null)
return;
stacks1;
stacks2;
node*cur=root;
s1.push(cur);
while(!s1.empty())
{
cur=#url#();
s1.pop();
s2.push(cur);
if(cur->left!=null)
s1.push(cur->left);
if(cur->right!=null)
s1.push(cur->right);
}
while(!s2.empty())
{
cout<<#url#()->data<<' ';
s2.pop();
}
}
//前序非遞歸遍歷
//解法1：（1）跟節(jié)點(diǎn)入棧，出棧并打��；（2）壓入出棧節(jié)點(diǎn)的右節(jié)點(diǎn)（判空），壓入出棧節(jié)點(diǎn)的左節(jié)點(diǎn)（判空），重復(fù)直到�？�
void travel_preorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
s.push(cur);
while(!s.empty())
{
cur=#url#();
s.pop();
cout<<cur->data<<' ';
if(cur->right!=null)
s.push(cur->right);
if(cur->left!=null)
s.push(cur->left);
}
}
//解法2：按照定義，先根后左再右；同樣用棧實(shí)現(xiàn)，遇到根節(jié)點(diǎn)直接輸出，并入棧保存最后回溯
//（1）跟節(jié)點(diǎn)入棧，當(dāng)跟節(jié)點(diǎn)非空時(shí)一直找到最左邊的節(jié)點(diǎn)后回溯；
//（2）當(dāng)節(jié)點(diǎn)為空時(shí)，棧不空時(shí)，開始回溯；將回溯節(jié)點(diǎn)的右節(jié)點(diǎn)入棧，重復(fù)過(guò)程1，直到棧空為止
void travle_preorder(node* root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !s.empty())
{
if(cur!=null)
{//一直找到最左邊的節(jié)點(diǎn)
cout<<cur->data<<' ';
s.push(cur);
cur=cur->left;
}
else
{
//回溯
cur=#url#();
s.pop();
cur=cur->right;
}
}
}
//中序非遞歸遍歷
//算法步驟：（1）根節(jié)點(diǎn)入棧，一直找到最左邊的節(jié)點(diǎn)，然后回溯；（2）找到最左邊的節(jié)點(diǎn)后，開始回溯，取棧頂數(shù)據(jù)輸出，右節(jié)點(diǎn)（非空）入棧，重復(fù)直到�？铡�
void travel_midorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !s.empty())
{
if(cur!=null)//找到最左邊的節(jié)點(diǎn)。
{
s.push(cur);
cur=cur->left;
}
else
{//回溯
cur=#url#();
cout<<cur->data<<' ';
s.pop();
cur=cur->right;
}
}
}
//層次遍歷樹：
//利用隊(duì)列先進(jìn)先出的'概念，先跟節(jié)點(diǎn)入隊(duì)，之后出隊(duì)；出隊(duì)節(jié)點(diǎn)的左右節(jié)點(diǎn)（非空）入隊(duì)；重復(fù)直到隊(duì)空
void travel_level(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
nd.push_back(cur);
while(!nd.empty())
{
cur=nd.front();
cout<<cur->data<<' ';
nd.pop_front();//出隊(duì)
if(cur->left!=null)
nd.push_back(cur->left);//入隊(duì)
if(cur->right!=null)
nd.push_back(cur->right);//入隊(duì)
}
}
//如果要求層次遍歷，每行按行輸出，有兩種常用解法
//1）使用兩個(gè)隊(duì)列，隊(duì)列1存放當(dāng)前層的節(jié)點(diǎn)，隊(duì)列而存放下一層的節(jié)點(diǎn)，然后交替打印
void travel_level_towq(node* &root)
{
if(root==null)
return;
dequend1;
dequend2;
node*cur=root;
nd1.push_back(cur);
while(!nd1.empty() || !nd2.empty() )
{
while(!nd1.empty())
{
cur=nd1.front();
cout<<cur->data<<'';//輸出當(dāng)前隊(duì)列中的節(jié)點(diǎn)
nd1.pop_front();
if(cur->left!=null)
nd2.push_back(cur->left);
if(cur->right!=null)
nd2.push_back(cur->right);
}
//此時(shí)nd1已經(jīng)為null，nd2為其下一行應(yīng)該要打印的節(jié)點(diǎn)
cout<<endl;//一層輸出完畢，進(jìn)行換行
while(!nd2.empty())
{
cur=nd2.front();
cout<<cur->data<<'';//輸出當(dāng)前隊(duì)列中的節(jié)點(diǎn)
nd2.pop_front();
if(cur->left!=null)
nd1.push_back(cur->left);
if(cur->right!=null)
nd1.push_back(cur->right);
}
cout<<endl;//一層輸出完畢，進(jìn)行換行
}
}
//2）只使用一個(gè)隊(duì)列，需要兩個(gè)額外的變量，來(lái)記錄當(dāng)前層的節(jié)點(diǎn)個(gè)數(shù)和下一層的節(jié)點(diǎn)個(gè)數(shù)。
void travel_level_oneq(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
nd.push_back(cur);
intcur_num=1;//當(dāng)前行有多少個(gè)節(jié)點(diǎn)，初始化為1
intnext_num=0;//下一層有多少個(gè)節(jié)點(diǎn)，初始為0
while(!nd.empty())
{
cur=nd.front();
cout<<cur->data<<' ';
nd.pop_front();
cur_num--;//當(dāng)前層輸出一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)就減少1
if(cur->left!=null)
{
nd.push_back(cur->left);
next_num++;
}//出棧節(jié)點(diǎn)的左子不為空的話，壓入隊(duì)列，下層的節(jié)點(diǎn)數(shù)加1
if(cur->right!=null)
{
nd.push_back(cur->right);
next_num++;
}//出棧節(jié)點(diǎn)的右子不為空的話，壓入隊(duì)列，下層的節(jié)點(diǎn)數(shù)加1
if(cur_num==0)
{
cout<<endl;//當(dāng)前層節(jié)點(diǎn)全部遍歷，輸出換行符
cur_num=next_num;//把下一行當(dāng)做當(dāng)前行處理
next_num=0;//初始化下一行為0
}
}
}
【二叉樹學(xué)結(jié)】相關(guān)文章：
對(duì)學(xué)結(jié)06-03
遠(yuǎn)程學(xué)結(jié)06-13
對(duì)標(biāo)學(xué)結(jié)06-03
蹲點(diǎn)學(xué)結(jié)06-03
俄語(yǔ)學(xué)結(jié)06-03
法規(guī)學(xué)結(jié)06-03
法語(yǔ)學(xué)結(jié)06-03
翻譯學(xué)結(jié)06-03