二叉樹的遍歷分為三種：

中序樹遍歷

前序樹遍歷

后序樹遍歷

中序樹遍歷

在這種遍歷策略中，首先訪問(wèn)左子樹，然后是根，最后是右子樹。請(qǐng)始終牢記，任何節(jié)點(diǎn)都可能是其自身的子樹。按順序遍歷二叉樹的輸出產(chǎn)生按升序排序的鍵值。

讓我們?yōu)?a href="/hot/996.html" target="_blank" title="淺談二叉樹中序遍歷">二叉樹的中序遍歷編寫一個(gè)基本的 C 程序。

//二叉搜索樹中序遍歷的C程序     
#include<stdio.h>  
#include<stdlib.h>    
結(jié)構(gòu) 節(jié)點(diǎn)  
{  
    整數(shù) 鍵；  
    結(jié)構(gòu) 節(jié)點(diǎn)*左；  
    結(jié)構(gòu) 節(jié)點(diǎn)*對(duì)；  
};    
//返回具有給定值的新節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn) *getNode( int  val)  
{  
    結(jié)構(gòu) 節(jié)點(diǎn) *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新節(jié)點(diǎn)->左= NULL；  
    新節(jié)點(diǎn)->右=空；    
    返回 新節(jié)點(diǎn)；  
}    
//在二叉搜索樹中插入節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn)*插入節(jié)點(diǎn)（結(jié)構(gòu) 節(jié)點(diǎn)*根，  int  val）  
{  
     如果（根 == NULL）  
         返回 getNode(val);    
     if (root->key < val)  
         root->right = insertNode(root->right,val);    
     if (root->key > val)  
         root->left = insertNode(root->left,val);    
     返回 根；  
}    
//二叉搜索樹的中序遍歷  
無(wú)效 順序（結(jié)構(gòu) 節(jié)點(diǎn)*根）  
{  
    如果（根 == NULL）  
        返回；    
    //遍歷左子樹  
    中序（根->左）；    
    //訪問(wèn)根  
    printf( "%d" ,root->key);    
    //遍歷右子樹  
    中序（根-> 右）；  
}    
主函數(shù) （）  
{  
   結(jié)構(gòu) 節(jié)點(diǎn) *root = NULL;      
    整數(shù) 數(shù)據(jù)；  
    字符 ch;  
        /* 執(zhí)行 while 循環(huán)以顯示各種選項(xiàng)以供選擇以決定輸入 */  
        做      
        {  
            printf( "\n選擇其中一項(xiàng)操作::" );  
            printf( "\n1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)" );  
            printf( "\n2. 顯示二叉樹的節(jié)點(diǎn)(通過(guò)中序遍歷).\n" );    
            整數(shù) 選擇；  
            scanf( "%d" ,&choice);              
            開關(guān) （選擇）  
            {  
            案例 1：   
                printf( "\n輸入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入節(jié)點(diǎn)（根，數(shù)據(jù)）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉樹的中序遍歷::\n" );  
                有序（根）；  
                休息;   
            默認(rèn) ：   
                printf( "輸入錯(cuò)誤\n" );  
                休息;     
            }    
            printf( "\n你想繼續(xù)嗎(輸入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );  
  
   返回 0；  
}  

輸出

上面的 C 代碼配置了以下輸出。

選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2. 顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
12
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
98
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
23
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
78
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
45
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
1
輸入要插入的值
87
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)中序遍歷）。
2
二叉樹的中序遍歷::
12 23 45 78 87 98
您要繼續(xù)嗎（鍵入 y 或 n）
n

前序樹遍歷

在這種遍歷方法中，首先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左子樹，最后訪問(wèn)右子樹。

讓我們?yōu)槎嫠阉鳂涞那靶虮闅v編寫一個(gè) C 代碼。

/* 
 * 程序：二叉搜索樹的前序遍歷 
 * 語(yǔ)言：C 
 */    
#include<stdio.h>  
#include<stdlib.h>    
結(jié)構(gòu) 節(jié)點(diǎn)  
{  
    整數(shù) 鍵；  
    結(jié)構(gòu) 節(jié)點(diǎn)*左；  
    結(jié)構(gòu) 節(jié)點(diǎn)*對(duì)；  
};    
//返回具有給定值的新節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn) *getNode( int  val)  
{  
    結(jié)構(gòu) 節(jié)點(diǎn) *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新節(jié)點(diǎn)->左= NULL；  
    新節(jié)點(diǎn)->右=空；    
    返回 新節(jié)點(diǎn)；  
}    
//在二叉搜索樹中插入節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn)*插入節(jié)點(diǎn)（結(jié)構(gòu) 節(jié)點(diǎn)*根，  int  val）  
{  
     如果（根 == NULL）  
         返回 getNode(val);    
     if (root->key < val)  
         root->right = insertNode(root->right,val);    
     if (root->key > val)  
         root->left = insertNode(root->left,val);    
     返回 根；  
}    
//二叉搜索樹的前序遍歷  
無(wú)效 預(yù)購(gòu)（結(jié)構(gòu) 節(jié)點(diǎn)*根）  
{  
    如果（根 == NULL）  
        返回；    
    //訪問(wèn)根  
    printf( "%d" ,root->key);    
    //遍歷左子樹  
    預(yù)購(gòu)（根->左）；    
    //遍歷右子樹  
    預(yù)購(gòu)（根->右）；  
}    
主函數(shù) （）  
{  
   結(jié)構(gòu) 節(jié)點(diǎn) *root = NULL;    
   整數(shù) 數(shù)據(jù)；  
    字符 ch;  
        /* 執(zhí)行 while 循環(huán)以顯示各種選項(xiàng)以供選擇以決定輸入 */  
        做      
        {  
            printf( "\n選擇其中一項(xiàng)操作::" );  
            printf( "\n1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)" );  
            printf( "\n2. 顯示二叉樹的節(jié)點(diǎn)(通過(guò)前序遍歷).\n" );    
            整數(shù) 選擇；  
            scanf( "%d" ,&choice);              
            開關(guān) （選擇）  
            {  
            案例 1：   
                printf( "\n輸入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入節(jié)點(diǎn)（根，數(shù)據(jù)）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉樹的前序遍歷::\n" );  
                預(yù)購(gòu)（根）；  
                休息;   
            默認(rèn) ：   
                printf( "輸入錯(cuò)誤\n" );  
                休息;     
            }    
            printf( "\n你想繼續(xù)嗎(輸入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );      
   返回 0；  
}  

輸出：

選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
45
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
53
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
1
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
2
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
97
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
22
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
2
二叉樹的前序遍歷::
45 1 2 22 53 97
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
76
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
30
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
67
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
1
輸入要插入的值
4
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)前序遍歷）。
2
二叉樹的前序遍歷::
45 1 2 22 4 30 53 97 76 67
您要繼續(xù)嗎（鍵入 y 或 n）
n

后序樹遍歷

在這種遍歷方法中，根節(jié)點(diǎn)最后被訪問(wèn)，因此得名。首先，我們遍歷左子樹，然后是右子樹，最后是根節(jié)點(diǎn)。

讓我們編寫一個(gè)用于二叉搜索樹的后序遍歷的程序。

/* 
 * 程序：二叉搜索樹的后序遍歷 
 * 語(yǔ)言：C 
 */    
#include<stdio.h>  
#include<stdlib.h>    
結(jié)構(gòu) 節(jié)點(diǎn)  
{  
    整數(shù) 鍵；  
    結(jié)構(gòu) 節(jié)點(diǎn)*左；  
    結(jié)構(gòu) 節(jié)點(diǎn)*對(duì)；  
};    
//返回具有給定值的新節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn) *getNode( int  val)  
{  
    結(jié)構(gòu) 節(jié)點(diǎn) *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新節(jié)點(diǎn)->左= NULL；  
    新節(jié)點(diǎn)->右=空；    
    返回 新節(jié)點(diǎn)；  
}  
//在二叉搜索樹中插入節(jié)點(diǎn)  
結(jié)構(gòu) 節(jié)點(diǎn)*插入節(jié)點(diǎn)（結(jié)構(gòu) 節(jié)點(diǎn)*根，  int  val）  
{  
     如果（根 == NULL）  
         返回 getNode(val);    
     if (root->key < val)  
         root->right = insertNode(root->right,val);    
     if (root->key > val)  
         root->left = insertNode(root->left,val);    
     返回 根；  
}   
//二叉搜索樹的后序遍歷  
無(wú)效 后序（結(jié)構(gòu) 節(jié)點(diǎn)*根）  
{  
    如果（根 == NULL）  
        返回；    
    //遍歷左子樹  
    后序（根->左）；    
    //遍歷右子樹  
    后序（根->右）；    
    //訪問(wèn)根  
    printf( "%d" ,root->key);  
}  
主函數(shù) （）  
{  
   結(jié)構(gòu) 節(jié)點(diǎn) *root = NULL;         
   整數(shù) 數(shù)據(jù)；  
    字符 ch;  
        /* 執(zhí)行 while 循環(huán)以顯示各種選項(xiàng)以供選擇以決定輸入 */  
        做      
        {  
            printf( "\n選擇其中一項(xiàng)操作::" );  
            printf( "\n1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)" );  
            printf( "\n2. 顯示二叉樹的節(jié)點(diǎn)(通過(guò)后序遍歷).\n" );   
            整數(shù) 選擇；  
            scanf( "%d" ,&choice);              
            開關(guān) （選擇）  
            {  
            案例 1：   
                printf( "\n輸入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入節(jié)點(diǎn)（根，數(shù)據(jù)）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉樹的后序遍歷::\n" );  
                后序（根）；  
                休息;   
            默認(rèn) ：   
                printf( "輸入錯(cuò)誤\n" );  
                休息;     
            }    
            printf( "\n你想繼續(xù)嗎(輸入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );    
   返回 0；  
}  

輸出：

選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
12
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
31
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
24
輸入錯(cuò)誤
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
24
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
88
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
67
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
56
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
90
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
44
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
71
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
38
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
1
輸入要插入的值
29
您要繼續(xù)嗎（鍵入 y 或 n）
是的
選擇其中一項(xiàng)操作::
1. 在二叉樹中插入一個(gè)新節(jié)點(diǎn)
2.顯示二叉樹的節(jié)點(diǎn)（通過(guò)后序遍歷）。
2
二叉樹的后序遍歷::
29 24 38 44 56 71 67 90 88 31 12
您要繼續(xù)嗎（鍵入 y 或 n）
n

我們已經(jīng)看到了不同的 C 程序來(lái)實(shí)現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)中二叉樹節(jié)點(diǎn)的中序、前序和后序遍歷。