【数据结构】二叉树链式结构的遍历（前序、中序、后序、层序遍历）

浅浅的花香味﹌ 2023-02-20 02:13 16阅读 0赞

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。前、中、后序遍历均采用递归操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]

**1.前序遍历**  
**根节点->根节点的左子树->根节点的右子树**  
递归实现：

void PreOrder(BTNode* root)
    {
        
    	if (root)
    	{
        
    		printf("%d ", root->data);
    		PreOrder(root->left);
    		PreOrder(root->right);
    	}
    }

**2.中序遍历**  
**根节点的左子树->根节点->根节点的右子树**  
递归实现：

void InOrder(BTNode* root)
    {
        
    	if (root)
    	{
        
    		InOrder(root->left);
    		printf("%d ", root->data);
    		InOrder(root->right);
    	}
    }

**3.后序遍历**  
**根节点的左子树->根节点的右子树->根节点**  
递归实现：

void PostOrder(BTNode* root)
    {
        
    	if (root)
    	{
        
    		PostOrder(root->left);
    		PostOrder(root->right);
    		printf("%d ", root->data);
    	}
    }

**4.层序遍历**  
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]

用队列实现：

void LevelOrder(BTNode* root)
    {
        
    	Queue q;
    	if (NULL == root)
    		return;
    	QueueInit(&q);
    	QueuePush(&q, root);
    
    	while (!QueueEmpty(&q))
    	{
        
    		BTNode* cur = QueueFront(&q);
    		printf("%d ", cur->data);
    		QueuePop(&q);
    		//如果左孩子存在，将左孩子入队列
    		if (cur->left)
    			QueuePush(&q, cur);
    		//如果cur右孩子存在，将右孩子入队列
    		if (cur->right)
    			QueuePush(&q, cur);
    	}
    	QueueDestroy(&q);
    }

**练习**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]

前序遍历：ABDEHCFG  
中序遍历：DBEHAFCG  
后序遍历：DHEBFGCA  
层序遍历：ABCDEFGH

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621210248427.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621210744565.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200621211355765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70