二叉树常用操作算法集、解释及注意事项
二叉树是一种常用的数据结构，在程序中也经常需要使用二叉树，但是你所使用语言却并不一定提供了二叉树这种数据类型，所以为了方便使用，我们可以自己实现一个二叉树的数据类型。在需要时就像使用其他已定义的类型一样方便。
下面给出一些本人写的算法和解释（基于C语言），希望对读者写一个二叉树数据类型有所帮助。
0、递归的四条基本法则
由于二叉树中的算法大多使用递归来实现，而且使用递归实现也使代码非常简洁和易于理解。但是写一个好的递归算法并不是一件容易的事，所以我觉得在开始这些算法的讲解之前有必要向大家说说递归实现的一些法则。而且本文中的代码都是以下面的法则作为依据的（至少我是这样认为）。
1）基准情形。必须总有某些基准情形，它无需递归就能解出。
2）不断推进。对于那些需要递归的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
3）设计法则。假设所有的递归调用都能进行。
4）合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
1、数据的储存结构和定义
#define TRUE 1
#define FALSE 0
//定义自己的数据类型
typedef char DataType;
typedef int BOOL;
typedef struct BiNode
{
DataType cData; //用于储存真正的数据
struct BiNode *LChild;//指向左孩子
struct BiNode *RChild;//指向右孩子
}BiNode, *BiTree;
2、基本操作的实现
1）遍历
遍历二叉树是其他操作的基础，二叉树的很多操作都是建立在遍历的基础上的，掌握了遍历对其他算法的理解和实现都大有帮助，那么我们就先来看一看遍历的算法，在二叉树中，根据访问根的次序分为3种，即先序遍历（先访问根，再先序访问左子树，最后先序访问右子树），中序遍历（先中序访问左子树，访问根，最后中序访问右子树）和后序遍历（先后序访问左子树，再后序访问右子树，最后访问根），还有一种就是层次性遍历（借助队列进行），它们的实现如下：
BOOL PreOrderTraverse(BiTree BT, BOOL(*Visit)(BiNode*))
{
//先序遍历二叉树，对每个结点调用Visit一次，且仅一次
//实现对结点的某种操作，Visit失败，则遍历失败
if(BT != NULL)
{
if((*Visit)(BT))//访问根结点
{
if(PreOrderTraverse(BT->LChild, Visit))//先序访问左子树
if(PreOrderTraverse(BT->RChild, Visit))//先序访问右子树
return TRUE;
return FALSE;
}
}
else
return TRUE;
}
//----------------------------------------------------------------------
BOOL InOrderTraverse(BiTree BT, BOOL(*Visit)(BiNode*))
{
//中序遍历二叉树，对每个结点调用Visit一次，且仅一次
//实现对结点的某种操作，Visit失败，则遍历失败
if(BT != NULL)
{
if(InOrderTraverse(BT->LChild, Visit))//中序访问左子树
{
if((*Visit)(BT))//访问根结点
if(InOrderTraverse(BT->RChild, Visit))//中序访问右子树
return TRUE;
return FALSE;
}
}
else
return TRUE;
}
//----------------------------------------------------------------------
BOOL PostOrderTraverse(BiTree BT, BOOL(*Visit)(BiNode*))
{
//后序遍历二叉树，对每个结点调用Visit一次，且仅一次
//实现对结点的某种操作，Visit失败，则遍历失败
if(BT != NULL)
{
if(PostOrderTraverse(BT->LChild, Visit))//后序访问左子树
{
if(PostOrderTraverse(BT->RChild, Visit))//后序访问右子树
if((*Visit)(BT))//访问根结点
return TRUE;
return FALSE;
}
}
else
return TRUE;
}
//----------------------------------------------------------------------
BOOL LevelOrderTraverse(BiTree BT, BOOL(*Visit)(BiNode*))
{
//层次性遍历二叉树，对每个结点调用Visit一次，且仅一次
//实现对结点的某种操作，Visit失败，则遍历失败
//使用数组模拟一个循环队列
if(BT == NULL)
return TRUE;
const int nCapicity = 300;
BiTree DT[nCapicity];
int nFront = 0, nRear = 1;
DT[0] = BT; //根结点入队
int nSize = 1;
while(nSize != 0) //队列非空
{
if(DT[nFront]->LChild)
{
//左子树非空，左子树入队
DT[nRear] = DT[nFront]->LChild;
++nRear;
++nSize;
}
if(DT[nFront]->RChild)
{
//右子树非空，右子树入队
DT[nRear] = DT[nFront]->RChild;
++nRear;
++nSize;
}
//访问队头元素，并出队
if(!(*Visit)(DT[nFront]))
return FALSE;
++nFront;
--nSize;
if(nSize > nCapicity)
return FALSE;
if(nRear == nCapicity)
nRear = 0;
if(nFront == nCapicity)
&nb
补充：综合编程 , 其他综合 ,
