二叉樹學(xué)結(jié)
今天學(xué)習(xí)了線索二叉樹，剛開始對這些線索該如何創(chuàng)建有些疑惑，后來仔細(xì)品讀書中的話語，再結(jié)合圖形，終于理解了。先將心得陳述如下：
首先，必須記住以下兩條規(guī)則：
1、當(dāng)某結(jié)點(diǎn)的左指針域為空時，令其指向依據(jù)某種方式遍歷（前序、中序、后序）時所得到的該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；
2、當(dāng)某結(jié)點(diǎn)的右指針域為空時，令其指向依據(jù)某種方式遍歷（前序、中序、后序）時所得到的該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。
下面，以一個實(shí)例進(jìn)行詳解：
一個中序線索二叉樹如下所示：
那么我們怎樣得到如圖所示的結(jié)果呢？
一、得出該二叉樹的中序（因為該圖式中序線索）遍歷結(jié)果；
二、根據(jù)該遍歷結(jié)果的順序，依次針對每個結(jié)點(diǎn)進(jìn)行那兩條規(guī)則的分析；
三、根據(jù)分析的結(jié)果畫出虛線，即線索。
具體分析如下：
該二叉樹的中序遍歷結(jié)果是：c b d a f h g i e
1）、對結(jié)點(diǎn)c，因為其是葉子結(jié)點(diǎn)，所以其左、右指針域都為空；由于其左指針域為空，所以，應(yīng)該指向其序列中的前驅(qū)結(jié)點(diǎn)，但是因為c結(jié)點(diǎn)已經(jīng)是序列中的第一個結(jié)點(diǎn)，所以它沒有前驅(qū)結(jié)點(diǎn)，只能指向null；由于其右指針域為空，所以，應(yīng)該指向其序列中的后繼結(jié)點(diǎn)b（如圖c指向b的虛線）。
2）、對結(jié)點(diǎn)b，因為其左、右指針域均不為空，所以，不會對它畫出線索。
3）、對結(jié)點(diǎn)d，它的情況和c相同，所以，分別指向該序列中它的前驅(qū)結(jié)點(diǎn)b和后繼結(jié)點(diǎn)a。
4）、對結(jié)點(diǎn)a，其情況和b相同，所以，沒有線索。
5）、對結(jié)點(diǎn)f，因為其左指針域為空，所以應(yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)a。
6）、對結(jié)點(diǎn)h，其是葉子結(jié)點(diǎn)，所以應(yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)f和后繼結(jié)點(diǎn)g。
7）、對結(jié)點(diǎn)g，其情況和b相同，沒有線索。
8）、對結(jié)點(diǎn)i，其是葉子結(jié)點(diǎn)，所以應(yīng)該指向序列中它的前驅(qū)結(jié)點(diǎn)g和后繼結(jié)點(diǎn)e。
9）、對結(jié)點(diǎn)e，因為其右指針域為空，所以應(yīng)該指向序列中它的后繼結(jié)點(diǎn)，但因為它已經(jīng)是該序列中的最后一個結(jié)點(diǎn)，所以，指向null。
過程結(jié)束。就是這樣。
二叉樹學(xué)結(jié) [篇2]
以下是我總結(jié)的關(guān)于二叉樹的前、中、后序以及層次遍歷的非遞歸算法；闡述了基本思想，代碼均通過驗證。(我去！sina博客有點(diǎn)low啊，我的類型顯示不出來，以下stack后面應(yīng)該是尖括號node*)
//兩個棧實(shí)現(xiàn)非遞歸后續(xù)遍歷樹
//算法步驟：
//（1）根節(jié)點(diǎn)壓入棧1，出棧并壓入第二個棧
//（2）將入棧2節(jié)點(diǎn)的左節(jié)點(diǎn)入棧（假如左節(jié)點(diǎn)非空），將其右節(jié)點(diǎn)入棧（非空），重復(fù)步驟一，直到棧空
//需要注意兩個地方，第一：將節(jié)點(diǎn)入棧時要判空；第二，因為使用兩個棧，本來后續(xù)是先左后右，一個棧需
//要按照先右后左的方式入棧，兩個棧的話則“負(fù)負(fù)得正”，先左后右入棧。這與一個棧的順序是不同的。
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)非空時一直找到最左邊的節(jié)點(diǎn)后回溯；
//（2）當(dāng)節(jié)點(diǎn)為空時，棧不空時，開始回溯；將回溯節(jié)點(diǎn)的右節(jié)點(diǎn)入棧，重復(fù)過程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;
}
}
}
//層次遍歷樹：
//利用隊列先進(jìn)先出的'概念，先跟節(jié)點(diǎn)入隊，之后出隊；出隊節(jié)點(diǎn)的左右節(jié)點(diǎn)（非空）入隊；重復(fù)直到隊空
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();//出隊
if(cur->left!=null)
nd.push_back(cur->left);//入隊
if(cur->right!=null)
nd.push_back(cur->right);//入隊
}
}
//如果要求層次遍歷，每行按行輸出，有兩種常用解法
//1）使用兩個隊列，隊列1存放當(dāng)前層的節(jié)點(diǎn)，隊列而存放下一層的節(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)前隊列中的節(jié)點(diǎn)
nd1.pop_front();
if(cur->left!=null)
nd2.push_back(cur->left);
if(cur->right!=null)
nd2.push_back(cur->right);
}
//此時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)前隊列中的節(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）只使用一個隊列，需要兩個額外的變量，來記錄當(dāng)前層的節(jié)點(diǎn)個數(shù)和下一層的節(jié)點(diǎn)個數(shù)。
void travel_level_oneq(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
nd.push_back(cur);
intcur_num=1;//當(dāng)前行有多少個節(jié)點(diǎn)，初始化為1
intnext_num=0;//下一層有多少個節(jié)點(diǎn)，初始為0
while(!nd.empty())
{
cur=nd.front();
cout<<cur->data<<' ';
nd.pop_front();
cur_num--;//當(dāng)前層輸出一個節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)就減少1
if(cur->left!=null)
{
nd.push_back(cur->left);
next_num++;
}//出棧節(jié)點(diǎn)的左子不為空的話，壓入隊列，下層的節(jié)點(diǎn)數(shù)加1
if(cur->right!=null)
{
nd.push_back(cur->right);
next_num++;
}//出棧節(jié)點(diǎn)的右子不為空的話，壓入隊列，下層的節(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)文章：
對學(xué)結(jié)06-03
遠(yuǎn)程學(xué)結(jié)06-13
對標(biāo)學(xué)結(jié)06-03
對excel的學(xué)結(jié)06-03
蹲點(diǎn)學(xué)結(jié)06-03
俄語學(xué)結(jié)06-03
法規(guī)學(xué)結(jié)06-03
法語學(xué)結(jié)06-03
翻譯學(xué)結(jié)06-03