数据结构二叉树遍历类型

二叉树的遍历分为三种：

中序树遍历

前序树遍历

后序树遍历

中序树遍历

在这种遍历策略中，首先访问左子树，然后是根，最后是右子树。请始终牢记，任何节点都可能是其自身的子树。按顺序遍历二叉树的输出产生按升序排序的键值。

让我们为二叉树的中序遍历编写一个基本的 C 程序。

//二叉搜索树中序遍历的C程序     
#include<stdio.h>  
#include<stdlib.h>    
结构 节点  
{  
    整数 键；  
    结构 节点*左；  
    结构 节点*对；  
};    
//返回具有给定值的新节点  
结构 节点 *getNode( int  val)  
{  
    结构 节点 *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新节点->左= NULL；  
    新节点->右=空；    
    返回 新节点；  
}    
//在二叉搜索树中插入节点  
结构 节点*插入节点（结构 节点*根，  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);    
     返回 根；  
}    
//二叉搜索树的中序遍历  
无效 顺序（结构 节点*根）  
{  
    如果（根 == NULL）  
        返回；    
    //遍历左子树  
    中序（根->左）；    
    //访问根  
    printf( "%d" ,root->key);    
    //遍历右子树  
    中序（根-> 右）；  
}    
主函数 （）  
{  
   结构 节点 *root = NULL;      
    整数 数据；  
    字符 ch;  
        /* 执行 while 循环以显示各种选项以供选择以决定输入 */  
        做      
        {  
            printf( "\n选择其中一项操作::" );  
            printf( "\n1. 在二叉树中插入一个新节点" );  
            printf( "\n2. 显示二叉树的节点(通过中序遍历).\n" );    
            整数 选择；  
            scanf( "%d" ,&choice);              
            开关 （选择）  
            {  
            案例 1：   
                printf( "\n输入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入节点（根，数据）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉树的中序遍历::\n" );  
                有序（根）；  
                休息;   
            默认 ：   
                printf( "输入错误\n" );  
                休息;     
            }    
            printf( "\n你想继续吗(输入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );  
  
   返回 0；  
}  

输出

上面的 C 代码配置了以下输出。

选择其中一项操作::
1. 在二叉树中插入一个新节点
2. 显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
12
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
98
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
23
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
78
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
45
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
1
输入要插入的值
87
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过中序遍历）。
2
二叉树的中序遍历::
12 23 45 78 87 98
您要继续吗（键入 y 或 n）
n

前序树遍历

在这种遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。

让我们为二叉搜索树的前序遍历编写一个 C 代码。

/* 
 * 程序：二叉搜索树的前序遍历 
 * 语言：C 
 */    
#include<stdio.h>  
#include<stdlib.h>    
结构 节点  
{  
    整数 键；  
    结构 节点*左；  
    结构 节点*对；  
};    
//返回具有给定值的新节点  
结构 节点 *getNode( int  val)  
{  
    结构 节点 *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新节点->左= NULL；  
    新节点->右=空；    
    返回 新节点；  
}    
//在二叉搜索树中插入节点  
结构 节点*插入节点（结构 节点*根，  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);    
     返回 根；  
}    
//二叉搜索树的前序遍历  
无效 预购（结构 节点*根）  
{  
    如果（根 == NULL）  
        返回；    
    //访问根  
    printf( "%d" ,root->key);    
    //遍历左子树  
    预购（根->左）；    
    //遍历右子树  
    预购（根->右）；  
}    
主函数 （）  
{  
   结构 节点 *root = NULL;    
   整数 数据；  
    字符 ch;  
        /* 执行 while 循环以显示各种选项以供选择以决定输入 */  
        做      
        {  
            printf( "\n选择其中一项操作::" );  
            printf( "\n1. 在二叉树中插入一个新节点" );  
            printf( "\n2. 显示二叉树的节点(通过前序遍历).\n" );    
            整数 选择；  
            scanf( "%d" ,&choice);              
            开关 （选择）  
            {  
            案例 1：   
                printf( "\n输入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入节点（根，数据）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉树的前序遍历::\n" );  
                预购（根）；  
                休息;   
            默认 ：   
                printf( "输入错误\n" );  
                休息;     
            }    
            printf( "\n你想继续吗(输入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );      
   返回 0；  
}  

输出：

选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
45
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
53
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
1
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
2
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
97
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
22
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
2
二叉树的前序遍历::
45 1 2 22 53 97
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
76
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
30
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
67
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
1
输入要插入的值
4
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过前序遍历）。
2
二叉树的前序遍历::
45 1 2 22 4 30 53 97 76 67
您要继续吗（键入 y 或 n）
n

后序树遍历

在这种遍历方法中，根节点最后被访问，因此得名。首先，我们遍历左子树，然后是右子树，最后是根节点。

让我们编写一个用于二叉搜索树的后序遍历的程序。

/* 
 * 程序：二叉搜索树的后序遍历 
 * 语言：C 
 */    
#include<stdio.h>  
#include<stdlib.h>    
结构 节点  
{  
    整数 键；  
    结构 节点*左；  
    结构 节点*对；  
};    
//返回具有给定值的新节点  
结构 节点 *getNode( int  val)  
{  
    结构 节点 *newNode;    
    newNode = malloc( sizeof ( struct  node));    
    newNode->key = val;  
    新节点->左= NULL；  
    新节点->右=空；    
    返回 新节点；  
}  
//在二叉搜索树中插入节点  
结构 节点*插入节点（结构 节点*根，  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);    
     返回 根；  
}   
//二叉搜索树的后序遍历  
无效 后序（结构 节点*根）  
{  
    如果（根 == NULL）  
        返回；    
    //遍历左子树  
    后序（根->左）；    
    //遍历右子树  
    后序（根->右）；    
    //访问根  
    printf( "%d" ,root->key);  
}  
主函数 （）  
{  
   结构 节点 *root = NULL;         
   整数 数据；  
    字符 ch;  
        /* 执行 while 循环以显示各种选项以供选择以决定输入 */  
        做      
        {  
            printf( "\n选择其中一项操作::" );  
            printf( "\n1. 在二叉树中插入一个新节点" );  
            printf( "\n2. 显示二叉树的节点(通过后序遍历).\n" );   
            整数 选择；  
            scanf( "%d" ,&choice);              
            开关 （选择）  
            {  
            案例 1：   
                printf( "\n输入要插入的值\n" );  
                scanf( "%d" ,&data);  
                根=插入节点（根，数据）；                    
                休息;                            
            案例 2：   
                printf( "\n二叉树的后序遍历::\n" );  
                后序（根）；  
                休息;   
            默认 ：   
                printf( "输入错误\n" );  
                休息;     
            }    
            printf( "\n你想继续吗(输入y或n)\n" );  
            scanf( "%c" ,&ch);                          
        } 而 (ch ==  'Y' || ch ==  'y' );    
   返回 0；  
}  

输出：

选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
12
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
31
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
24
输入错误
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
24
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
88
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
67
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
56
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
90
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
44
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
71
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
38
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
1
输入要插入的值
29
您要继续吗（键入 y 或 n）
是的
选择其中一项操作::
1. 在二叉树中插入一个新节点
2.显示二叉树的节点（通过后序遍历）。
2
二叉树的后序遍历::
29 24 38 44 56 71 67 90 88 31 12
您要继续吗（键入 y 或 n）
n

我们已经看到了不同的 C 程序来实现常用数据结构中二叉树节点的中序、前序和后序遍历。