求二叉树的高度和叶子结点的个数

雨点打透心脏的1/2处 2022-04-15 06:51 247阅读 0赞

叶子结点即是左右子树都为空的结点，求叶子结点的个数。

### 1.先运用递归的方式**创建二叉树**，上篇已经提过，可以自行查阅，此处不做赘述。 ###

//创建二叉树
    Status CreateBiTree(BiTree &T)
    {
           char ch;
           scanf("%c",&ch);
           if (ch=='.') T = NULL;
           else {
                    if (!(T=(BiTree)malloc(sizeof(BiTNode))))
                        return OVERFLOW;
                    T->data = ch;
                    CreateBiTree(T->Lchild);
                    CreateBiTree(T->Rchild);
           }
           return OK;
    }

### 2.求叶子结点个数 ###

//求叶子结点数目
    int leaves(BiTree root)
    {
    	int k = 0;
    	if (!root)
    	   return 0;
            else
    	   if (root->Lchild==NULL&&root->Rchild==NULL)
    	       k++;
    
    	   else {
                        //递归遍历所有结点，若遇到左右孩子都为空，则给k加1
    	   	   if (root->Lchild)  leaves(root->Lchild);
    	   	   if (root->Rchild)  leaves(root->Rchild);
    	   	
    	   }	   	   
    	   return k;
    }

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

//运用递归求二叉树的高度
    int BiTreeHeight(BiTree root)
    {
    	int LH,RH;
    	if(!root)
    		return 0;
    	else
    	{
    		LH=BiTreeHeight(root->Lchild );//左子树高度
    		RH=BiTreeHeight(root->Rchild );//右子树高度
    		if(LH>RH)
    			return LH+1;
    			else return RH+1;
    	}
     }

### 4.完整代码 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int Status;
    typedef struct BiTNode{
            char data;
            struct BiTNode *Lchild,*Rchild;
    }BiTNode, *BiTree;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    
    int k; //全局变量记录叶子结点的个数
    
    //创建二叉树
    Status CreateBiTree(BiTree &T)
    {
           char ch;
           scanf("%c",&ch);
           if (ch=='.') T = NULL;
           else {
                    if (!(T=(BiTree)malloc(sizeof(BiTNode))))
                        return OVERFLOW;
                    T->data = ch;
                    CreateBiTree(T->Lchild);
                    CreateBiTree(T->Rchild);
           }
           return OK;
    } 
    
    //输出先序序列
    void preorder (BiTree root)  {//先序遍历root指向根的二叉树
              if (root!=NULL)   { 
                  printf("%c",root->data);//访问根结点
                  preorder(root->Lchild); //先序遍历根的左子树            
                  preorder(root->Rchild); //先序遍历根的右子树
              }//if
        }//preorder
    
    //求叶子结点数目
    int leaves(BiTree root)
    {
    	
    	if (!root)
    	   return 0;
        else
    	   if (root->Lchild==NULL&&root->Rchild==NULL)
    	       k++;
    	   else {
    	   	   if (root->Lchild)  leaves(root->Lchild);
    	   	   if (root->Rchild)  leaves(root->Rchild);
    	   	
    	   }	   	   
    	   return k;
    }  
    
    //求树高
    int BiTreeHeight(BiTree root)
    {
    	int LH,RH;
    	if(!root)
    		return 0;
    	else
    	{
    		LH=BiTreeHeight(root->Lchild );
    		RH=BiTreeHeight(root->Rchild );
    		if(LH>RH)
    			return LH+1;
    			else return RH+1;
    	}
     } 
    
    //主函数
    int main()
    {
        BiTree root;
        CreateBiTree(root);
        preorder(root);
        
        printf("\n");
        printf("leaves = %d\n",leaves(root));
        printf("Height = %d\n", BiTreeHeight(root));
        system("pause"); 
        return 0;
    }

### 5.运行结果 ###

![20181122201422984.png][]

[20181122201422984.png]: /images/20220415/014c4ec7fe3c423c893a799a8bba9305.png