数据结构——交换左右子树

ゝ一世哀愁。 2022-12-23 11:09 116阅读 0赞

## 递归——层次遍历—交换左右子树算法 ##

思路：  
与先序递归遍历类似  
1如果有子树，交换这个节点的左右子树（和交换两个变量的值一样）  
2再递归这个节点的左子树，右子树；

#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 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);
    		}
    	
     }
     int BiTree_height1(BiTree T)//ÇóÊ÷µÄÉî¶ÈËã·¨1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    	{
        
    		if(BiTree_height1(T->lchild)>BiTree_height1(T->rchild))
    				return 1+BiTree_height1(T->lchild);
    		else
    				return 1+BiTree_height1(T->rchild);
    	
    	}
    	
    	
    } 
    void printNodeAtLevel(BiTree T,int level)  
    {
          
        if(T==NULL||level<0)  
            return;  
      
        if(level==0)  
        {
          
        printf("%c ",T->data);
    	return;  
        }  
      
        // ×ó×ÓÊ÷µÄ level - 1 ¼¶  
        printNodeAtLevel(T->lchild,level-1);  
      
        // ÓÒ×ÓÊ÷µÄ level - 1 ¼¶  
        printNodeAtLevel(T->rchild,level-1);  
    }
     
    void levelOrder(const BiTree T)
    {
        
    	if(T==NULL)
    		return;
    	int totalLevel = BiTree_height1(T);
    	for(int i = 0; i< totalLevel; i++)
    	{
        
    		printNodeAtLevel(T, i);
    		printf("\n");//´òÓ¡ÍêÒ»²ã£¬»»ÐÐ
    	}
    } 
     int main()
     {
        
     	BiTree T;
    	printf("´´½¨Ê÷ÊäÈëÊ÷TµÄÏÈÐòÐòÁÐ(ÆäÖÐÊ¹ÓÃ#´ú±í¿Õ½Úµã)\n");
    	CreateBiTree(T);
    	levelOrder(T);
    	
    	printf("½»»»Ê÷×óÓÒ×ÓÊ÷Ëã·¨\n");
    	Exchange_lchild_rchild(T);
    	
    	 levelOrder(T);
    	
    	
      }