数据结构——二叉树的递归算法

男娘i 2022-12-24 06:00 167阅读 0赞

二叉树的结构定义：

typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;

这里包含的递归算法有：

1.  二叉树的先序创建；
2.  二叉树的先序中序后序遍历；
3.  二叉树的销毁算法；
4.  双序遍历；
5.  求结点的个数；
6.  求结点值的和；
7.  求树的深度；
8.  求叶子结点的个数；
9.  求单分支结点的个数；
10. 交换结点的左右子树；
11. 寻找最小值结点；
12. 判断是否是相同的二叉树；
13. ***判断是否是平衡二叉树；***
14. ***判断是对称二叉树；***
15. 二叉树的最小深度算法  
    查看之前的博文  
    [ 二叉树的最小深度][Link 1]
16. 二叉树的层次遍历  
    查看之前的博文  
    [二叉树的层次遍历][Link 2]  
    [二叉树的层次遍历进阶][Link 3]
17. 二叉树的最长路径  
    查看之前的博文  
    [二叉树的最长路径问题][Link 4]
18. 从叶子结点到根节点的全部路径  
    查看之前的博文  
    [从叶子结点到根节点的全部路径][Link 5]

最底面有全部代码的合集：  
1 二叉树的先序创建  
思路：  
和先序递归遍历差不多，二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表。（序列中元素为‘\#’时，表示该结点为空）。

void CreateBiTree(BiTree &T)//二叉树的先序创建 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }

2二叉树的先序中序后序遍历  
思路：  
先序中序后序递归算法都类似

int  preorderTraverse(BiTree T)//二叉树的先序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			printf("%c ",T->data);
    			preorderTraverse(T->lchild);
    			preorderTraverse(T->rchild);
    		}
     } 
     
    int  InorderTraverse(BiTree T)//二叉树的中序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			InorderTraverse(T->lchild);
    			printf("%c ",T->data);
    			InorderTraverse(T->rchild);
    		}
     }
     
    int  PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			PostorderTraverse(T->lchild);
    			PostorderTraverse(T->rchild);
    			printf("%c ",T->data);
    		}
     }

3二叉树的销毁算法  
思路：  
和后序递归算法类似

void DestroyBiTree(BiTree &T)//二叉树的销毁算法 
    {
        
    	if(T==NULL)
    		exit(-1);
    	else
    	{
        
    		DestroyBiTree(T->lchild);
    		DestroyBiTree(T->rchild);
    		free(T);
    	}
    }

4双序遍历  
思路：和普通前序中序遍历类似

void double_preorderTraverse(BiTree T)//双序遍历 
    {
        
    	if(T!=NULL)
    	{
        
    		printf("%c ",T->data);
    		double_preorderTraverse(T->lchild);
    		printf("%c ",T->data);
    		double_preorderTraverse(T->rchild);
    	}
    }

5求结点的个数  
思路：仅一个if else

int NodeCount(BiTree &T)//求节点的个数 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
    }

6求结点值的和  
思路：  
和求结点个数一样的算法

int Sum(BiTree &T)//求结点值的和 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return T->data+Sum(T->lchild)+Sum(T->rchild);
    }

7求树的深度  
思路：  
树的深度是指树的最大深度（根节点到最远叶子结点的层次）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]

int max(int x,int y)//求两数的最大值 
    {
        
    	if(x>y)
    		return x;
    	else
    		return y;	
    }
    
    int BiTree_height1(BiTree &T)//求树的深度算法1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));
    	
    }

int BiTree_height2(BiTree &T)//求树的深度算法2 
    {
        
    	int l_height,r_height;
    	if(T==NULL)
    		return 0;
    	else
    	{
        
    		l_height=BiTree_height2(T->lchild);
    		r_height=BiTree_height2(T->rchild);
    		return (l_height>r_height)?(l_height+1):(r_height+1);
    	}
    
    }

8求叶子结点的个数  
思路：  
若T为空，则返回0；  
若T为叶子结点，则返回1；  
若为非叶子结点，则返回（左子树叶子结点数+右子树叶子结点数）；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]

int leafCount(BiTree &T)//求叶子结点的个数 
    {
        
    	if(T==NULL)
    		return 0;
    	if(T->lchild==NULL&&T->rchild==NULL)
    		return 1;
    	else
    	{
        
    		return leafCount(T->lchild)+leafCount(T->rchild);
    	}
     }

9求单分支结点的个数  
思路：

int DegreeOne(BiTree T)
    {
        
    	if(NULL == T)
    		return 0;
     
    	if(NULL == T->lchild && NULL == T->rchild)//为叶子结点 
    		return 0;
     
    	if(NULL != T->lchild && NULL != T->rchild)//为双分支结点 
    		return DegreeOne(T->lchild) + DegreeOne(T->rchild);
    	//此时为单分支结点 
    	return 1 + DegreeOne(T->lchild) + DegreeOne(T->rchild);
     
    
    }
    int DegreeOne1(BiTree &T)//求单分支节点的个数 算法2
    {
        
        int lnum, rnum, n;
        if(T == NULL)
            return 0;
        else
        {
        
        	if((T->lchild == NULL && T->rchild != NULL) ||(T->lchild != NULL && T->rchild == NULL))
                n = 1; //为单分支结点
            else
                n = 0; //其他结点
    	lnum = DegreeOne1(T->lchild); //递归求左子树中单分支结点数
        rnum = DegreeOne1(T->rchild); //递归求右子树中单分支结点数
        return (lnum + rnum + n);
    	}
            
        
    }

10交换结点的左右子树  
另一个单独的问题的博文  
[数据结构——二叉树交换左右子树][Link 6]  
代码：

void Exchange_lchild_rchild(BiTree &T)//½»»»×óÓÒº¢×Ó½áµã 
    {
        
    	if(T!=NULL)	
    	if(T->lchild!=NULL||T->rchild!=NULL)
    		{
        
    			BiTree temp;
    			temp=T->lchild;
    			T->lchild=T->rchild;
    			T->rchild=temp;
    	Exchange_lchild_rchild(T->lchild);
    	Exchange_lchild_rchild(T->rchild);
    		}
    	
     }

11寻找最小值结点  
代码：

void Findminnode(BiTree &T,char &min)//Ñ°ÕÒ×îÐ¡Öµ½áµã 
    {
        
    	
    	if(T!=NULL)
     {
        
    	if(T->data<min)
    	{
        
    		min=T->data;
    	}
    	Findminnode(T->lchild,min);
    	Findminnode(T->rchild,min);
    	
     }

12判断是否是相同的二叉树

思路：  
1判断这两棵树是否都空，如果都空，则是相同的树，如果有一棵树不空另一棵树为空，则不是相同的树  
2这两棵树都不空，判断这个节点对应的值相等吗？  
3若这两个节点的值相等，递归同时判断这两棵树的左子树，右子树。

status BiTree_is_same(BiTree &T,BiTree &S)//ÊÇ·ñÊÇÏàÍ¬µÄ¶þ²æÊ÷ 
    {
        
    	if(T==NULL&&S==NULL)
    			return 1;
    	if(T==NULL||S==NULL)
    			return 0;
    	if(T->data!=S->data)
    			return 0;
    	return(BiTree_is_same(T->lchild,S->lchild)&&BiTree_is_same(T->rchild,S->rchild));
    }

13判断是否是平衡二叉树  
思路：  
1如果这颗树为空，则返回1  
2此时（这棵树不为空），判断该节点的左右子树的高度差的绝对值|（左子树的高度—右子树的高度）|>1,如果大于1，则返回0  
3此时（该节点的左右子树的高度差<1），递归遍历该节点的左右子树。

int BiTree_height1(BiTree &T)//ÇóÊ÷µÄÉî¶ÈËã·¨1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));
    	
    } 
    
    
    
    status BiTree_is_Balanced(BiTree T)//ÅÐ¶ÏÊÇ·ñÊÇÆ½ºâ¶þ²æÊ÷ 
    {
        
    	if(T==NULL)
    		return 1;
    	if(abs(BiTree_height1(T->lchild)-BiTree_height1(T->rchild))>1)
    		return 0;
    	return BiTree_is_Balanced(T->lchild)&&BiTree_is_Balanced(T->rchild);
    }

14判断是对称二叉树  
思路：  
1用BiTree\_symmetry(BiTree T)函数调用T的左右子树  
2调用 BiTree\_check(BiTree root1,BiTree root2)函数核实他的左右子树是否满足左右对称，镜像：如果左右子树都空则返回1，若果仅有一棵树为空,则返回0，若两棵树都不空，则返回（判断左右子树对应根节点的值是否相等，递归调用BiTree\_check(BiTree root1,BiTree root2)判断该节点的左右子树）BiTree\_check(root1->lchild,root2->rchild)&&BiTree\_check(root1->rchild,root2->lchild)

status BiTree_check(BiTree root1,BiTree root2)
    {
        
    	if(root1==NULL&&root2==NULL) return 1;
    	if(root1==NULL||root2==NULL) return 0;
    	return root1->data==root2->data&&BiTree_check(root1->lchild,root2->rchild)&&BiTree_check(root1->rchild,root2->lchild);
    }
    
    status BiTree_symmetry(BiTree T)//
    {
        
    	return BiTree_check(T->lchild,T->rchild);
     }

全部代码（可执行）

#include<stdio.h>
    #include<bits/stdc++.h> 
    typedef char TElemType;
    typedef int status; 
    typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    void CreateBiTree(BiTree &T)//¶þ²æÊ÷µÄÏÈÐò´´½¨ 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    void CreateBiTree2(BiTree &T)//¶þ²æÊ÷µÄÖÐÐò´´½¨ 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		
    		CreateBiTree(T->lchild);
    		T->data=ch;
    		CreateBiTree(T->rchild);
    	}
    }
    void DestroyBiTree(BiTree &T)//¶þ²æÊ÷µÄÏú»ÙËã·¨ 
    {
        
    	if(T==NULL)
    		exit(-1);
    	else
    	{
        
    		DestroyBiTree(T->lchild);
    		DestroyBiTree(T->rchild);
    		free(T);
    	}
    }
    
    void double_preorderTraverse(BiTree T)//Ë«Ðò±éÀú 
    {
        
    	if(T!=NULL)
    	{
        
    		printf("%c ",T->data);
    		double_preorderTraverse(T->lchild);
    		printf("%c ",T->data);
    		double_preorderTraverse(T->rchild);
    	}
    }
    
    
    
    
    int  preorderTraverse(BiTree T)//¶þ²æÊ÷µÄÏÈÐòµÝ¹é±éÀúËã·¨ 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			printf("%c ",T->data);
    			preorderTraverse(T->lchild);
    			preorderTraverse(T->rchild);
    		}
     } 
     
    int  InorderTraverse(BiTree T)//¶þ²æÊ÷µÄÖÐÐòµÝ¹é±éÀúËã·¨ 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			InorderTraverse(T->lchild);
    			printf("%c ",T->data);
    			InorderTraverse(T->rchild);
    		}
     }
     
    int  PostorderTraverse(BiTree T)//¶þ²æÊ÷µÄºóÐòµÝ¹é±éÀúËã·¨ 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			PostorderTraverse(T->lchild);
    			PostorderTraverse(T->rchild);
    			printf("%c ",T->data);
    		}
     }
    
    int NodeCount(BiTree &T)//Çó½ÚµãµÄ¸öÊý 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
    }
    
    int Sum(BiTree &T)//Çó½áµãÖµµÄºÍ 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return T->data+Sum(T->lchild)+Sum(T->rchild);
    }
    
    int max(int x,int y)//ÇóÁ½ÊýµÄ×î´óÖµ 
    {
        
    	if(x>y)
    		return x;
    	else
    		return y;	
    }
    
    int BiTree_height1(BiTree &T)//ÇóÊ÷µÄÉî¶ÈËã·¨1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    		return 1+max(BiTree_height1(T->lchild),BiTree_height1(T->rchild));
    	
    } 
    
    int BiTree_height2(BiTree &T)//ÇóÊ÷µÄÉî¶ÈËã·¨2 
    {
        
    	int l_height,r_height;
    	if(T==NULL)
    		return 0;
    	else
    	{
        
    		l_height=BiTree_height2(T->lchild);
    		r_height=BiTree_height2(T->rchild);
    		return 1+max(l_height,r_height);
    	}
    		
    	
    }
    
    int leafCount(BiTree &T)//ÇóÒ¶×Ó½áµãµÄ¸öÊý 
    {
        
    	if(T==NULL)
    		return 0;
    	if(T->lchild==NULL&&T->rchild==NULL)
    		return 1;
    	else
    	{
        
    		return leafCount(T->lchild)+leafCount(T->rchild);
    	}
     } 
    
    void Exchange_lchild_rchild(BiTree &T)//½»»»×óÓÒº¢×Ó½áµã 
    {
        
    	if(T!=NULL)	
    	if(T->lchild!=NULL||T->rchild!=NULL)
    		{
        
    			BiTree temp;
    			temp=T->lchild;
    			T->lchild=T->rchild;
    			T->rchild=temp;
    	Exchange_lchild_rchild(T->lchild);
    	Exchange_lchild_rchild(T->rchild);
    		}
    	
     } 
    
    void Findminnode(BiTree &T,char &min)//Ñ°ÕÒ×îÐ¡Öµ½áµã 
    {
        
    	
    	if(T!=NULL)
     {
        
    	if(T->data<min)
    	{
        
    		min=T->data;
    	}
    	Findminnode(T->lchild,min);
    	Findminnode(T->rchild,min);
    	
     }
    	
    } 
    
    int DegreeOne(BiTree T)
    {
        
    	if(NULL == T)
    		return 0;
     
    	if(NULL == T->lchild && NULL == T->rchild)//ÎªÒ¶×Ó½áµã 
    		return 0;
     
    	if(NULL != T->lchild && NULL != T->rchild)//ÎªË«·ÖÖ§½áµã 
    		return DegreeOne(T->lchild) + DegreeOne(T->rchild);
    	//´ËÊ±Îªµ¥·ÖÖ§½áµã 
    	return 1 + DegreeOne(T->lchild) + DegreeOne(T->rchild);
     
    
    }
    int DegreeOne1(BiTree &T)//Çóµ¥·ÖÖ§½ÚµãµÄ¸öÊý Ëã·¨2
    {
        
        int lnum, rnum, n;
        if(T == NULL)
            return 0;
        else
        {
        
        	if((T->lchild == NULL && T->rchild != NULL) ||(T->lchild != NULL && T->rchild == NULL))
                n = 1; //Îªµ¥·ÖÖ§½áµã
            else
                n = 0; //ÆäËû½áµã
    	lnum = DegreeOne1(T->lchild); //µÝ¹éÇó×ó×ÓÊ÷ÖÐµ¥·ÖÖ§½áµãÊý
        rnum = DegreeOne1(T->rchild); //µÝ¹éÇóÓÒ×ÓÊ÷ÖÐµ¥·ÖÖ§½áµãÊý
        return (lnum + rnum + n);
    	}
            
        
    }
    
    
    
    
    status BiTree_is_same(BiTree &T,BiTree &S)//ÊÇ·ñÊÇÏàÍ¬µÄ¶þ²æÊ÷ 
    {
        
    	if(T==NULL&&S==NULL)
    			return 1;
    	if(T==NULL||S==NULL)
    			return 0;
    	if(T->data!=S->data)
    			return 0;
    	return(BiTree_is_same(T->lchild,S->lchild)&&BiTree_is_same(T->rchild,S->rchild));
    }
    
    
    status BiTree_is_Balanced(BiTree T)//ÅÐ¶ÏÊÇ·ñÊÇÆ½ºâ¶þ²æÊ÷ 
    {
        
    	if(T==NULL)
    		return 1;
    	if(abs(BiTree_height1(T->lchild)-BiTree_height1(T->rchild))>1)
    		return 0;
    	return BiTree_is_Balanced(T->lchild)&&BiTree_is_Balanced(T->rchild);
    }
    
    status BiTree_check(BiTree root1,BiTree root2)
    {
        
    	if(root1==NULL&&root2==NULL) return 1;
    	if(root1==NULL||root2==NULL) return 0;
    	return root1->data==root2->data&&BiTree_check(root1->lchild,root2->rchild)&&BiTree_check(root1->rchild,root2->lchild);
    }
    
    status BiTree_symmetry(BiTree T)//¶Ô³Æ¶þ²æÊ÷ 
    {
        
    	return BiTree_check(T->lchild,T->rchild);
     } 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    int main()
    {
        	
    	int x;
    	int node_number,BiTree_height;
    	BiTree T;
    	char min;
    	printf("´´½¨Ê÷ÊäÈëÊ÷TµÄÏÈÐòÐòÁÐ(ÆäÖÐÊ¹ÓÃ#´ú±í¿Õ½Úµã)\n");
    	CreateBiTree(T);
    	
    	printf("---²Ëµ¥---\n"); 
    	printf("[1]:ÏÈÐò±éÀúËã·¨\n");
    	printf("[2]:ÖÐÐò±éÀúËã·¨\n");
    	printf("[3]:ºóÐò±éÀúËã·¨\n");
    	printf("[4]:Çó½áµã¸öÊýËã·¨\n");
    	printf("[5]:ÇóÊ÷µÄÉî¶ÈËã·¨\n");
    	printf("[6]:½»»»×óÓÒº¢×Ó½ÚµãËã·¨\n");
    	printf("[7]:Ñ°ÕÒ×îÐ¡Öµ½áµãËã·¨\n"); 
    	printf("[8]:Çóµ¥·ÖÖ§½ÚµãµÄ¸öÊýËã·¨\n");
    	printf("[9]ÅÐ¶ÏÊÇ·ñÊÇÏàÍ¬µÄÊ÷\n");
    	printf("[10]:ÅÐ¶ÏÊÇ·ñÊÇÆ½ºâ¶þ²æÊ÷\n"); 
    	printf("[11]:ÅÐ¶ÏÊÇ·ñÊÇ¶Ô³Æ¶þ²æÊ÷\n"); 
    	while(1)
    	{
        
    		int n; 
    		printf("\nÊäÈëÒª½øÐÐµÄ²Ù×÷:");
    		scanf("%d",&n);
    		switch(n)
    		{
        
    			case 1:
    					preorderTraverse(T);
    					break;
    			case 2:
    					InorderTraverse(T);
    					break;
    			case 3:
    					PostorderTraverse(T);
    					break;
    			case 4:
    					node_number=NodeCount(T);
    					printf("%d",node_number);
    					break;
    			case 5:
    					BiTree_height=BiTree_height1(T);
    					printf("%d",BiTree_height);
    					break;
    			case 6:
    					Exchange_lchild_rchild(T);
    					break;
    			case 7:
    					min=T->data;
    					Findminnode(T,min);//±ØÐëÔÚµ÷ÓÃº¯ÊýÇ°¸³³õÖµ 
    					printf("%c",min);
    					
    					break;
    			case 8:
    					printf("Çóµ¥·ÖÖ§½áµã¸öÊý£º");
    					printf("%d",DegreeOne1(T)); 
    					break;
    			case 9:
    				
    				
    				if(BiTree_is_same(T,T)) 
    						printf("ÊÇÏàÍ¬µÄÊ÷\n");
    					else printf("²»ÊÇÏàÍ¬µÄÊ÷\n");
    					break;		
    			case 10:
    					
    					if(BiTree_is_Balanced(T)) 
    						printf("ÊÇÆ½ºâ¶þ²æÊ÷\n");
    					else printf("²»ÊÇÆ½ºâ¶þ²æÊ÷\n");
    					break; 
    			case 11:
    					
    					if(BiTree_symmetry(T)) 
    						printf("ÊÇ¶Ô³Æ¶þ²æÊ÷\n");
    					else printf("²»ÊÇ¶Ô³Æ¶þ²æÊ÷\n");
    					break;
    				
    		}
    	} 
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	
    
    	
    }

[Link 1]: https://blog.csdn.net/qq_50675813/article/details/110052820
[Link 2]: https://blog.csdn.net/qq_50675813/article/details/110064164
[Link 3]: https://blog.csdn.net/qq_50675813/article/details/110202450
[Link 4]: https://blog.csdn.net/qq_50675813/article/details/110204845
[Link 5]: https://blog.csdn.net/qq_50675813/article/details/110206878
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/77cecdbb8b5d4d03b96b67a4c3c3c4c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201127114428173.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70#pic_center
[Link 6]: https://blog.csdn.net/qq_50675813/article/details/110087497