今天學習了線索二叉樹,剛開始對這些線索該如何建立有些疑惑,後來仔細品讀書中的話語,再結合圖形,終於理解了。先將心得陳述如下:
首先,必須記住以下兩條規則:
1、當某結點的左指標域為空時,令其指向依據某種方式遍歷(前序、中序、後序)時所得到的該結點的前驅結點;
2、當某結點的右指標域為空時,令其指向依據某種方式遍歷(前序、中序、後序)時所得到的該結點的後繼結點。
下面,以一個例項進行詳解:
一箇中序線索二叉樹如下所示:
那麼我們怎樣得到如圖所示的結果呢?
一、得出該二叉樹的中序(因為該圖式中序線索)遍歷結果;
二、根據該遍歷結果的順序,依次針對每個結點進行那兩條規則的分析;
三、根據分析的結果畫出虛線,即線索。
具體分析如下:
該二叉樹的中序遍歷結果是:c b d a f h g i e
1)、對結點c,因為其是葉子結點,所以其左、右指標域都為空;由於其左指標域為空,所以,應該指向其序列中的前驅結點,但是因為c結點已經是序列中的第一個結點,所以它沒有前驅結點,只能指向null;由於其右指標域為空,所以,應該指向其序列中的後繼結點b(如圖c指向b的虛線)。
2)、對結點b,因為其左、右指標域均不為空,所以,不會對它畫出線索。
3)、對結點d,它的情況和c相同,所以,分別指向該序列中它的前驅結點b和後繼結點a。
4)、對結點a,其情況和b相同,所以,沒有線索。
5)、對結點f,因為其左指標域為空,所以應該指向序列中它的前驅結點a。
6)、對結點h,其是葉子結點,所以應該指向序列中它的前驅結點f和後繼結點g。
7)、對結點g,其情況和b相同,沒有線索。
8)、對結點i,其是葉子結點,所以應該指向序列中它的前驅結點g和後繼結點e。
9)、對結點e,因為其右指標域為空,所以應該指向序列中它的後繼結點,但因為它已經是該序列中的最後一個結點,所以,指向null。
過程結束。就是這樣。
二叉樹學結 [篇2]
以下是我總結的關於二叉樹的前、中、後序以及層次遍歷的非遞迴演算法;闡述了基本思想,程式碼均通過驗證。(我去!sina部落格有點low啊,我的型別顯示不出來,以下stack後面應該是尖括號node*)
//兩個棧實現非遞迴後續遍歷樹
//演算法步驟:
//(1)根節點壓入棧1,出棧並壓入第二個棧
//(2)將入棧2節點的左節點入棧(假如左節點非空),將其右節點入棧(非空),重複步驟一,直到棧空
//需要注意兩個地方,第一:將節點入棧時要判空;第二,因為使用兩個棧,本來後續是先左後右,一個棧需
//要按照先右後左的方式入棧,兩個棧的話則“負負得正”,先左後右入棧。這與一個棧的順序是不同的。
void travel_postorder(node* &root)
{
if(root==null)
return;
stacks1;
stacks2;
node*cur=root;
(cur);
while(!y())
{
cur=#url#();
();
(cur);
if(cur->left!=null)
(cur->left);
if(cur->right!=null)
(cur->right);
}
while(!y())
{
cout<<#url#()->data<<' ';
();
}
}
//前序非遞迴遍歷
//解法1:(1)跟節點入棧,出棧並列印;(2)壓入出棧節點的右節點(判空),壓入出棧節點的左節點(判空),重複直到棧空
void travel_preorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
(cur);
while(!y())
{
cur=#url#();
();
cout<<cur->data<<' ';
if(cur->right!=null)
(cur->right);
if(cur->left!=null)
(cur->left);
}
}
//解法2:按照定義,先根後左再右;同樣用棧實現,遇到根節點直接輸出,併入棧儲存最後回溯
//(1)跟節點入棧,當跟節點非空時一直找到最左邊的'節點後回溯;
//(2)當節點為空時,棧不空時,開始回溯;將回溯節點的右節點入棧,重複過程1,直到棧空為止
void travle_preorder(node* root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !y())
{
if(cur!=null)
{//一直找到最左邊的節點
cout<<cur->data<<' ';
(cur);
cur=cur->left;
}
else
{
//回溯
cur=#url#();
();
cur=cur->right;
}
}
}
//中序非遞迴遍歷
//演算法步驟:(1)根節點入棧,一直找到最左邊的節點,然後回溯;(2)找到最左邊的節點後,開始回溯,取棧頂資料輸出,右節點(非空)入棧,重複直到棧空。
void travel_midorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !y())
{
if(cur!=null)//找到最左邊的節點。
{
(cur);
cur=cur->left;
}
else
{//回溯
cur=#url#();
cout<<cur->data<<' ';
();
cur=cur->right;
}
}
}
//層次遍歷樹:
//利用佇列先進先出的概念,先跟節點入隊,之後出隊;出隊節點的左右節點(非空)入隊;重複直到隊空
void travel_level(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
_back(cur);
while(!y())
{
cur=t();
cout<<cur->data<<' ';
_front();//出隊
if(cur->left!=null)
_back(cur->left);//入隊
if(cur->right!=null)
_back(cur->right);//入隊
}
}
//如果要求層次遍歷,每行按行輸出,有兩種常用解法
//1)使用兩個佇列,佇列1存放當前層的節點,佇列而存放下一層的節點,然後交替列印
void travel_level_towq(node* &root)
{
if(root==null)
return;
dequend1;
dequend2;
node*cur=root;
_back(cur);
while(!y() || !y() )
{
while(!y())
{
cur=t();
cout<<cur->data<<'';//輸出當前佇列中的節點
_front();
if(cur->left!=null)
_back(cur->left);
if(cur->right!=null)
_back(cur->right);
}
//此時nd1已經為null,nd2為其下一行應該要列印的節點
cout<<endl;//一層輸出完畢,進行換行
while(!y())
{
cur=t();
cout<<cur->data<<'';//輸出當前佇列中的節點
_front();
if(cur->left!=null)
_back(cur->left);
if(cur->right!=null)
_back(cur->right);
}
cout<<endl;//一層輸出完畢,進行換行
}
}
//2)只使用一個佇列,需要兩個額外的變數,來記錄當前層的節點個數和下一層的節點個數。
void travel_level_oneq(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
_back(cur);
intcur_num=1;//當前行有多少個節點,初始化為1
intnext_num=0;//下一層有多少個節點,初始為0
while(!y())
{
cur=t();
cout<<cur->data<<' ';
_front();
cur_num--;//當前層輸出一個節點,節點數就減少1
if(cur->left!=null)
{
_back(cur->left);
next_num++;
}//出棧節點的左子不為空的話,壓入佇列,下層的節點數加1
if(cur->right!=null)
{
_back(cur->right);
next_num++;
}//出棧節點的右子不為空的話,壓入佇列,下層的節點數加1
if(cur_num==0)
{
cout<<endl;//當前層節點全部遍歷,輸出換行符
cur_num=next_num;//把下一行當做當前行處理
next_num=0;//初始化下一行為0
}
}
}