二叉樹學結

今天學習了線索二叉樹，剛開始對這些線索該如何創建有些疑惑，後來仔細品讀書中的話語，再結合圖形，終於理解了。先將心得陳述如下：

首先，必須記住以下兩條規則：

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

}

}

}