树的遍历

你的名字 2023-05-21 11:54 9阅读 0赞

[树的遍历][Link 1]

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    #define m 3
    #define MAXLEN 100
      
    typedef char datatype;
    typedef struct node {
        
         datatype data;
         struct node *child[m];
    } node;
    typedef  node *tree;
    tree  CreateTree(); /*按前序遍历顺序建立一棵3度树,返回树根地址  */
    void LevelOrder(tree t);    /* t为指向树根结点的指针,输出树的层次遍历序列*/
    void PreOrder(tree t);    /* t为指向树根结点的指针,输出树的前序遍历序列*/
    void PostOrder(tree t); /* t为指向树根结点的指针,输出树的后序遍历序列*/
    int main()
    {
        
       tree t;
       t=CreateTree();
       printf("\nthe LevelOrder is:");
       LevelOrder(t);
       printf("\nthe PreOrder is:");
       PreOrder(t);
       fflush(stdin); //fflush清空缓冲区残余信息
       printf("\nthe PostOrder is:");
       PostOrder(t);
       system("pause");
       return 0;
    }
    tree  CreateTree()
     {
        
       int i;
       char ch;
       tree t;
       if ((ch=getchar())=='#')  t=NULL;
       else{
        
            t=(tree) malloc (sizeof(node));
            t->data=ch;
            for (i=0;i<m;++i)
                t->child[i]= CreateTree();
        }
       return t;
    }
    void LevelOrder(tree t){
          /* t为指向树根结点的指针,输出树的层次遍历序列
    						  队列不为空->出队->依次访问p的所有子女结点，并进队并进队*/
    	tree queue[MAXLEN],q;
    	int front,rear;
    	front=rear=0;
    	printf("%c",t->data);
    	queue[rear++]=t;
    	while(front<rear){
        
    		q=queue[front++];
    		for(int i=0;i<m;i++){
        
    			if(q->child[i]){
        
    				printf("%c",q->child[i]->data);
    				queue[rear++]=q->child[i];
    			}
    		}
    	}
    }
    void PreOrder(tree t){
         
    	int i=0;/* t为指向树根结点的指针,输出树的前序遍历序列*/
    		if(t!=NULL){
        
    			printf("%c",t->data);
    			for(i=0;i<m;i++){
        
    				PreOrder(t->child[i]);
    		} 
    		} 
    		
    }
    void PostOrder(tree t){
         /* t为指向树根结点的指针,输出树的后序遍历序列*/
     	 int i;
        if (t)
            {
        
                for (i=0;i<m;i++)
                    PostOrder(t->child[i]);
                printf("%c",t->data);
            }
    
        }
    
    输入样例：
    
    ab###ce###fh###i####g###d###
    
    
    
    输出样例：
    
    the LevelOrder is:abcdefghi
    the PreOrder is:abcefhigd
    the PostOrder is:behifgcda

[Link 1]: https://blog.csdn.net/qq_36289725/article/details/78558512