树与二叉树的深度优先与广度优先算法（递归与非递归）

本博客前面文章已对树与二叉树有过简单的介绍，本文主要是重点介绍有关二叉树的一些具体操作与应用

阅读本文前，可以先参考本博客 各种基本算法实现小结（三）—— 树与二叉树 和 各种基本算法实现小结（二）—— 堆 栈

二叉树

深度层数、叶子数、节点数和广度优先算法

以及树的先序、中序、后序的递归与非递归（深度优先）

测试环境：VS2008（C）

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define DataType char
int d_tree=0;  /* tree's depth */
int l_tree=0;  /* tree's leaf */
int n_tree=0;  /* tree's node */
/**************************************/
/********     树的结构定义     ********/
/**************************************/
struct _tree
{
	DataType data;
	struct _tree *lchild;
	struct _tree *rchild;
};
typedef struct _tree tree, *ptree;
/**************************************/
/********     栈的结构定义     ********/
/**************************************/
struct _node
{
	ptree pt;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _stack
{
	int size;
	pnode ptop;
};
typedef struct _stack stack, *pstack;
/**************************************/
/********     堆的结构定义     ********/
/**************************************/
struct _queue
{
	pnode front;
	pnode rear;
};
typedef struct _queue queue, *pqueue;
/**************************************/
/********     栈的数据操作     ********/
/**************************************/
pstack init_stack()
{
	pnode pn=NULL;
	pstack ps=NULL;
	pn=(pnode)malloc(sizeof(node));
	ps=(pstack)malloc(sizeof(stack));
	pn->pt=NULL;
	pn->next=NULL;
	ps->ptop=pn;
	return ps;
}
int empty_stack(pstack ps)
{
	if(ps->ptop->next==NULL)
		return 1;
	else
		return 0;
}
void push_stack(pstack ps, ptree pt) /* flag for post tree: 0 for lchild; 1 for rchild */
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->pt=pt;
	pn->next=ps->ptop;
	ps->ptop=pn;
}
ptree pop_stack(pstack ps)
{
	ptree pt=NULL;
	pnode pn=NULL;
	if(!empty_stack(ps))
	{
		pn=ps->ptop;
		ps->ptop=ps->ptop->next;
		pt=pn->pt;
		free(pn);
	}
	return pt;
}
ptree gettop_stack(pstack ps)
{
	if(!empty_stack(ps))
		return ps->ptop->pt;
}
/**************************************/
/********     堆的数据操作     ********/
/**************************************/
queue init_queue()
{
	pnode pn=NULL;
	queue qu;
	pn=(pnode)malloc(sizeof(node));
	pn->pt=NULL;
	pn->next=NULL;
	qu.front=qu.rear=pn; /* init: pn is header */
	return qu;
}
int empty_queue(queue &qu)
{
	if(qu.front==qu.rear)
		return 1;
	else
		return 0;
}
void en_queue(queue &qu, ptree pt)
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->pt=pt;
	pn->next=qu.rear->next;
	qu.rear->next=pn;
	qu.rear=qu.rear->next;
}
ptree de_queue(queue &qu)
{
	ptree pt=NULL;
	pnode pn=NULL;
	if(!empty_queue(qu))
	{
		pn=qu.front->next;
		if(pn==qu.rear) /* qu is null: qu.front==qu.rear */
			qu.rear=qu.front;
		else
			qu.front->next=qu.front->next->next;
		pt=pn->pt;
		free(pn);
	}
	return pt;
}
/**************************************/
/********     树的数据操作     ********/
/**************************************/
ptree init_tree()
{
	ptree pt=NULL;
	pt=(ptree)malloc(sizeof(tree));
	pt->data='0';
	pt->lchild=NULL;
	pt->rchild=NULL;
	return pt;
}
ptree create_tree()
{
	char ch;
	ptree pt=NULL;
	
	scanf("%c", &ch);
	getchar();	
	if(ch==' ')
		return NULL;
	else
	{
		pt=(ptree)malloc(sizeof(tree));
		pt->data=ch;
		pt->lchild=create_tree();
		pt->rchild=create_tree();
	}
	return pt;
}
int depth_tree(ptree pt)
{
	int l_len, r_len;
	ptree p=pt;
	if(p==NULL)
		return 0;
	else
	{
		l_len=depth_tree(p->lchild);
		r_len=depth_tree(p->rchild);
		return l_len>r_len?(l_len+1):(r_len+1);
	}
}
void leaf_tree(ptree pt)
{
	ptree p=pt;
	if(p->lchild==NULL && p->rchild==NULL)
		l_tree++;
	else
	{
		leaf_tree(p->lchild);
		leaf_tree(p->rchild);
	}
}
void node_tree(ptree pt)
{
	ptree p=pt;
	if(p!=NULL)
	{
		n_tree++;
		node_tree(p->lchild);
		node_tree(p->rchild);
	}
}
void print_pretree(ptree pt)
{
	if(pt!=NULL)
	{
		printf("%3c", pt->data);
		print_pretree(pt->lchild);
		print_pretree(pt->rchild);
	}
}
void print_pretree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ps=init_stack();
	p=pt;
	while(p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			printf("%3c", p->data);
			push_stack(ps, p);
			p=p->lchild;
		}
		if(!empty_stack(ps))
		{
			p=pop_stack(ps);
			p=p->rchild;
		}
	}
}
void print_midtree(ptree pt)
{
	if(pt!=NULL)
	{
		print_midtree(pt->lchild);
		printf("%3c", pt->data);
		print_midtree(pt->rchild);
	}
}
void print_midtree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ps=init_stack();
	p=pt;
	while (p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			push_stack(ps, p);
			p=p->lchild;		
		}
		if(!empty_stack(ps))
		{			
			p=pop_stack(ps);
			printf("%3c", p->data);
			p=p->rchild;
		}
	}
}
void print_posttree(ptree pt)
{
	if(pt!=NULL)
	{
		print_posttree(pt->lchild);		
		print_posttree(pt->rchild);	
		printf("%3c", pt->data);
	}
}
void print_posttree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ptree p2=NULL;
	ptree lastvisit=NULL;
	ps=init_stack();
	p=pt;
	while (p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			push_stack(ps, p);
			p=p->lchild;					
		}
		p2=gettop_stack(ps); /* top: rchild==null or sub_root */
		if(p2->rchild==NULL || p2->rchild==lastvisit)
		{
			printf("%3c", p2->data);
			lastvisit=pop_stack(ps); /* pop */
		}
		else
			p=p2->rchild;
	}	
}
void bfs_tree(ptree pt)
{
	ptree p=NULL;
	queue qu;
	qu=init_queue();
	p=pt;
	if(p!=NULL)
	{
		en_queue(qu, p);
		while (!empty_queue(qu))
		{
			p=de_queue(qu);
			printf("%3c", p->data);
			if(p->lchild!=NULL)			
				en_queue(qu, p->lchild);
			if(p->rchild!=NULL)
				en_queue(qu, p->rchild);
		}
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	ptree pt=NULL;
	/*pt=init_tree();*/
	
	printf("Create tree:/n");
	pt=create_tree();
	/************  recursion ************/
	printf("/n/nrecursion...");
	printf("/npre tree.../n");
	print_pretree(pt);
	printf("/nmid tree.../n");
	print_midtree(pt);
	printf("/npost tree.../n");
	print_posttree(pt);
	/************  stack ************/
	printf("/n/nstack, non recursion:");
	printf("/npre tree.../n");
	print_pretree2(pt);
	printf("/nmid tree.../n");
	print_midtree2(pt);
	printf("/npost tree.../n");
	print_posttree2(pt);
	/**********  bfs tree **********/
	printf("/n/nbfs_tree:/n");
	bfs_tree(pt);
	/********* tree operation ********/
	printf("/n/ntree operation:");
	d_tree=depth_tree(pt);
	leaf_tree(pt);
	node_tree(pt);
	printf("/ntree's depth: %d", d_tree);
	printf("/ntree's leaf: %d", l_tree);
	printf("/ntree's node: %d", n_tree);
	printf("/n");
	return 0;
}

运行结果：

======================================

===================================================================