二叉树遍历及路径查找

待我称王封你为后i 2023-06-21 10:27 6阅读 0赞

#include<iostream>
    #include<stdio.h>
    #include<math.h>
    #include<malloc.h>
    
    using namespace std;
    #define MAXQSIZE 100
    int k=0;
    char nodes[100];
    //二叉树的二叉链表存储表示
    typedef struct BiNode{
        				
    	char data;						//结点数据域
    	struct BiNode *lchild,*rchild;	//左右孩子指针
    }BiTNode,*BiTree;
    
    //创建队列 
    typedef struct{
        
        struct BiNode*  base[100];
        int front,rear;
    }SqQueue;
    
    //按先序次序输入二叉树中结点的值创建二叉链表表示的二叉树T
    void CreateBiTree(BiTree &T){
        	//ABC##DE#G##F###
    	char ch;
    	cin >> ch;
    	if(ch=='#')  
    		T=NULL;			//递归结束，建空树
    	else
    	{
        							
    		T=(BiTree)malloc(sizeof(BiNode));
    		T->data=ch;//生成根结点
    		nodes[k++]=ch;
    		CreateBiTree(T->lchild);	//递归创建左子树
    		CreateBiTree(T->rchild);	//递归创建右子树
    	}								//else
    }									//CreateBiTree
    
    //先序遍历
    void PreOrderTraverse(BiTree T){
        
    	if(T)
    	{
        
    		printf("%c ",T->data);
    		PreOrderTraverse(T->lchild);
    		PreOrderTraverse(T->rchild); 
    	}
    }
     
    //中序遍历							
    void InOrderTraverse(BiTree T){
          
    	//中序遍历二叉树T的递归算法
    	if(T){
        
    		InOrderTraverse(T->lchild);
    		printf("%c ",T->data);
    		InOrderTraverse(T->rchild);
    	}
    }
    
    //后序遍历 
    void PostOrderTraverse(BiTree T){
        
    	if(T)
    	{
        
    		PostOrderTraverse(T->lchild);
    		PostOrderTraverse(T->rchild);
    		printf("%c ",T->data);
    	}
    }
    
    //层次遍历 
    void LevelOrderTraverse(BiTree T){
          
    	BiTree p;
        SqQueue Q;
        Q.rear=Q.front=0;
        if (T)
    	{
          
    		Q.base[Q.rear]=T;
            Q.rear=(Q.rear+1)%MAXQSIZE;
            while (Q.front !=Q.rear)
            {
         
    			p=Q.base[Q.front];
                printf("%c ",p->data);
                Q.front=(Q.front+1)%MAXQSIZE;
                if (p->lchild)
                {
         
    				Q.base[Q.rear]=p->lchild;
                    Q.rear=(Q.rear+1)%MAXQSIZE;
    				printf("\n");; //使不同层次的结点分行 
    			}
    			
                if (p->rchild)
                {
        
    				Q.base[Q.rear]=p->rchild;
                	Q.rear=(Q.rear+1)%MAXQSIZE;
    			} 
    		} 
    	}
    }
    
    //求给定结点的路径
    void FindPath(BiTree root,char ch){
            
        typedef struct{
        
     		BiTree t;
     		int tag;//tag=0表示访问左子树，tag=1表示访问右子树
     	}stack;
     	
        stack s[100];
    	int top=0,flag=0,i,j=0;
    	for(i=0;i<=k;i++)
    		if(nodes[i]==ch)
    			j++;
    	if(j>1)
    	{
        
    		printf("此结点不唯一！\n");
    		return;
    	}
    	while(root||top)
     	{
        
      		while(root&&root->data!=ch)
      		{
        
       			s[++top].t=root;
    			s[top].tag=0;
    			root=root->lchild;//访问左子树
      		}
      		if(root&&root->data==ch)
      		{
        
       			printf("从根节点到达结点%c的路径为：",ch);
       			for(int i=1;i<=top;i++)
    				printf("%c->",s[i].t->data);//ABC##DE#G##F###
    			flag=1;
    			printf("%c\n",ch);
    			return ;
      		}
      		while(top&&s[top].tag==1)
      			top--;//退栈
      		if(top)
      		{
        
       			s[top].tag=1;
    			root=s[top].t->rchild;//访问右子树
      		}
     	}
     	if(flag==0)
     		printf("不存在此结点！\n\n"); 
     	return;
    }
    
    int main(){
        
    	BiTree tree;
    	int p=-1;
    	char node;
    	printf("1．建立二叉树存储结构\n2．求二叉树的先序遍历\n3．求二叉树的中序遍历\n4．求二叉树的后序遍历\n");
    	printf("5．求二叉树的层次遍历\n6．求给定结点的路径\n0．退出系统\n\n请选择0-6:\n\n");
    	while(p)
    	{
        	printf("请输入：");
    		scanf("%d",&p);
    		printf("\n");
    		switch(p)//ABC##DE#G##F###
    		{
        
    			case 0:
    				break;
    			case 1:
    				printf("请输入建立二叉树的序列:\n");
    				CreateBiTree(tree);
    				break;
    			case 2:	
    				printf("先序遍历:\n");
    				PreOrderTraverse(tree);
    				printf("\n\n");
    				break;
    			case 3:
    				printf("中序遍历:\n");
    				InOrderTraverse(tree);
    				printf("\n\n");
    				break;
    			case 4:
    				printf("后序遍历:\n");
    				PostOrderTraverse(tree);
    				printf("\n\n");
    				break;
    			case 5:
    				printf("层次遍历：\n");
    				LevelOrderTraverse(tree);
    				printf("\n\n");
    				break;
    			case 6:
    				printf("请输入结点名称:\n");
    				cin >> node;
    				FindPath(tree,node); 
    				break;
    			default:
    				break; 
    		}		
    	}	
    	return 0;
    }