PTA 6-2 二叉树的遍历 (25分)

心已赠人 2023-07-25 05:28 5阅读 0赞

题目：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]  
分析：  
此处用了递归的方式，因为行数比较短。  
特别注意第四个函数，层序遍历法，由于数据结构书上（浙大陈越姥姥版）用了入队列的方法:

void LevelorderTraversal( BinTree BT )
    {
        	Queue Q;     /*关键字在该题目中未定义*/
        BinTree T;
        
    	if(!BT) return;
    	
    	Q=CreatQueue();
    	AddQ(Q, BT);
    	while(!IsEmpty(Q)){
        
    		T=DeleteQ(Q);
    		printf("%d", T->Data);
    		if(T->Left)  AddQ(Q,T->Left);
    		if(T->Right)  AddQ(Q,T->Right;

而该方法的一些关键字如Queue等在题目中未定义，因此需要自己定义数组或链表队列，以及将入队列，出队列和判断队列是否为空这些操作写入函数中。具体方法如下：

void InorderTraversal( BinTree BT )
    {
        
        if(BT){
        
            InorderTraversal(BT->Left);
            printf(" %c",BT->Data);
            InorderTraversal(BT->Right);
        }
    }
    void PreorderTraversal( BinTree BT )
    {
        
        if(BT){
        
            printf(" %c",BT->Data);
            PreorderTraversal(BT->Left);
            PreorderTraversal(BT->Right);
        }
    }
    void PostorderTraversal( BinTree BT )
    {
        
        if(BT){
        
            PostorderTraversal(BT->Left);
            PostorderTraversal(BT->Right);
            printf(" %c",BT->Data);
        }
    }
    void LevelorderTraversal( BinTree BT )
    {
        
        BinTree a[1000];
        int front=0,tail=0;
        BinTree T;
        if(BT) a[++tail]=BT;
        while(front!=tail){
        
            T=a[++front];
            printf(" %c",T->Data);
            if(T->Left) a[++tail]=T->Left;
            if(T->Right) a[++tail]=T->Right;
        }
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]: /images/20230528/0b5b3f2145464d8397c8b5c166ce2c5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70 1]: /images/20230528/181fde0ad9bf49c39ae3ce55ca2d1ac2.png