二叉树遍历的一些简单应用

深碍√TFBOYSˉ_ 2023-02-27 13:50 22阅读 0赞

### 前言 ###

前两篇博客讲了二叉树的几种遍历  
[二叉树的三种遍历（前序，中序，后序），递归与非递归表示,（初中生表示看完就懂了）][Link 1]  
[简述二叉树的层序遍历（队列），五分钟保证理解][Link 2]  
接下来讲点二叉树遍历的简单应用

### 输出二叉树的叶子节点 ###

思路：在二叉树遍历算法中增加检测其左右节点是否为空

void PreOrderTraversal (BinTree *BT)
    {
        
    	
    	if(BT)
    	{
        
    		if(!BT->Left && !BT->Right)
    			cout << BT->Value << ednl;
    		PreOrderTraversal(BT->Left);
    		PreOrderTraversal(BT->Right);
    	}
    }

### 求二叉树的高度 ###

思路：二叉树的高度=左右子树最大高度 + 1

int PostOrderGetHeight(BinTree *BT)
    {
        
    	int HLeft,HRight,MaxH;
    	if(BT)
    	{
        
    		HLeft = PostOrderGetHeight(Bt->Left);
    		HRight = PostOrderGetHeight(BT->Right);
    		MaxH = (HLeft > HRight) ? HLeft : HRight;
    		return (MaxH + 1);
    	}
    	else 
    		return 0;
    }

### 二元运算表达式树及其遍历 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlb3dhaGFoYQ_size_16_color_FFFFFF_t_70]  
三种遍历得到的不同结果

*  先序遍历：前缀表达式 ++a\*bc \*+\*defg
 *  中序遍历：中缀表达式 a+b \* c + d \* e+f\*g
 *  后序遍历：后缀表达式 abc \* + de \* f + g \* +

其中，中缀表达式会受到运算符优先级的影响，可能不能正确表达出运算表达式树想表达的意思

要解决这个问题，其实也简单的，在你输出左子树的时候，先输出个左括号，左子树结束的时候，再加一个右括号，这样就能解决了

[Link 1]: https://blog.csdn.net/leowahaha/article/details/107404424
[Link 2]: https://blog.csdn.net/leowahaha/article/details/107416090
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlb3dhaGFoYQ_size_16_color_FFFFFF_t_70]: /images/20230209/07fffbea04c8432fb8321e398fb7462e.png