一、背景介绍

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

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

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

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

      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