一、背景介绍

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

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

 

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

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

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);
	}

}