raverse(pBTree->lchild); // 中序遍历左子树
printf("%c", pBTree->data); // 中序访问根结点
InOrderTraverse(pBTree->rchild); // 中序遍历右子树
}
}
/*****************************************************************************
* 方法名：PostOrderTraverse
* 描述： 后序遍历二叉树
* 参数： pBTree--指向BTree结构体的指针
******************************************************************************/
void PostOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
PostOrderTraverse(pBTree->lchild); // 后序遍历左子树
PostOrderTraverse(pBTree->rchild); // 后序遍历右子树
printf("%c", pBTree->data); // 后序访问根结点
}
}
/*****************************************************************************
* 方法名：LevelOrderTraverse
* 描述： 层序遍历二叉树
* 参数： pBTree--指向BTree结构体的指针
******************************************************************************/
void LevelOrderTraverse(BTree *pBTree)
{
Queue queue; // 队列变量
QueueElemType e; // 队列元素指针变量
InitializeQueue(&queue); // 初始化队列
if (pBTree != NULL)
{
EnQueue(&queue, *pBTree); // 将根结点指针入队
}
while (!IsQueueEmpty(queue))
{
DeQueue(&queue, &e);
printf("%c", e.data);
if (e.lchild != NULL) // 若存在左孩子，则左孩子入队
{
EnQueue(&queue, *e.lchild);
}
if (e.rchild != NULL) // 若存在右孩子，则右孩子入队
{
EnQueue(&queue, *e.rchild);
}
}
}
/*****************************************************************************
* 方法名：GetDepth
* 描述： 获取树的深度
* 参数： pBTree--指向BTree结构体的指针
* 返回值：树的深度
******************************************************************************/
int GetDepth(BTree *pBTree)
{
int depth = 0;
int leftDepth = 0;
int rightDepth = 0;
if (pBTree)
{
leftDepth = GetDepth(pBTree->lchild); // 获取左子树的深度
rightDepth = GetDepth(pBTree->rchild); // 获取右子树的深度
depth = leftDepth > rightDepth leftDepth + 1: rightDepth + 1;
}
return depth;
}
/*****************************************************************************
* 方法名：IsLeaf
* 描述： 判断该结点是否为叶子结点
* 参数： node--结点
* 返回值：1--表示叶子结点，0--表示非叶子结点
******************************************************************************/
int IsLeaf(BTree node)
{
if (node.lchild == NULL && node.rchild == NULL)
{
return 1;
}
return 0;
}
/*****************************************************************************
* 方法名：TraverseLeafNodes
* 描述： 遍历所有的叶子结点
* 参数： pBTree--指向BTree结构体的指针
******************************************************************************/
void TraverseLeafNodes(BTree *pBTree)
{
if (pBTree != NULL)
{
if (1 == IsLeaf(*pBTree))
{
printf("%c", pBTree->data);
}
else
{
TraverseLeafNodes(pBTree->lchild);
TraverseLeafNodes(pBTree->rchild);
}
}
}
//
// 判断一棵二叉树是否为平衡二叉树
// 平衡二叉树的定义: 如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树
// 算法思路：递归判断每个节点的左右子树的深度是否相差大于1，如果大于1，说明该二叉树不
// 是平衡二叉树，否则继续递归判断
int IsBalanceBinaryTree(BTree *pBTree)
{
int leftDepth = 0;
int rightDepth = 0;
int distance = 0;
if (pBTree != NULL)
{
leftDepth = GetDepth(pBTree->lchild); // 获取左子树的深度
|