学步园

这一小节我们介绍一种特殊的树—二叉树。它的特殊之处在于每个?根节点的叶子节点个数不超过两个，所以我们很容想到通过下面的结构定义二叉树：

typedef char ElemType;

typedef struct BTreeNode
{
	ElemType vaule;
	struct BTreeNode *Lchild;
	struct BTreeNode *Rchild;
}BTreeNode,*BTree;

二叉树的核心操作也是遍历，根据访问节点值与访问左右孩子的先后顺序的不同，有3种遍历方式：前序遍历、中序遍历和后序遍历。前序遍历就是先访问节点值，再访问左孩子，最后访问右孩子；中序遍历就是先访问左孩子，再访问节点值，最后访问右孩子；后续遍历是先访问左孩子，再访问右孩子，最后访问节点值。

//初始化一个节点
BTree initNode(ElemType e)
{
	BTree pnew = (BTree)malloc(sizeof(BTreeNode));
	pnew->vaule = e;
	pnew->Lchild = NULL;
	pnew->Rchild = NULL;
	return pnew;
}

//释放二叉树：采用后续遍历的方式比较容易
void destroyBTree(BTree *T)
{

	if(NULL == *T)
		return;
	destroyBTree(&(*T)->Lchild);
	destroyBTree(&(*T)->Rchild);
	free(*T);
	*T = NULL;
}


//前序遍历
void PreOrderTraverse(BTree T)
{
	
	if(NULL == T)
		return;
	else
	{
		printf("%c",T->vaule);
		PreOrderTraverse(T->Lchild);
		PreOrderTraverse(T->Rchild);
	}

}

//中序遍历
void InOrderTraverse(BTree T)
{
	if(NULL == T)
		return;
	else
	{
		InOrderTraverse(T->Lchild);
		printf("%c",T->vaule);
		InOrderTraverse(T->Rchild);
	}
}

//后序遍历
void PostOrderTraverse(BTree T)
{
	if(NULL == T)
		return;
	else
	{
		PostOrderTraverse(T->Lchild);
		PostOrderTraverse(T->Rchild);
		printf("%c",T->vaule);
	}
}

//求二叉树树的深度
int TreeHeight(BTree T)
{
	int leftlen = 0;
	int rightlen = 0;
	int currMaxLen = 0;
	int len = 0;

	if(NULL == T)
		return 0;
	else
	{

		leftlen = TreeHeight(T->Lchild);
		rightlen = TreeHeight(T->Rchild);
		//获取左右子树高度的最大值
		leftlen>rightlen?currMaxLen = leftlen:currMaxLen = rightlen;
		//与之前记录的最大值相比
		if(len < currMaxLen)
			len = currMaxLen;
	}
	return len+1;
}

//求二叉树中全部节点的个数
int count(BTree T)
{
	int leftCount = 0;
	int rightCount = 0;
	if(NULL == T )
		return 0;
	if(T)
	{
		leftCount = count(T->Lchild);
		rightCount = count(T->Rchild);
	}
	return leftCount+rightCount+1;
}


//树的查找
//通过全局变量将查找到的结过带出来
BTree result = NULL;
void locateElem(BTree T,ElemType e)
{
	
	if(NULL == T)
		return ;

	//如果找到，把它赋给全局变量
	if(T->vaule  == e)
	{
		result = T;
	}

	if(T!= NULL)
	{
		
		locateElem(T->Lchild,e);
		locateElem(T->Rchild,e);
	}

}

BTree findLeftChild(BTree T,ElemType e)
{
	//必须清空全局变量
	result = NULL;
	locateElem(T,e);
	if(NULL == result )
		return NULL;
	else
		return result->Lchild;
}

BTree findRightChild(BTree T,ElemType e)
{
	result = NULL;
	locateElem(T,e);
	if(NULL == result )
		return NULL;
	else
		return result->Rchild;	
}


//插入子树
//参数为：插入的某个数，插入节点的位置（0代表左子树，1代表右子树），插入为这个节点的左子树或者右子树，待插入的子树
bool insertSubTree(BTree T,ElemType e,int LR,BTree subT)
{
	//遍历树，找到插入的位置
	result = NULL;
	locateElem(T,e);
	//判断是否可以插入
	if(0 == LR && NULL == result->Lchild )
	{
		result->Lchild = subT;
		return true;
	}
	if(1 == LR && NULL == result->Rchild)
	{
		result->Rchild = subT;
		return true;
	}
	return false;
}

//删除子树
//参数为：需要被删除的树，删除的位置，删除它的左子树还是右子树
bool deleteSubTree(BTree T,ElemType e,int LR)
{
	//遍历树，找到待的位置
	result = NULL;
	locateElem(T,e);
	//判断是否可以删除
	if(0 == LR && NULL != result->Lchild )
	{
		destroyBTree(&result->Lchild);
		return true;
	}

	if(1 == LR && NULL != result->Rchild)
	{
		destroyBTree(&result->Rchild);
		return true;
	}
	return false;
}

跟树的程序类似，我们必须自己将树中的关系连接起来。其实创建二叉树也可以类的利用递归实现:

void Create(BTree &root )  
{  	 	
	printf("Enter the data \n");
	char tmp;
	scanf(" %c",&tmp);  
	if(tmp =='#')
	{
		
		root = NULL;
	}
	else
	{  
		
		root =(BiNode*) malloc(sizeof(BiNode)); 
		root->data = tmp;
		Create(root->lch);  
		Create(root->rch);
	} 
	
	
} 

但是我更喜欢“自由”的创建它，所以并没有那样写函数。
所谓树的先序、中序、后序遍历，是通过将访问函数写在两次递归的前面、中间和后面实现的。注意到，删除节点时的特点，必须要将这个节点的子树删除，才能删除节点本身，所以采用后序遍历会很方便，不用在像删除链表的节点那样，必须记录被删除节点的前一个位置。跟二叉树查找的有关操作要注意的是，程序是通过全局变量将查找到的节点带出来，所以如果再做跟查找有关的操作，必须先将全局变量初始化。
很多书籍对树避而不谈的原因，是因为对树可以转换成二叉树，而二叉树的操作更加简单、规范。只要把我们之前定义的树的兄弟部分顺时针旋转45度，看起来他就是一颗二叉树了。其实，因为在我们定义时，只通过了孩子、兄弟两根指针定义树，所以这种定义方法也称为二叉树定义法。
还有两种特殊的二叉树需要专门提一下：满二叉树和完全二叉树。
满二叉树就是每一层的叶子节点都是满的，而完全二叉树则是一棵这样的树：如何把它的所有n个节点从上到下，从左到右依次编号，那么与对应的完全二叉树是相同的。也就是说，完全二叉树像是把满二叉树的最后若干的元素去掉。这类二叉树有一个特点：就是按照节点序号可以确定节点之间的父子关系：编号为i的节点的两个子节点序号是2*i和2*i+1；而编号为i的节点的父节点序号是i/2（整除）。所以可以通过数组来保存这类二叉树，这样它的操作会很方便。对于其他的二叉树，可以通过给那些缺失的节点补一个特殊的值来转化成完全二叉树。当然，如果补的节点太多，就得不偿失了。