专注Java教育14年 全国咨询/投诉热线:444-1124-454
赢咖4LOGO图
始于2009,口口相传的Java黄埔军校
首页 hot资讯 数据结构二叉树遍历类型

数据结构二叉树遍历类型

更新时间:2022-03-29 11:23:22 来源:赢咖4 浏览715次

二叉树的遍历分为三种:

中序树遍历

前序树遍历

后序树遍历

中序树遍历

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

让我们为二叉树的中序遍历编写一个基本的 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 程序来实现常用数据结构中二叉树节点的中序、前序和后序遍历。

提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>