一、背景介绍

二叉树结构有根结点-左子树-右子树组成，每个子树又可分成根结点-左子树-右子树......

这说明二叉树具有递归性质，利用递归的思想实现二叉树的创建与遍历。

二、递归思想创建/遍历二叉树

先左（子树）后右（子树）的顺序创建二叉树

  

   

    

     

    
    

     

      void create_btree(btree_pnode *T)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	datatype_bt ch;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//如果结点不存在，则输入时，用#表示
     
    
   

    

     

    
    

     

      	scanf("%c",&ch);
     
    
   

    

     

    
    

     
	if('#' == ch)
     
    
   

    

     

    
    

     

      		*T = NULL;
     
    
   

    

     

    
    

     
	else{
     
    
   

    

     

    
    

     
		//创建根结点
     
    
   

    

     

    
    

     

      		*T = (btree_pnode)malloc(sizeof(btree_node));
     
    
   

    

     

    
    

     
		if(NULL == *T){
     
    
   

    

     

    
    

     

      			perror("malloc");
     
    
   

    

     

    
    

     
			exit(1);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		(*T)->data = ch;
     
    
   

    

     

    
    

     
		//创建左子树
     
    
   

    

     

    
    

     

      		create_btree(&(*T)->lchild);
     
    
   

    

     

    
    

     
		//创建右子树
     
    
   

    

     

    
    

     

      		create_btree(&(*T)->rchild);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

先左后右的遍历，先序遍历结点（第一次遍历结点输出）

A B C D E F G H K

  

   

    

     

    
    

     

      void pre_order(btree_pnode t)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(t != NULL){
     
    
   

    

     

    
    

     
		//访问根结点
     
    
   

    

     

    
    

     

      		printf("%c",t->data);
     
    
   

    

     

    
    

     
		//先序遍历左子树
     
    
   

    

     

    
    

     

      		pre_order(t->lchild);
     
    
   

    

     

    
    

     
		//先序遍历右子树
     
    
   

    

     

    
    

     

      		pre_order(t->rchild);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

先左后右的遍历，中序遍历结点（第二次遍历结点输出）

B D C A E H G K F

  

   

    

     

    
    

     

      void mid_order(btree_pnode t)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(t != NULL){
     
    
   

    

     

    
    

     
		//中序遍历左子树
     
    
   

    

     

    
    

     

      		mid_order(t->lchild);
     
    
   

    

     

    
    

     
		//访问根结点
     
    
   

    

     

    
    

     

      		printf("%c",t->data);
     
    
   

    

     

    
    

     
		//中序遍历右子树
     
    
   

    

     

    
    

     

      		mid_order(t->rchild);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

先左后右的遍历，后序遍历结点（第三次遍历结点输出）

D C B H K G F E A

  

   

    

     

    
    

     

      void post_order(btree_pnode t)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(t != NULL){
     
    
   

    

     

    
    

     
		//后序遍历左子树
     
    
   

    

     

    
    

     

      		post_order(t->lchild);
     
    
   

    

     

    
    

     
		//后序遍历右子树
     
    
   

    

     

    
    

     

      		post_order(t->rchild);
     
    
   

    

     

    
    

     
		//访问根结点
     
    
   

    

     

    
    

     

      		printf("%c",t->data);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

二、按层遍历

A B E C F D G H K

按照从左向右的顺序遍历一层的结点，同时将这个结点的左右子结点存放到队列中，以便下一层的遍历。

算法思路：先遍历一层根结点，将根结点下的左右子结点（若存在）入队。第二层的结点出队，遍历结点同时将结点的左右子节点入队。第二层结点遍历完成，说明此时第三层的结点元素已经存在队列中，开始第三层结点的遍历......直到队列为空！

  

   

    

     

    
    

     

      void level_order(btree_pnode t)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	link_pqueue q;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	init_linkqueueu(&q);  //初始化链式队列
     
    
   

    

     

    
    

     
	while(t != NULL){
     
    
   

    

     

    
    

     

      		printf("%c",t->data);
     
    
   

    

     

    
    

     
		if(t->lchild != NULL)
     
    
   

    

     

    
    

     

      			in_linkqueue(t->lchild,q);
     
    
   

    

     

    
    

     
		if(t->rchild != NULL)
     
    
   

    

     

    
    

     

      			in_linkqueue(t->rchild,q);
     
    
   

    

     

    
    

     
		if(is_empty_linkqueue(q))
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      			out_linkqueue(&t,q);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/81174245