二叉树的遍历

ゝ一纸荒年。 2021-09-10 23:56 309阅读 0赞

按照一定次序访问树中所有结点  
 并且每个结点的值仅被访问一次  
 二叉树  
     D  
 ↙ ↘  
 L       R  
 先根遍历：DLR  
 中先遍历：LDR  
 后根遍历：LRD

遍历的顺序是先左后右

![Center][]

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    typedef struct  btnode
    	  {char    data;            
    	   struct  btnode  *lchild;//左结点
    	   struct  btnode  *rchild;//右结点  
    	   }NODE; //定义一个结点结构体
    
    NODE  * create(NODE *p)    //创建一颗树
     {	char ch;
    	NODE *t;
        scanf("%c",&ch);
    	if(ch==' ')  p=NULL;
    	else
    	 {p->data=ch;
    	  t=(NODE *)malloc(sizeof(NODE));
    	  p->lchild=create(t);
    	  t=(NODE*)malloc(sizeof(NODE));
    	  p->rchild=create(t);
    	 }
    	  return p;
     }
    
    void preorder(NODE *root)   //先根遍历
    {	if (root!=NULL)
    	   { printf( " %c", root->data);
    		 preorder(root->lchild);
    		 preorder(root->rchild);
    		}
       return;
     }
    
    void   inorder (NODE *root)  //中根遍历  递归调用inorder
    {	if (root!=NULL)
    	  {	inorder(root->lchild);
    		printf(" %c ", root->data);
    		inorder(root->rchild);
    	  }
    	return;
     }
    
    void postorder(NODE *root)  //后根遍历
    {	if (root!=NULL)
    	 {	postorder (root->lchild);
    		postorder (root->rchild);
    		printf(" %c ", root->data);
    	  }
         return;
    }
    
    void main()
    {	
    	NODE *root,*q,n;
    	NODE *create(NODE *p);  //create()  创建树 
    	void preorder(NODE *root);
    	void inorder(NODE *root);
    	void postorder(NODE *root);
    
     	printf("At  the first,we create a tree\n");
    	printf("Please input nodes of tree\n"); 
    
    	int t;
    	q=&n;
    	root=create(q);
    
    	if  (root==NULL)   
    		printf("It's  an empty  tree!\n");
    	else
    	   {
    		printf("  1.xian gen \n");
    	    printf("  2.zhong gen \n");
    	    printf("  3.hou gen \n");
    		printf("  Please choose  a  kind  of  order\n");
    		scanf("%d",&t);
    
    		switch(t)
    		   {
    			case 1: preorder(root);  break;
    			case 2: inorder(root);   break;
    			case 3:postorder(root);   break;
    			default: printf(" The error!");
    		   }
    		}
    }

[Center]: /images/20210813/94acb27ca85d4078a92cdedc48ba2aea.png