二叉树的操作(一)

落日映苍穹つ 2022-02-05 11:11 237阅读 0赞

### 二叉树的操作 ###

*   *   *   *  二叉树的遍历
             *   *   *  中序遍历
                     *  先序遍历
                     *  后序遍历
                     *  层序遍历
             *  二叉树叶结点的输出算法
             *  二叉树的高度算法

#### 二叉树的遍历 ####

###### 中序遍历 ######

它是指对树中任一结点的访问实在遍历玩其左子树后进行的，访问此结点后，再对其右子数遍历。其遍历过程为：  
1.中序遍历其左子树  
2.访问根结点  
3.中序遍历其右子树  
**代码：**

void InorderTraversal(BinTree BT)
    {
        
    	if(BT)
    	{
        
    		InorderTraversal(BT->Left);
    		//此处假设对BT结点的访问就是打印数据
    		printf("%d",BT->Data);//鸡舍数据为整型
    		InorderTraversal(BT->Right); 
    	}
    }

**如图所示：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]

###### 先序遍历 ######

它是指对结点的访问是在其左、右子树遍历之前进行的，其遍历过程为：  
1.访问根结点  
2.先序遍历其左子树  
2.先序遍历其右子数  
**代码：**

void PreorderTraversal(BinTree BT)
    {
    	if(BT)
    	{
    		printf("%d",BT->Data);
    		PreorderTraversal(BT->Left);
    		PreorderTraversal(BT->Right);
    	}
    }

**如图所示：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]

###### 后序遍历 ######

它是指结点左右子树的遍历先进行，然后才是对此结点的访问，其遍历过程为：  
1.后序遍历其左子树  
2.后序遍历其右子树  
3.访问根结点  
**代码**

void PostorderTraversal(BinTree BT)
    {
        
    	if(BT)
    	{
        
    		PostorderTraversal(BT->Left);
    		PostorderTraversal(BT->Right);
    		printf("%d",BT->Data);
    	}
    }

**如图所示：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]

###### 层序遍历 ######

层序遍历的特点是从上到下，从左到右，其遍历过程为：（详见“二叉树的遍历–PTA”）

#### 二叉树叶结点的输出算法 ####

void PreorderPrintLeaves( BinTree BT )
    {
        
        if(BT){
        
            if(!BT->Left&&!BT->Right)printf(" %c",BT->Data);
            if(BT->Left)PreorderPrintLeaves(BT->Left);
            if(BT->Right)PreorderPrintLeaves(BT->Right);
            
        }
    }

#### 二叉树的高度算法 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 3]  
**代码**

int GetHeight( BinTree BT )
    {
        
    	int HL,HR,MaxH;
    	if(BT)
    	{
        
    		HL=GetHeight(BT->Left);
    		HR=GetHeight(BT->Right);
    		MaxH=HL>HR? HL:HR;
    		return (MaxH+1);
    	}
    	else return 0;
    }

![在这里插入图片描述][2019050517343068.gif]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220205/fdf080deca494ad8a205ae02b8a3fc1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]: /images/20220205/2c1354a527e743ee8a37dda865bb87c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]: /images/20220205/c3ceabda5e1648bb947e60618db2b6e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 3]: /images/20220205/635f280b95b8412fb0cfef723c8f59b3.png
[2019050517343068.gif]: /images/20220205/91a38c5814bb4beb9414c7d8600af619.png