數據結構二叉樹遍歷演算法

Ⅰ 什麼是二叉樹數的遍歷

二叉樹遍歷（Traversal）是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。

遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：訪問結點本身（N），遍歷該結點的左子樹（L），遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。
注意：前三種次序與後三種次序對稱

遍歷命名
根據訪問結點操作發生位置命名：
①NLR：前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問根結點的操作發生在遍歷其左右子樹之前。
②LNR：中序遍歷(InorderTraversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間）。
③LRN：後序遍歷(PostorderTraversal)——訪問根結點的操作發生在遍歷其左右子樹之後。注意：由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。

遍歷演算法

1．先（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
2．中（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
3．後（根）序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。

Ⅱ 計算機二級二叉樹前序中序後序

二叉樹遍歷方式是數據結構的基礎知識，作為計算賀團機專業的大學生，我的理解如下：

1、 前序遍歷

它的遍歷順序是：先訪問根結點，再進入這個根結點的左子樹；以上述方式遍歷完所有左子樹後，再進入它的右子樹，以同樣的方式遍歷右子樹中的結點，即根結禪大橘點→左子樹→右子樹。下圖中1為主根結點，245為左子樹，367為右子樹；在左子樹中，2為根結點，4為左子樹，5為右子樹；在右子樹中，3為根結點，6為左子樹，7為右子樹。依次將每個樹中的根結點、左子樹以及右子樹分清，只到子樹中只剩一個元素為止。綜上可知，結果為1→2→4→5→3→6→7。

例題

前序遍歷：A→B→D→F→G→H→I→E→C

中序遍歷：F→D→H→G→I→B→E→A→C

後序遍歷：F→H→I→G→D→E→B→C→A

Ⅲ 數據結構題目二叉樹遍歷，哪位大神幫忙解答下，謝謝！

本題考察二叉樹的遍歷

二叉樹的遍歷一共有4中

1. 前序遍歷
   

2. 中序遍歷

3. 後序遍歷

4. 層序遍歷

略

Ⅳ 如何用二叉樹遍歷所有可能

關於如何使用二叉樹遍歷所有可能（即：所有數據節點）的話，那麼非常簡單：就是在編寫程序的時候設計一個數據結構正確的遞歸子函數，然後使用二賣行叉樹演算法遍歷所有數據節點。
但中此嘩是這里要注意的就是：如果想今後使用二叉樹（或者是遍歷別的數據結構，例如：單鏈表、雙鏈表、或者是多叉樹等），那麼在對數據進行存儲時，就必須要把將來需要訪問遍歷的數據保存成相應的數據格式（例如：單鏈扒旦表、雙鏈表、或者是多叉樹等）。否則的話，如果數據格式不匹配的話，那是無法使用相對應的遍歷演算法進行遍歷的。
關於樹的各種遍歷問題，以根節點位置為標准，包括：前序（根左右）、中序（左根右）、後序（左右根），這個是數據結構上的問題。只要你的數據格式保存正確得當，至於說使用哪一種具體的遍歷方式，那麼肯定都是可以正確訪問的。

Ⅳ 數據結構二叉樹遍歷問題，遍歷方法中右根左(RNL)遍歷的方法可以叫中序遍歷嗎

沒沖弊有右根左的遍歷，只有三種遍歷：
前序遍歷（根左右）：
1.訪問根節點
2.前序遍歷左子樹
3.前序遍歷右子樹肢飢
中序遍歷（左根右）：
1.中序遍歷左子樹
2.訪問根節點
3.中序遍歷歷判返右子樹
後序遍歷（左右根）：
1.後序遍歷左子樹
2.後序遍歷右子樹
3.訪問根節點

Ⅵ 中序遞歸遍歷二叉樹的演算法（數據結構）

有哪位高手幫忙分析下以下程序：#include"iostream.h"
#define
maxnode
100
typedef
char
datatype;
typedef
struct
bitnode{
datatype
data;//存儲數據信息的信息域
struct
bitnode
*lchild,*rchild;//左右孩子指針
}bitnode,*bitree;void
createbitree(bitree
*t){//創建一棵已生成左右子樹的二叉樹的演算法char
ch;cin>>ch;if(ch=='0')(*t)=null;else{(*t)=new
bitnode;
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);}}int
inorderout(bitree
bt)
{//非遞歸中序遍歷二叉樹
bitree
stack[maxnode],p;int
top;if(bt==null)
return
1;//空樹
top=-1;//棧頂指針初始化p=bt;while(!(p==null&&top==-1))
{
while(p!=null)
{
if(top
lchild;//指針指向p的左孩子結點}if(top==-1)
return
1;//棧空時結束else{p=stack[top];//從棧中彈出棧頂元素
cout<
data;top--;p=p->rchild;//指針指向p的右孩子結點}}}void
main()
//主函數{bitree
bt;int
n;cout<<"
***************二叉樹***************"<
>n;switch(n){case
0:break;
case
1:createbitree(&bt);break;case
2:cout<<"中序遍歷輸出二叉樹為：";

Ⅶ 二叉樹的遍歷演算法實現為何要採用遞歸

樹的結構定義本來就是遞歸思想！

Ⅷ 數據結構二叉樹中，如果m是n的祖先,哪種遍歷找到m到n的路徑

後序遍歷。

在後序遍歷退回時訪問根結點，就可以從下向上把從n到m的路徑咐慶上的結點輸出出來，如果採用非遞歸演算法。

當後序遍歷訪問到n時，棧中把從根到n的父指針的路徑上的結點都記憶下來，也可以找到從m到n的路徑。其他遍歷方式都不方便。

二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。

(8)數據結構二叉樹遍歷演算法擴展閱讀：

從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位於第L層，則其子節點位於第L+1層。

按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪旁拍問一次，而且只被訪問一次。由衡啟握於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

Ⅸ 數據結構與演算法-二叉樹(Binary Tree)

    名詞解釋

        節點: 每個元素

        父子關系: 用來連線相鄰節點之間的關系

        父節點: A節點就是B節點的父節點

        子節點:  B節點就是A節點的子節點

        兄弟節點: B、C、D這三個節點的父節點是同一個節點

        根結點: 沒有父節點的節點

        葉子結點: 沒有子節點的節點

        節點的高度: 節點到葉子結點到最長路徑(邊數)  (計數起點為0, 從下往上)

        節點的深度: 根節點到這個節點經歷過的邊個數  (計數起點為0, 從上往下)

        節點的層數:     節點到深度 + 1  (計數起點為1)

        樹的高度: 根節點的高度

    特點

        最常用的樹數據結構

       裂頌 每個節點最多有兩個子節點(左子節點、右子節點)

         滿二叉樹: 葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點

         完全二叉樹:  葉子節點都在最底下兩層，最後一層的葉子節點都 靠左排列 ，並且除了最後一層，其他層的節點個數都要達到最大

        二叉樹存儲方式

            數組順序存儲法

                通過數組下標來順序存儲數據 (i表示當前節點深度,從0開始)

                根節點: i = 1，左節點:2 * i，右節點: 2 * i + 1，父節點: i / 2

                完全二叉樹採用此方式節省內存空間

            鏈式存儲法

                每個節點需要存儲三分數據:當前節點數據、左節點指針、右節點指針,比較佔用空間                

            遍歷

                常用方式

                前序遍歷: 樹任意節點，先列印當前節點，再列印它的左子樹，最後列印它的右子樹

                中序遍歷: 樹任意節點，先列印它的左子樹，再列印當前節點，最後列印它的右子樹

                後序遍歷: 樹任意節點，先列印它的左子樹，再列印它的右子樹，最後列印當前節肆謹鄭點

                二叉樹的前、中、後序遍歷就是一個遞歸的過程

                時間復雜度是O(n)

                    每個節點最多被訪問兩次，遍歷操作的時間復雜度跟節點的個數n成正比

特點

    二叉查找樹為實現快速查找而生，支持快速查找一個數據、快速插入、快速刪除一個數據

    特殊結構: 其左子樹每個節點的值 < 樹的任意一個節點的值 < 其右子樹每個節點的值

            先取根節點，如果它等於要查找的數據，那就返回。

            如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；

            如果要查找的數據比根節點晌悄的值大，那就在右子樹中遞歸查找

            一般插入的數據在葉子節點上，從根節點開始依次比較要插入的數據和節點的大小關系

            如果插入數據比節點的數值大，並且節點的右子樹為空，將新數據插到右子節點位置；

            如果不為空，就再遞歸遍歷右子樹，查找插入位置。

            如果插入數據比節點的數值小，並且節點的左子樹為空，將新數據插到左子節點位置；

            如果不為空，就再遞歸遍歷左子樹，查找插入位置。

        針對要刪除節點的子節點個數的不同，需分三種情況來處理

        1.如果要刪除的節點沒有子節點，步驟如下: (如圖中的刪除節點55)

            只需將父節點中指向要刪除節點的指針置為null

        2.如果要刪除的節點只有一個子節點，步驟如下: (如圖中刪除節點13)

            只需將父節點中指向要刪除節點的指針，讓它指向要刪除節點的子節點即可

        3.如果要刪除的節點有兩個子節點，步驟如下: (如圖中的刪除節點18)

            首先，需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上；

            然後，再刪除掉這個最小節點，因為最小節點肯定沒有左子節點        

            刪除操作，有個優化方案: 就是單純將要刪除的節點標記為「已刪除」，

            這種方案刪除操作就變簡單很多，但是比較浪費內存空間

        支持快速地查找最大節點和最小節點、前驅節點和後繼節點

        另外一種重要特性: 

            中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度為O(n)

            因此，二叉查找樹也叫作二叉排序樹

        以上幾種操作都默認樹中節點存儲的都是數字，而且都是不存在鍵值相同的情況

        實際應用場景中採用對象的某個欄位作為鍵值來構建二叉查找樹，其他欄位稱為衛星數據

        如果存儲的兩個對象鍵值相同，兩種解決方案

        1.把值相同的數據都存儲在同一個節點(採用鏈表或支持動態擴容的數組等數據結構)   

        2.每個節點只存儲一個數據，把這個新插入的數據當作大於這個節點的值來處理，如下圖:

        查找操作

            當查找數據時遇到值相同的節點，繼續在右子樹中查找，直到遇到葉子節點才停止。

            這樣就把鍵值等於要查找值的所有節點都查找出來        

            刪除操作

                先查找到每個要刪除的節點，然後再按前面講的刪除操作的方法，依次刪除

        對於同一組數據可構造不同二叉查找樹。查找、插入、刪除操作的執行效率都不一樣

        圖最左邊樹，根節點的左右子樹極度不平衡，退化成鏈表，查找時間復雜度為O(n)

        最理想的情況，二叉查找樹是一棵完全二叉樹（或滿二叉樹）

        時間復雜度都跟樹的高度成正比，也就是O(height)

        樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示

        滿二叉樹: 下一層節點個數是上一層的2倍，第K層包含節點個數就是2^(K-1)

        完全二叉樹: 假設最大層數是L，總的節點個數n，它包含的節點個數在1個到2^(L-1)個之間

            L的范圍是[ , +1]，完全二叉樹的高度小於等於

            極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求

        平衡二叉查找樹: 樹的高度接近logn，時間復雜度較穩定為O(logn)

    1.排序對比

        散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序

        二叉查找樹只需要中序遍歷，就可以在O(n)的時間復雜度內，輸出有序的數據序列

    2.性能穩定性對比

        散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定

        最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在O(logn)

    3.時間復雜度對比

        散列表查找等操作時間復雜度是常量級，因存在哈希沖突，這個常量不一定比logn小

        另外加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高

    4.結構設計對比

        散列表構造比較復雜，需要考慮:散列函數設計、沖突解決辦法、擴容、縮容等

        平衡二叉查找樹只需要考慮平衡性，而且目前這個的解決方案較成熟、固定

    5.空間復雜度

        散列表: 避免過多散列沖突，裝載因子不能太大，特別基於開放定址法，否則浪費太多空間

            

        

Ⅹ 遍歷二叉樹

遍歷方案：
1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍歷序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
A
/ \
B C
/ / \
D E F
圖
（1） 中序序列（inorder traversal）
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列（postorder traversal）
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
（4）層次遍歷（level traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右訪問每一個結點，從而實現對每一個結點的遍歷
注意：
（1）在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2）上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鏈表的構造
1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】
設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼(遞歸演算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]