map遍历顺序和保存顺序_树遍历–顺序，预顺序和后顺序

- 日理万妓 2022-12-07 12:58 190阅读 0赞

![7d1849d4b2ea7d6806a512cdc0246553.png][]

map遍历顺序和保存顺序

Here you will learn about tree traversal with program example.

在这里，您将通过程序示例了解有关树遍历的信息。

**Tree** is a subset of Graph data structure where the number of edges are exactly one less than the number of vertices (nodes). We can call any graph a tree if it does not have any cycle (closed loop).

**树**是图数据结构的子集，其中边的数量比顶点(节点)的数量少一。 如果任何图没有任何循环(闭环)，我们可以称其为树。

**Tree traversal** refers to the process of visiting each node of the tree at least once. Unlike basic linear data structures like arrays, linked list, stack and queue where there was only one way of traversing, trees can be traversed in different ways.

**树遍历**是指至少访问树的每个节点一次的过程。 与只有一种遍历方式的基本线性数据结构(如数组，链表，堆栈和队列)不同，可以以不同的方式遍历树。

We can categorize the tree traversal into two categories:

我们可以将树遍历分为两类：

1.  Breadth-first Traversal
    
    广度优先遍历
2.  Depth-first Traversal
    
    深度优先遍历

## 深度优先遍历 **(**Depth-first Traversal**)** ##

In Depth-first traversal, the direction of traversal is from top to bottom. As the name suggests, we traverse to the depth of the tree starting from the root node of the tree. Based on the way of traversal, we have these three types of traversals:

在深度优先遍历中，遍历的方向是从上到下。 顾名思义，我们从树的根节点开始遍历树的深度。 基于遍历的方式，我们有以下三种遍历类型：

*  In-order Traversal
    
    有序遍历
 *  Pre-order Traversal
    
    预购遍历
 *  Post-order Traversal
    
    订单遍历

These three types of traversal are usually performed on binary trees. Binary tree is a special type of tree in which a parent node can have at most two child nodes. Binary Search Tree (BST) is a special binary tree where every smaller value is on the left of the parent node and every greater value is on the right of the parent node.

这三种遍历通常在二叉树上执行。 二叉树是一种特殊类型的树，其中父节点最多可以有两个子节点。 二进制搜索树(BST)是一种特殊的二进制树，其中每个较小的值在父节点的左侧，每个较大的值在父节点的右侧。

![Binary Tree][]

Let’s see these traversals in detail.

让我们详细了解这些遍历。

### 有序遍历 **(**In-order Traversal**)** ###

As the name suggest, in in-order traversal we traverse the tree in the order that we humans normally use. We first visit the left subtree after that we visit the parent of the left subtree and then we visit the right subtree. When we use in-order traversal on a Binary Search Tree (BST), we get the data in sorted order (ascending order).

顾名思义，在有序遍历中，我们按照人类通常使用的顺序遍历了树。 我们先访问左子树，然后再访问左子树的父级，然后访问右子树。 当我们在二叉搜索树(BST)上使用有序遍历时，我们以排序顺序(升序)获得数据。

**Algorithm for In-order Traversal**

**有序遍历算法**

1.  *Check that the current node is not null, if null return to the previous call.*
    
    *检查当前节点是否不为null，如果为null，则返回上一个调用。*
2.  *Make recursive call to the in-order function for traversing the left subtree.*
    
    *递归调用顺序函数以遍历左侧子树。*
3.  *Print the value of the current node.*
    
    *打印当前节点的值。*
4.  *Make recursive call to the in-order function for traversing the right subtree.*
    
    *递归调用顺序函数以遍历正确的子树。*

### 预购遍历 **(**Pre-order Traversal**)** ###

Pre-order traversal is the type of traversal in which we first visit the root node of the tree. After the root node, we visit the left subtree and finally we visit the right subtree. The Pre-order traversal is mainly used to create a copy of the existing tree. It is also used in the evaluation of expressions, for example: we can create a prefix form of an expression using the pre-order traversal.

顺序遍历是我们首先访问树的根节点的遍历类型。 在根节点之后，我们访问左侧的子树，最后访问右侧的子树。 Pre-order遍历主要用于创建现有树的副本。 例如，它也可用于表达式的求值：我们可以使用前置遍历创建表达式的前缀形式。

**Algorithm for Pre-order Traversal**

**顺序遍历算法**

1.  *Check that the current node is not null, if null return to the previous call.*
    
    *检查当前节点是否不为null，如果为null，则返回上一个调用。*
2.  *Print the value of the current node.*
    
    *打印当前节点的值。*
3.  *Make recursive call to the pre-order function for traversing the left subtree.*
    
    *递归调用pre-order函数以遍历左侧子树。*
4.  *Make recursive call to the pre-order function for traversing the right subtree.*
    
    *递归调用pre-order函数以遍历正确的子树。*

### 订单遍历 **(**Post-order Traversal**)** ###

In Post-order Traversal, the tree is traversed in the order of left->right->root. That means we first visit the left subtree after that we visit the right subtree and finally we visit the root node. The Post-order traversal is used during deletion of the tree. It is suitable for deletion operation because it first deletes the child nodes then it deletes the parent node.

在后序遍历中，以左->右->根的顺序遍历树。 这意味着我们首先访问左子树，然后访问右子树，最后访问根节点。 在删除树的过程中使用后顺序遍历。 它适用于删除操作，因为它首先删除子节点，然后删除父节点。

**Algorithm for Post-order Traversal**

**后遍历算法**

1.  *Check that the current node is not null, if null return to the previous call.*
    
    *检查当前节点是否不为null，如果为null，则返回上一个调用。*
2.  *Make recursive call to the post-order function for traversing the left subtree.*
    
    *递归调用后顺序函数以遍历左侧子树。*
3.  *Make recursive call to the post-order function for traversing the right subtree.*
    
    *递归调用后置函数以遍历正确的子树。*
4.  *Print the value of the current node.*
    
    *打印当前节点的值。*

## 广度优先遍历 **(**Breadth-first Traversal**)** ##

The Breadth-first traversal is usually used in graphs but not commonly used in trees. It is also called **Level-order traversal**. When we traverse a tree using level-order traversal, we visit all the nodes of tree level by level. We first visit all the nodes of the current level before visiting the nodes of the next level. The number of nodes keeps increasing as we go to the next level, so the name breadth-first traversal is given as the breadth keep broadening as we traverse the height of the tree.

广度优先遍历通常在图形中使用，但在树中则不常用。 也称为**Level-order遍历** 。 当我们使用级别顺序遍历遍历树时，我们逐级访问树的所有节点。 我们首先访问当前级别的所有节点，然后再访问下一级别的节点。 随着我们进入下一个级别，节点的数量一直在增加，因此名称广度优先遍历是因为当我们遍历树的高度时宽度不断扩大。

**Implementation of the In-order, pre-order & post-order Traversal in C++**

**用C ++实现有序，前序和后序遍历**

#include<bits/stdc++.h>
     
    using namespace std;
     
    /* Creating structure for nodes */
    struct node
    {
    	int value;
    	node *left,*right;
    };
     
    /* creating a class to manage the binary tree */
    class btree
    {
    	void insert(int,node*);  // private member function
    	
    public:
    	node *root;	
    	btree();   //constructor
    	~btree();  //destructor
    	void insert(int);
    	void inorder(node*);
    	void preorder(node*);
    	void postorder(node*);
    };
     
    btree::btree()
    {
    	root=NULL;  // intializing the root
    }
     
    btree::~btree()
    {
    	cout<<"\nDestructor executed!!";
    }
     
    void btree::insert(int key)
    {
    	
    	if(!(root==NULL))  
    	{
    		/* if the tree is not empty */
    		insert(key,root);
    	}
    	
    	else
    	{
    		/* if tree is empty */
    		root=new node;
    		root->value=key;
    		root->left=NULL;
    		root->right=NULL;
    	}
    }
     
    /* preserving the properties of binary tree */
    void btree::insert(int key,node *leaf)
    {
    	if(key<leaf->value)
    	{
    		if(leaf->left==NULL)
    		{
    			leaf->left= new node;
    			leaf->left->value=key;
    			leaf->left->left=NULL;
    			leaf->left->right=NULL;
    		}
    		
    		else
    		{
    			insert(key,leaf->left);
    		}
    	}
    	
    	else
    	{
    		if(leaf->right==NULL)
    		{
    			leaf->right= new node;
    			leaf->right->value=key;
    			leaf->right->left=NULL;
    			leaf->right->right=NULL;
    		}
    		
    		else
    		{
    			insert(key,leaf->right);
    		}
    	}
    }
     
    /* recursive implmentation of in-order traversal*/
    void btree::inorder(node *leaf)
    {
    	if(leaf!=NULL)
    	{
    		inorder(leaf->left);
    		cout<<leaf->value<<" ";
    		inorder(leaf->right);
    	}
    }
     
    /* recursive implmentation of pre-order traversal*/
    void btree::preorder(node *leaf)
    {
    	if(leaf!=NULL)
    	{
    		cout<<leaf->value<<" ";
    		preorder(leaf->left);
    		preorder(leaf->right);
    	}
    }
     
    /* recursive implmentation of post-order traversal*/
    void btree::postorder(node *leaf)
    {
    	if(leaf!=NULL)
    	{
    		postorder(leaf->left);
    		postorder(leaf->right);
    		cout<<leaf->value<<" ";
    	}
    }
     
    int main()
    {
    	btree b;  // creating object of class
    	int arr[]={10,6,12,3,8,11,14,5};
    	
    	for(int i=0;i<8;i++)
    	b.insert(arr[i]); //inserting values
    	
    	/* call to inorder traversal*/
    	cout<<"The inorder traversal is : ";
    	b.inorder(b.root); 
    	
    	/* call to preorder traversal*/
    	cout<<"\nThe preorder traversal is: ";
    	b.preorder(b.root); 
    	
    	/* call to postorder traversal*/
    	cout<<"\nThe postorder traversal is: ";
    	b.postorder(b.root); 
    	
    	return 0;
    }

**Output:**

**输出：**

*The inorder traversal is : 3 5 6 8 10 11 12 14*  *The preorder traversal is: 10 6 3 5 8 12 11 14*  *The postorder traversal is: 5 3 8 6 11 14 12 10*  *Destructor executed!!*

*顺序遍历为：3 5 6 8 10 11 12 14* *预先遍历为：10 6 3 5 8 12 11 14* *后期遍历为：5 3 8 6 11 14 12 10* *执行了析构* *函数* *！*

Comment down below if you have any queries related to tree traversal.

如果您有关于树遍历的任何查询，请在下面注释掉。

> 翻译自: [https://www.thecrazyprogrammer.com/2019/09/tree-traversal.html][https_www.thecrazyprogrammer.com_2019_09_tree-traversal.html]

map遍历顺序和保存顺序

[7d1849d4b2ea7d6806a512cdc0246553.png]: /images/20221123/27515255cc344f0fba08fcf611a12928.png
[Binary Tree]: /images/20221123/a0c662a711f144108628eda99cc9a03a.png
[https_www.thecrazyprogrammer.com_2019_09_tree-traversal.html]: https://www.thecrazyprogrammer.com/2019/09/tree-traversal.html