246-对二叉树进行层次遍历和Z字形输出

旧城等待， 2022-11-14 10:21 102阅读 0赞

## 二叉树的层次遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**二叉树的层次遍历：打印ABGCDHEF**

我们使用队列来解决问题。  
把A入队列，队列空不空，不空，A出栈，打印A，B,G入栈，队列不空，出B，入C,D，出G，G的左边为空，右边不为空，入H，出C，C的左右都为空，出D，E,F入栈，出H，H的左右都为空，E的左右为空，出E，F的左右为空，出F。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

void NiceLevelOrder(BtNode *ptr)
    {
        
    	if(ptr==nullptr) return;
    	std::queue<BtNode*>qu;
    	qu.push(ptr);
    	while(!qu.empty())
    	{
        
    		BtNode* p=qu.front();qu.pop();
    		cout<<p->data<<" ";
    		if(p->leftchild!=nullptr)
    		{
        
    			qu.push(p->leftchild);
    		}
    		if(p->rightchild!=nullptr)
    		{
        
    			qu.push(p->rightchild);
    		}
    	}
    	cout<<endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

## 对二叉树Z字形输出 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**打印出AGBCDHFE**

![在这里插入图片描述][20210328201952607.png_pic_center]  
**规律：出A（第一层），先左后右，出第二层，先右后左，出第三层，先左后右。**

我们定义2个栈。首先把A入1号栈，不为空，A出栈，B，G先后入2号栈，出G后，按先右后左的方式，H入1号栈，G的左为空，不入了，出B，仍然是先右后左的方式，D,C先后入1号栈，C出栈，以此类推下去。

void NiceZLOrder(BtNode *ptr)
    {
        
    	if(ptr==nullptr) return;
    	std::stack<BtNode*>sta,stb;
    	sta.push(ptr);
    	while(!sta.empty()||!stb.empty())
    	{
        
    		while(!sta.empty())
    		{
        
    			ptr=sta.top(); sta.pop();
    			cout<<ptr->data<<" ";
    			if(ptr->leftchild!=nullptr) stb.push(ptr->leftchild);
    			if(ptr->rightchild!=nullptr) stb.push(ptr->rightchild);
    		}
    		while(!stb.empty())
    		{
        
    			ptr=stb.top(); stb.pop();
    			cout<<ptr->data<<" ";
    			if(ptr->rightchild!=nullptr) sta.push(ptr->rightchild);
    			if(ptr->leftchild!=nullptr) sta.push(ptr->rightchild);
    		}
    	}
    	cout<<endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
**如果增加H的左孩子为X**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
**再次运行程序**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/6b145747e7b045d1ade7a2f5004bb75d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/08b39d64de914528a34af88d12ad787e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/43109bc23397458db3dae138999ec657.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210328201809262.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20210328201952607.png_pic_center]: https://img-blog.csdnimg.cn/20210328201952607.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210328203237955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210328203247243.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210328203405588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center