6-8 求二叉树高度（数据结构与算法题目集（中文）PTA）

谁践踏了优雅 2023-07-24 05:52 23阅读 0赞

## 6-8求二叉树高度 （递归与非递归） ##

本题要求给定二叉树的高度。

### 函数接口定义： ###

int GetHeight( BinTree BT );

其中`BinTree`结构定义如下：

typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };

要求函数返回给定二叉树BT的高度值。

### 裁判测试程序样例： ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    int GetHeight( BinTree BT );
    
    int main()
    {
        
        BinTree BT = CreatBinTree();
        printf("%d\n", GetHeight(BT));
        return 0;
    }
    /* 你的代码将被嵌在这里 */

### 输出样例（对于图中给出的树）： ###

![img][]

求二叉树高度，也就是二叉树的层数。

1.  常规递归解法

依次遍历左右子树，并且每向下访问到不为空的左右子树时，depth+1，否则返回0。

上方样例分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]  
代码实现：

int GetHeight(BinTree BT){
        
        if(!BT) return 0;
        return max(GetHeight(BT->Left),GetHeight(BT->Right))+1;
    } 
    int max(int a,int b){
        return a > b ? a : b;}

1.  非递归实现：

对于非递归求深度，最容易想到的就是借助于层次遍历，然后记录层次遍历的层数，层次遍历借助于队列实现，

思路：当前队列中的结点依次出队，同时将出队结点的左右子树入队，直到本层结点全部出队，下层结点全部入队，深度depth+1。

具体实现(使用数组模拟队列)：

int GetHeight( BinTree BT ){
        
    	BinTree temp;
    	BinTree queue[20];
    	int front=0,rear=0;
    	int depth = 0;
        if(!BT) return depth;
    	queue[rear++]=BT;
    	while(rear-front!=0){
        
    		int count = rear - front;
    		depth++;
    		while(count-->0){
        
    			temp = queue[front];
    			if(temp->Left) queue[rear++]=temp->Left;
    			if(temp->Right) queue[rear++]=temp->Right;
    			++front;
    		}
    	}
    	return depth;
    }

[img]: /images/20230528/a0d3c9927e794592bce93948ef864fab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/287b92018a7943b6a15ea9cf243a0449.png