数据结构：二叉树的遍历

向右看齐 2022-12-30 13:43 8阅读 0赞

**（1）实验目的**  
通过该实验，使学生理解二叉树的链式存储，掌握二叉树的几种遍历算法，并通过该实验使学生理解递归的含义，掌握C语言编写递归函数的方法和注意事项。  
**（2）实验内容**  
实现教材中算法6.4描述的二叉树创建算法，在此基础上实现二叉树的先序、后序递归遍历算法、两种非递归中序遍历、层序遍历、求二叉树的深度。注意：在非递归算法中用到栈和队列时，不要调用系统的栈和队列，需要自己实现栈和队列的操作。  
**（3）参考界面**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70]  
**（4）验收/测试用例**

*  创建

输入 ：ABC$ $ DE$ G $ $ F$ $ $ ($表示空格)  
该输入对应的树如图所示

*  先序 屏幕输出 A B C D E G F
 *  后序 屏幕输出 C G E F D B A
 *  中序 屏幕输出 C B E G D F A  
    (两种中序非递归还需看源代码)
 *  层序 屏幕输出 A B C D E F G
 *  深度 屏幕显示 深度为5
 *  另外自己画出一棵树，再测试一遍。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70 1]  
    **设计思想**  
    创建二叉树：按先序次序输入二叉树中结点得值（一个字符），空格字符表示空树，  
    构造二叉链表表示的二叉树T。  
    先序遍历：采用二叉链表存储结构，递归  
    先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。  
    一旦visit（）失败，则操作失败。  
    后序遍历：同先序；  
    非递归中序遍历：先遍历左子树，然后再遍历根节点，最后遍历右子树，  
    故需要一个空间存放遍历左子树时经过的节点，且  
    后遍历的节点先调用，故该空间可用栈来存放。  
    层序遍历：树是肯定没发直接将一层的节点挨个遍历，它只能将一个树枝上  
    的节点遍历完后再去遍历其他节点（否则不容易检查节点是否被遍历）  
    显而易见，这肯定需要另一个空间存储该树枝上该层下的节点  
    并且先放进去的节点是原节点下一层的节点所以最好先取出来  
    故该存储空间选用队列 继续分析下去， 当根节点进入又推出时，该 左右孩子都进入了，此时需要判断一下其是否有左右孩子。  
    求二叉树深度：递归  
    **主要源代码**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    //--------------二叉树的二叉链表存储表示------------------- 
    #define INIT_SIZE 100 //初始分配量 
    #define CREMENT 10 //分配增量
    
    typedef int status;     //status是函数的类型，其值是函数结果状态代码。
    typedef int TElem;      //自定义
    
    /* 二叉链表 data：存储数据或者权值； lchild,rchild ：左右孩子指针 */
    typedef struct BiTNode{ 
    	TElem data;
    	struct BiTNode *lchild,*rchild;//左右孩子指针 
    }BiTNode,*BiTree;
    
    //链队列 
    typedef struct QNode{ 
    	BiTree data;
    	struct QNode *next;
    }QNode,*Queue;
    
    typedef struct { 
    	Queue front;
    	Queue rear;
    }LQueue;
    
    //顺序栈 
    typedef struct { 
    	BiTree *base;  
    	BiTree *top;
    	int stacksize;     
    }SqStack;   
    
    //---------------基本操作的函数原型说明------------
     
    //二叉树 
    status CreatBiTree(BiTree &T);
           //按先序次序输入二叉树中结点得值（一个字符），空格字符表示空树，
    	   //构造二叉链表表示的二叉树T。
    status visit(TElem e);
           //对结点进行访问 
    status PreOrderTraverse(BiTree T,status(*visit)(TElem e));
           //采用二叉链表存储结构，递归 
    	   //先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
    	   //一旦visit（）失败，则操作失败。
    status InOrderTraverse(BiTree T,status(*visit)(TElem e));
           //同上，中序遍历，递归 
    status PostOrderTraverse(BiTree T,status(*visit)(TElem e));
           //同上，后序遍历 ，递归 
    status InOrderTraverse1(BiTree T,status(*visit)(TElem e));
           //非递归中序遍历1 
    status InOrderTraverse2(BiTree T,status(*visit)(TElem e));
           //非递归中序遍历2 
    status LevelOrderTraverse(BiTree T,status(*visit)(TElem e));
           //同上，层序遍历
    status BiTreeDepth(BiTree T);	
           //求二叉树深度 
     
     //栈 
    status InitStack(SqStack &S);
           //创建栈 
    status Push(SqStack &S,BiTree T); 
           //入栈 
    status StackEmpty(SqStack S);
           //栈判空 
    status GetTop(SqStack S,BiTree &e);
           //取栈顶元素 
    status Pop(SqStack &S,BiTree &e); 
           //出栈 
    
    //队列函数
    status InitQueue(LQueue &L);
           //初始化队列 
    status QueueEmpty(LQueue L);
           //队列判空 
    status EnQueue(LQueue &L,BiTree T);
           //入队列 
    status DeQueue(LQueue &L,BiTree &e);
           //出队列 
    //---------------主函数---------------------------- 
    int main(){ 
    	int i;
    	BiTree T = NULL;
    	
    	int choice;
    	while (1){ 
    		//菜单
    		printf("--------------------------------------------------------------\n");
    		printf("\t\t\t 1---创建一个二叉树\n");
    		printf("\t\t\t 2---先序遍历二叉树\n");
    		printf("\t\t\t 3---中序遍历二叉树1\n");
    		printf("\t\t\t 4---中序遍历二叉树2\n");
    		printf("\t\t\t 5---后序遍历二叉树\n");
    		printf("\t\t\t 6---层序遍历二叉树\n");
    		printf("\t\t\t 7---求二叉树的深度\n");	
    		printf("\t\t\t 退出，输入一个负数！");
    		printf("\n");
    		printf("--------------------------------------------------------------\n");
    		printf("\n");
    		printf("请输入你需要的操作：\n");
    		//退出
    		scanf("%d",&choice);
    		if(choice<=0){ 
    			printf("已退出\n");
    			return 0;
    		} 
    		switch (choice){ 
    			case 1:
    				i = CreatBiTree(T);
    				if(i == -2){ 
    					printf("空间开辟失败\n");
    				}else{ 
    					printf("创建成功！\n");
    				}
    				break;
    			case 2:
    				i = PreOrderTraverse(T,visit);
    				if(i == 1){ 
    					printf("\n先序遍历成功！\n");
    				}else{ 
    					printf("先序遍历失败！\n");
    				}
    				break;
    			case 3:
    				
    				i == InOrderTraverse1(T,visit);
    				if(i == 1){ 
    					printf("\n中序遍历成功！\n");
    				}else{ 
    					printf("中序遍历失败！\n");
    				}
    				
    				break;
    			case 4:
    				i == InOrderTraverse2(T,visit);
    				if(i == 1){ 
    					printf("\n中序遍历成功！\n");
    				}else{ 
    					printf("中序遍历失败！\n");
    				}
    				break;
    			case 5:
    				i == PostOrderTraverse(T,visit);
    				if(i == 1){ 
    					printf("\n后序遍历成功！\n");
    				}else{ 
    					printf("后序遍历失败！\n");
    				}
    				break;
    			case 6:
    				i == LevelOrderTraverse(T,visit);
    				if(i == 1){ 
    					printf("\n层序遍历成功！\n");
    				}else{ 
    					printf("层序遍历失败！\n");
    				}
    				break;
    			case 7:
    				i = BiTreeDepth(T);
    				if(i == 0){ 
    					printf("该树是空树\n");
    				} else{ 
    					printf("该树的深度为%d\n",i);
    				}
    				break;
    			default:
    				printf("选择失败！请重新选择！\n");
    				break; 	 	 	 			
    		}
    		system("pause");   //请按任意键结束 
    		system("cls");     //清屏 
    	}
    	return 0;
    } 
    
    //---------------基本操作的算法描述----------------
    status CreatBiTree(BiTree &T){  
        //按先序次序输入二叉树中结点得值（一个字符），空格字符表示空树，
    	//构造二叉链表表示的二叉树T。
    	char ch = ' ';
    	printf("请输入结点值（空格表示空）：");
    	getchar();    //清空缓存区，否则scanf会直接读取选择后的回车键。 
    	scanf("%c",&ch);
    	if(ch ==' '){ 
    		T = NULL;
    	}else { 
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		if(!T){ 
    			return OVERFLOW;
    		}
    		T->data = ch;     //生成该节点值，第一个则生成根节点 
    		CreatBiTree(T->lchild);//构造左孩子 
    		CreatBiTree(T->rchild);//构造右孩子 
    	}
    	return OK; 
    } 
    
    status visit(TElem e){ 
    	//对结点进行访问,有值则输出该值返回OK，为空则输出$返回ERROR 
    	 if(e){ 
    	 	printf("%c",e);
    	 	return OK;
    	 }else{ 
    	 	return ERROR;
    	 }
    };
     
    //递归调用的三种遍历 
    status PreOrderTraverse(BiTree T,status(*visit)(TElem e)){ 
    	//采用二叉链表存储结构，Visit是对结点操作的应用函数。
    	//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
    	//一旦visit（）失败，则操作失败。
    	if(T){ 
    		if(visit(T->data)==1){ 
    			if(PreOrderTraverse(T->lchild,visit) == 1){ 
    				if(PreOrderTraverse(T->rchild,visit) == 1){ 
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else{ 
    		return OK;
    	}
    }
      
    status InOrderTraverse(BiTree T,status(*visit)(TElem e)){ 
    	//采用二叉链表存储结构，Visit是对结点操作的应用函数。
    	//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
    	//一旦visit（）失败，则操作失败。
    	if(T){ 
    		if(InOrderTraverse(T->lchild,visit) ==1){ 
    			if(visit(T->data)== 1){ 
    				if(InOrderTraverse(T->rchild,visit) == 1){ 
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else{ 
    		return OK;
    	}
    }
    
    status PostOrderTraverse(BiTree T,status(*visit)(TElem e)){ 
    	//采用二叉链表存储结构，Visit是对结点操作的应用函数。
    	//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
    	//一旦visit（）失败，则操作失败。
    	if(T){ 
    		if(PostOrderTraverse(T->lchild,visit) ==1){ 
    			if(PostOrderTraverse(T->rchild,visit) == 1){ 
    				if(visit(T->data) == 1){ 
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else{ 
    		return OK;
    	}
    }
    
    //非递归调用的两种中序遍历 
    status InOrderTraverse1(BiTree T,status(*visit)(TElem e)){ 
    	//非递归中序遍历1。
    	/*中序：先遍历左子树，然后再遍历根节点，最后遍历右子树， 故需要一个空间存放遍历左子树时经过的节点，且 后遍历的节点先调用，故该空间可用栈来存放 */ 
    	BiTree p = NULL;
    	int i = 0;
    	SqStack S = { NULL,NULL,0};
    	i = InitStack(S);  //构造一个栈
    	i = Push(S,T);  //将根指针进栈
    	while(StackEmpty(S) != OK){ 
    		while(GetTop(S,p) == OK && p != NULL){ 
    			//当可取栈顶元素时 
    			i = Push(S,p->lchild);  //一路到最左
    		}
    		i = Pop(S,p);  //结束时会有一个空指针进栈，故需要将其退出
    		if(StackEmpty(S) != OK){ 
    			//访问结点，向右一步 
    			i = Pop(S,p);
    			if(visit(p->data) != 1){ 
    				 return ERROR;
    			} 
    			i = Push(S,p->rchild);
    		} 
    	}
    	return OK;
    }
    
    status InOrderTraverse2(BiTree T,status(*visit)(TElem e)){ 
    	//同上，中序遍历2 
    	int i = 0;
    	SqStack S = { NULL,NULL,0};
    	i = InitStack(S);
    	BiTree p = T;
    	while(p || StackEmpty(S) != OK){ 
    		if(p){ 
    			//根指针进栈，遍历左子树 
    			i = Push(S,p);
    			p = p->lchild;
    		}else{ 
    			//根指针退栈，访问根节点，遍历右子树
    			i = Pop(S,p);
    			if(visit(p->data) != 1){ 
    				return ERROR;
    			} 
    			p = p->rchild;
    		}
    	} 
    	return OK;
    }
        
    status LevelOrderTraverse(BiTree T,status(*visit)(TElem e)){ 
    	//层序遍历，从上到下，从左到右
    	/* 树是肯定没发直接将一层的节点挨个遍历，它只能将一个树枝上 的节点遍历完后再去遍历其他节点（否则不容易检查节点是否被遍历） 显而易见，这肯定需要另一个空间存储该树枝上该层下的节点 并且先放进去的节点是原节点下一层的节点所以最好先取出来 故该存储空间选用队列 继续分析下去， 当根节点进入又推出时，该其左右孩子都进入了，此时 需要判断一下其是否有左右孩子。 */
    	LQueue L = { NULL,NULL};
    	int i = 0;
    	BiTree e;
    	i = InitQueue(L);//初始化队列
    	i = EnQueue(L,T);//根节点入队列
    	while(QueueEmpty(L) != OK){ 
    		i = DeQueue(L,e);
    		if(visit(e->data) != OK){ 
    			return ERROR;
    		}
    		if(e->lchild != NULL){ 
    			//如果有左孩子，则将左孩子入队列
    			EnQueue(L,e->lchild); 
    		}
    		if(e->rchild != NULL){ 
    			EnQueue(L,e->rchild);
    		}
    	}
    	return OK;
    }
           
    status BiTreeDepth(BiTree T){ 
    	//求二叉树深度,同样需要用到递归调用
    	/*对该节点左右孩子节点调用该函数， 并进行比较 ，取节点深度更大的那个 */
    	if(T){ 
    		int m = BiTreeDepth(T->rchild);//定义一个m为右孩子的深度
    		int n = BiTreeDepth(T->lchild);//定义一个n为左孩子的深度
    		int max = m>n?(m+1):(n+1);//求两者最大值，并返回最大值加一
    		return max;  //max为最大值加一，因为返回到上一层深度加一 
    	} else{ 
    		return ERROR;
    	}
    }	
             
    //栈函数
    status InitStack(SqStack &S){ 
    	//构造一个空栈。 
    	S.base = (BiTree*)malloc(INIT_SIZE * sizeof(BiTree));
    	S.top = S.base;
    	S.stacksize = INIT_SIZE;  //初始为100 
    	return OK; 
    }
    
    status Push(SqStack &S, BiTree T){ 
    	//用于存储节点
    	if((S.top - S.base) >= S.stacksize) { 
    		//栈满,追加空间 
    		S.base = (BiTree*)realloc(S.base,(S.stacksize + CREMENT) * (sizeof(BiTree))); 
    		S.top = S.base + S.stacksize;
    		S.stacksize += CREMENT;
    	}
    	*(S.top) = T; //将数据存入栈
    	S.top++;	
    	return OK;
    }
    
    status StackEmpty(SqStack S){ 
    	//对栈进行判空
    	if(S.top == S.base){ 
    		return OK;
    	}else{ 
    		return ERROR;
    	}
    } 
    
    status Pop(SqStack &S,BiTree &e){ 
    	//出栈
    	e = *(S.top-1);	
    	S.top--;
    	return OK; 
    }
    
    status GetTop(SqStack S,BiTree &p){ 
    	//取栈顶元素 
    	if(S.top == S.base){ 
    		return ERROR;
    	}else{ 
    		p = *(S.top-1);
    		return OK;
    	}
    }
        
    
    //队列函数
    status InitQueue(LQueue &L){ 
    	//初始化队列
    	L.front = L.rear = (Queue)malloc(sizeof(QNode));
    	L.front->next = NULL;
    	return OK;
    } 
    
    status QueueEmpty(LQueue L){ 
    	//判空
    	if(L.front == L.rear){ 
    		return OK;
    	} else{ 
    		return ERROR;
    	}
    }
    
    status EnQueue(LQueue &L,BiTree T){ 
    	//入队列
    	Queue p;
    	p = (Queue)malloc(sizeof(QNode));
    	p->data = T;
    	p->next = NULL;
    	L.rear->next = p;
    	L.rear = p;
    	return OK;
    }
    
    status DeQueue(LQueue &L,BiTree &e){ 
    	//出队列
    	Queue p;
    	p = L.front->next;
    	e = p->data;
    	L.front->next = p->next;
    	if(L.rear == p){ 
    		L.rear = L.front;
    	} 
    	free(p);
    	return OK;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70]: /images/20221120/bb61c527558d4617bfada3778efa71a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/8e806329243f477d94f04e868e8b0c34.png