二叉树-递归求叶子节点数、数的高度

左手的ㄟ右手 2022-03-30 05:12 266阅读 0赞

![20190101173727566.png][]

*  一共有3个叶子节点
 *  高度：4

--------------------

## 代码 ##

#include <stdio.h>
    #include <string.h>
    
    
    
    typedef struct BINARYNODE
    { 
    	char ch;
    	struct BINARYNODE* left;
    	struct BINARYNODE* right;
    
    }BinaryNode;
    
    int GetHeightOfTree( BinaryNode* root) //计算树的高度
    { 
    	if (root == NULL) return 0;
    	
    	int Lheight = GetHeightOfTree(root->left);
    	int Rheight = GetHeightOfTree(root->right);
    	return Lheight > Rheight ? Lheight + 1 : Rheight + 1;
    }
    
    
    void CalculateLeaves(BinaryNode* root, int* num)
    { 
    	if(root==NULL)
    		return;
    	if(root->left == NULL && root->right == NULL)
    		(*num)++;
    	CalculateLeaves(root->left, num);  //递归，传左孩子
    	CalculateLeaves(root->right, num); 
    }
    
    int main(void)
    { 
        BinaryNode b1,b2,b3,b4,b5,b6,b7,b8;
    	int num=0;
    
    	b1.ch = 'A'; b1.left = &b2; b1.right = &b3;
    	b2.ch = 'B'; b2.left = NULL;b2.right = &b4;
    	b3.ch = 'F'; b3.left = NULL;b3.right = &b5;
    	b4.ch = 'C'; b4.left = &b6; b4.right = &b7;
    	b5.ch = 'G'; b5.left = &b8; b5.right = NULL;
    	b6.ch = 'D'; b6.left = NULL; b6.right = NULL;
    	b7.ch = 'E'; b7.left = NULL; b7.right = NULL;
    	b8.ch = 'H'; b8.left = NULL; b8.right = NULL;
    
    	
    	CalculateLeaves(&b1, &num);
    	printf("%d\n", num);
    
    
    	int height = GetHeightOfTree(&b1);
    	printf("%d\n",height);
    
    	return 0;
    }

结果  
叶子节点：3  
树高度：4

[20190101173727566.png]: /images/20220330/57fa2900e2434a3298a6dafb3e61e2ce.png