【数据结构】（二叉树）递归求解双分支结点个数

「爱情、让人受尽委屈。」 2021-11-14 14:34 424阅读 0赞

> **算法思想：** 求二叉树双分支结点个数就是当一个结点左右孩子非空  
> 时该结点为双分支结点

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

//二叉树结构体定义
    typedef struct BiTree{
        
    	char data;
    	BiTree *lchild;
    	BiTree *rchild;
    	
    }BiTree;

int DsonNodes(BiTree *T){
        
    	if(!T){
        
    		return 0;
    	}
    	if(T->rchild!=NULL && T->lchild!=NULL) //若结点的左右孩子存在
    		return 1+DsonNodes(T->rchild)+DsonNodes(T->lchild);
    	else
    		return DsonNodes(T->rchild)+DsonNodes(T->lchild);
    
    }

**测试数据：**

char pre[13]={
        '#','A','B','D','F','H','J','M','N','C','E','K','G'};
    	char in[13]={
        '#','D','B','J','H','M','N','F','A','E','K','C','G'};
    
    	char pre1[10]={
        '#','A','B','C','D','E','F','G','H','I'};
    	char in1[10]={
        '#','B','C','A','E','D','G','H','F','I'};
    
    	char pre2[6]={
        '#','A','B','D','E','C'};
    	char in2[6]={
        '#','D','B','E','A','C'};
    
    	char pre3[5]={
        '#','A','B','D','C'};
    	char in3[5]={
        '#','D','B','A','C'};
    
    	cout<<"The number of double-branch nodes is: "<<DsonNodes(PreInCreate(pre,in,1,12,1,12))<<endl;
    	cout<<"The number of double-branch nodes is: "<<DsonNodes(PreInCreate(pre3,in3,1,4,1,4))<<endl;
    	cout<<"The number of double-branch nodes is: "<<DsonNodes(PreInCreate(pre1,in1,1,9,1,9))<<endl;

**结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211114/0e1183af3e3e4118a5242872ad0f88f0.png