数据结构中的二叉树遍历

2024年8月28日 | 阅读16分钟

树可以被定义为一种非线性数据结构，它以节点的形式存储数据，节点之间通过边相互连接。在所有节点中，有一个主节点称为根节点，所有其他节点都是这些节点的子节点。

在任何数据结构中，遍历都是一项重要的操作。在遍历操作中，我们走遍整个数据结构，至少访问其每个元素一次。在对数据结构执行各种其他操作时，遍历操作扮演着非常重要的角色，例如搜索操作，我们需要至少访问数据结构中的每个元素一次，以便可以将数据结构中的每个传入元素与我们想在数据结构中查找的键进行比较。因此，像任何其他数据结构一样，树数据结构也需要被遍历以访问其每个元素，也称为树数据结构的节点。

根据访问树节点的顺序和用于遍历树的数据结构类型，有不同的遍历树的方法。遍历树涉及到多种数据结构，因为遍历树需要以某种方式迭代所有节点。

由于从一个给定节点出发，可能有不止一种方式来遍历或访问树的下一个节点，因此存储其中一个节点以便进一步遍历，并存储其余具有可能路径的节点以便在需要时回溯树，就变得很重要。回溯不是一种线性方法，所以我们需要不同的数据结构来遍历整棵树。栈和队列是用于遍历树的主要数据结构。

遍历是一种访问树的所有节点并打印其值的技术。遍历树涉及以某种方式迭代所有节点。我们总是从根（头）节点开始，因为所有节点都通过边（链接）连接。由于树不是线性数据结构，从一个给定节点出发，可能存在多个可能的下一个节点，所以一些节点必须被延迟处理，即以某种方式存储以便后续访问。

二叉树的遍历类型

二叉树的遍历有三种类型。

中序树遍历
前序树遍历
后序树遍历

中序树遍历

在这种遍历策略中，首先访问左子树，然后是根节点，最后是右子树。始终要记住，任何节点本身都可以是一个子树。二叉树的中序遍历输出会按升序产生排序后的键值。

C 代码

让我们编写一个用于二叉搜索树中序遍历的基本 C 语言程序。

//C Program for Inorder traversal of the binary search tree
 
#include<stdio.h>
#include<stdlib.h>

struct node
{
    int key;
    struct node *left;
    struct node *right;
};

//return a new node with the given value
struct node *getNode(int val)
{
    struct node *newNode;

    newNode = malloc(sizeof(struct node));

    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}

//inserts nodes in the binary search tree
struct node *insertNode(struct node *root, int val)
{
     if(root == NULL)
         return getNode(val);

     if(root->key < val)
         root->right = insertNode(root->right,val);

     if(root->key > val)
         root->left = insertNode(root->left,val);

     return root;
}

//inorder traversal of the binary search tree
void inorder(struct node *root)
{
    if(root == NULL)
        return;

    //traverse the left subtree
    inorder(root->left);

    //visit the root
    printf("%d ",root->key);

    //traverse the right subtree
    inorder(root->right);
}

int main()
{
   struct node *root = NULL;


    int data;
    char ch;
        /*  Do while loop to display various options to select from to decide the input  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Binary Tree");
            printf("\n2. To display the nodes of the Binary Tree(via Inorder Traversal).\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value to be inserted\n");
                scanf("%d",&data);
                root = insertNode(root,data);                  
                break;                          
            case 2 : 
                printf("\nInorder Traversal of the Binary Tree::\n");
                inorder(root);
                break; 
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y');

   return 0;
}

输出

上述 C 代码产生以下输出。

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree (via Inorder Traversal).
1

Enter the value to be inserted
12

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
1

Enter the value to be inserted
98

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
1

Enter the value to be inserted
23

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
1

Enter the value to be inserted
78

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
1

Enter the value to be inserted
45

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
1

Enter the value to be inserted
87

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Inorder Traversal).
2

Inorder Traversal of the Binary Tree::
12 23 45 78 87 98 
Do you want to continue (Type y or n)
n

前序树遍历

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

代码

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

/*
 * Program: Preorder traversal of the binary search tree
 * Language: C
 */

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int key;
    struct node *left;
    struct node *right;
};

//return a new node with the given value
struct node *getNode(int val)
{
    struct node *newNode;

    newNode = malloc(sizeof(struct node));

    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}

//inserts nodes in the binary search tree
struct node *insertNode(struct node *root, int val)
{
     if(root == NULL)
         return getNode(val);

     if(root->key < val)
         root->right = insertNode(root->right,val);

     if(root->key > val)
         root->left = insertNode(root->left,val);

     return root;
}

//preorder traversal of the binary search tree
void preorder(struct node *root)
{
    if(root == NULL)
        return;

    //visit the root
    printf("%d ",root->key);

    //traverse the left subtree
    preorder(root->left);

    //traverse the right subtree
    preorder(root->right);
}

int main()
{
   struct node *root = NULL;

   int data;
    char ch;
        /*  Do while loop to display various options to select from to decide the input  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Binary Tree");
            printf("\n2. To display the nodes of the Binary Tree(via Preorder Traversal).\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value to be inserted\n");
                scanf("%d",&data);
                root = insertNode(root,data);                  
                break;                          
            case 2 : 
                printf("\nPreorder Traversal of the Binary Tree::\n");
                preorder(root);
                break; 
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y');
  
   return 0;
}

输出

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
45

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
53

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
1

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
2

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
97

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
22

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
2

Preorder Traversal of the Binary Tree::
45 1 2 22 53 97 
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
76

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
30

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
67

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
1

Enter the value to be inserted
4

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
2

Preorder Traversal of the Binary Tree::
45 1 2 22 4 30 53 97 76 67 
Do you want to continue (Type y or n)
n

后序树遍历

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

代码

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

/*
 * Program: Postorder traversal of the binary search tree
 * Language: C
 */

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int key;
    struct node *left;
    struct node *right;
};

//return a new node with the given value
struct node *getNode(int val)
{
    struct node *newNode;

    newNode = malloc(sizeof(struct node));

    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}
//inserts nodes in the binary search tree
struct node *insertNode(struct node *root, int val)
{
     if(root == NULL)
         return getNode(val);

     if(root->key < val)
         root->right = insertNode(root->right,val);

     if(root->key > val)
         root->left = insertNode(root->left,val);

     return root;
}

//postorder traversal of the binary search tree
void postorder(struct node *root)
{
    if(root == NULL)
        return;

    //traverse the left subtree
    postorder(root->left);

    //traverse the right subtree
    postorder(root->right);

    //visit the root
    printf("%d ",root->key);
}
int main()
{
   struct node *root = NULL;

   
   int data;
    char ch;
        /*  Do while loop to display various options to select from to decide the input  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Binary Tree");
            printf("\n2. To display the nodes of the Binary Tree(via Postorder Traversal).\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value to be inserted\n");
                scanf("%d",&data);
                root = insertNode(root,data);                  
                break;                          
            case 2 : 
                printf("\nPostorder Traversal of the Binary Tree::\n");
                postorder(root);
                break; 
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y');

   return 0;
}

输出

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
12

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
31

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
24
Wrong Entry

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
24

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
88

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
67

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
56

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
90

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
44

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
71

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
38

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
29

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Postorder Traversal).
2

Postorder Traversal of the Binary Tree::
29 24 38 44 56 71 67 90 88 31 12 
Do you want to continue (Type y or n)
n

我们已经看到了实现二叉树节点中序、前序和后序遍历的不同 C 语言程序。现在让我们编写一个程序，在单个程序中执行所有三种类型的遍历。

代码

//Binary tree traversal:
 
#include <stdio.h>
// #include <conio.h>
#include <malloc.h>
struct node
{
    struct node *left;
    int data;
    struct node *right;
};
 
void main()
{
    void insert(struct node **,int);
    void inorder(struct node *);
    void postorder(struct node *);
    void preorder(struct node *);
 
    struct node *ptr = NULL;
    int no,i,num;
 
    // ptr = NULL;
    // ptr->data=0;
    
    int data;
    char ch;
        /*  Do while loop to display various options to select from to decide the input  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Binary Tree");
            printf("\n2. To display the nodes of the Binary Tree(via Preorder Traversal).");
            printf("\n3. To display the nodes of the Binary Tree(via Inorder Traversal).");
            printf("\n4. To display the nodes of the Binary Tree(via Postorder Traversal).\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value to be inserted\n");
                scanf("%d",&data);
                insert(&ptr,data);                  
                break;                          
            case 2 : 
                printf("\nPreorder Traversal of the Binary Tree::\n");
                preorder(ptr);
                break;
            case 3 : 
                printf("\nInorder Traversal of the Binary Tree::\n");
                inorder(ptr);
                break;
            case 4 : 
                printf("\nPostorder Traversal of the Binary Tree::\n");
                postorder(ptr);
                break; 
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y');
 
    
    // printf("\nProgram for Tree Traversal\n");
    // printf("Enter the number of nodes to add to the tree.<BR>\n");
    // scanf("%d",&no);
 
    // for(i=0;i<no;i++)
    // {
    //     printf("Enter the item\n");
    //     scanf("%d",&num);
    //     insert(&ptr,num);
    // }
 
    // //getch();
    // printf("\nINORDER TRAVERSAL\n");
    // inorder(ptr);
 
    // printf("\nPREORDER TRAVERSAL\n");
    // preorder(ptr);
 
    // printf("\nPOSTORDER TRAVERSAL\n");
    // postorder(ptr);
 
}
 
void insert(struct node **p,int num)
{
    if((*p)==NULL)
    {
        printf("Leaf node created.");
        (*p)=malloc(sizeof(struct node));
        (*p)->left = NULL;
        (*p)->right = NULL;
        (*p)->data = num;
        return;
    }
    else
    {
        if(num==(*p)->data)
        {
            printf("\nREPEATED ENTRY ERROR VALUE REJECTED\n");
            return;
        }
        if(num<(*p)->data)
        {
            printf("\nDirected to left link.\n");
            insert(&((*p)->left),num);
        }
        else
        {
            printf("Directed to right link.\n");
            insert(&((*p)->right),num);
        }
    }
    return;
}
 
void inorder(struct node *p)
{
    if(p!=NULL)
    {
        inorder(p->left);
        printf("%d ",p->data);
        inorder(p->right);
    }
    else
    return;
}
 
void preorder(struct node *p)
{
    if(p!=NULL)
    {
        printf("%d ",p->data);
        preorder(p->left);
        preorder(p->right);
    }
    else
    return;
}
 
void postorder(struct node *p)
{
    if(p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        printf("%d ",p->data);
    }
    else
    return;
}

输出

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
2
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
5
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
7
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
Y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
9
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
31
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
1

Enter the value to be inserted
78
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Directed to right link.
Leaf node created.
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
2

Preorder Traversal of the Binary Tree::
2 5 7 9 31 78 
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
3

Inorder Traversal of the Binary Tree::
2 5 7 9 31 78 
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Binary Tree
2. To display the nodes of the Binary Tree(via Preorder Traversal).
3. To display the nodes of the Binary Tree(via Inorder Traversal).
4. To display the nodes of the Binary Tree(via Postorder Traversal).
4

Postorder Traversal of the Binary Tree::
78 31 9 7 5 2 
Do you want to continue (Type y or n)
n

结论

因此，在本文中，我们理解了二叉树遍历以及不同类型的二叉树遍历，如中序二叉树遍历、前序二叉树遍历和后序二叉树遍历。我们还对所有这些类型的树遍历进行了编程实现。在文章的最后一部分，我们还理解了如何实现一个基本的 C 语言程序，该程序可用于在单个文件中实现所有三种类型的树遍历。

下一个主题数据结构中的队列操作

数据结构中的二叉树遍历

二叉树的遍历类型

中序树遍历

前序树遍历

后序树遍历

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的二叉树遍历

二叉树的遍历类型

中序树遍历

前序树遍历

后序树遍历

结论

相关帖子

如何知道一个数组是否是双峰的

从 2D 矩阵构建链表

检查字符串的某个回文排列是否存在

对存储在不同机器上的数字进行排序

查找数据结构中所有好字符串的问题

一种生成 1 到 n 的二进制数的有趣方法

稀疏集

二叉树的层序遍历

二叉树的直径

K 中心问题 (贪心近似算法)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器