rightDepth = GetDepth(pBTree->rchild); // 获取右子树的深度
distance = leftDepth > rightDepth leftDepth - rightDepth : rightDepth - leftDepth;
return distance > 1 0 : IsBalanceBinaryTree(pBTree->lchild) && IsBalanceBinaryTree(pBTree->rchild);
}
}
//
// 获取叶子结点的个数
int GetLeafCount(BTree *pBTree)
{
int count = 0;
if (pBTree != NULL)
{
if (IsLeaf(*pBTree))
{
count++;
}
else
{
count = GetLeafCount(pBTree->lchild) + GetLeafCount(pBTree->rchild);
}
}
return count;
}
//
// 获取度为1的结点的个数
int GetCountOfOneDegree(BTree *pBTree)
{
int count = 0;
if (pBTree != NULL)
{
if ((pBTree->lchild != NULL && pBTree->rchild == NULL) || (pBTree->lchild == NULL && pBTree->rchild != NULL))
{
count++;
}
count += GetCountOfOneDegree(pBTree->lchild) + GetCountOfOneDegree(pBTree->rchild);
}
return count;
}
//
// 获取度为2的结点的个数
int GetCountOfTwoDegree(BTree *pBTree)
{
int count = 0;
if (pBTree != NULL)
{
if (pBTree->lchild != NULL && pBTree->rchild != NULL)
{
count++;
}
count += GetCountOfTwoDegree(pBTree->lchild) + GetCountOfTwoDegree(pBTree->rchild);
}
return count;
}
//
// 获取二叉树的结点的总数
int GetNodesCount(BTree *pBTree)
{
int count = 0;
if (pBTree != NULL)
{
count++;
count += GetNodesCount(pBTree->lchild) + GetNodesCount(pBTree->rchild);
}
return count;
}
//
// 交换左右子树
void SwapLeftRightSubtree(BTree **pBTree)
{
BTree *tmp = NULL;
if (*pBTree != NULL)
{
// 交换当前结点的左右子树
tmp = (*pBTree)->lchild;
(*pBTree)->lchild = (*pBTree)->rchild;
(*pBTree)->rchild = tmp;
SwapLeftRightSubtree(&(*pBTree)->lchild);
SwapLeftRightSubtree(&(*pBTree)->rchild);
}
}
//
// 判断值e是否为二叉树中某个结点的值，返回其所在的层数，返回0表示不在树中
int GetLevelByValue(BTree *pBTree, ElemType e)
{
int leftDepth = 0;
int rightDepth = 0;
int level = 0;
if (pBTree->data == e)//这里的1是相对于以pBTree为根节点的层数值。
{
return 1;
}
if (pBTree->lchild != NULL)//leftDepth所代表的层数是相对以pBTree的左节点为根的树的层数
{
leftDepth = GetLevelByValue(pBTree->lchild, e);
}
if (pBTree->rchild != NULL)
{
// rightDepth所代表的层数是相对以pBTree的右节点为根的树的层数
rightDepth = GetLevelByValue(pBTree->rchild, e);
}
//
// 查找结果要么在左子树找到，要么在右子树中找到，要么找不到
if (leftDepth > 0 && rightDepth == 0) // 在左子树中找到
{
level = leftDepth;
}
else if (leftDepth == 0 && rightDepth > 0) // 在右子树中找到
{
level = rightDepth;
}
if (leftDepth != 0 || rightDepth != 0) // 判断是否找到该结点
{
level++;
}
return level;
}
//
// 非递归中序遍历
void NoneRecursionInOrder(BTree tree)
{
Stack s;
StackElemType *p = NULL, *q;
q = (StackElemType *)malloc(sizeof(StackElemType)); // 用于指向退栈元素的地址
InitStack(&s);
p = &tree;
while (p || !IsStackEmpty(s))
{
if (p)
{
Push(&s, *p);
p = p->lchild;
}
else
{
Pop(&s, q);
printf("%c", q->data);
p = q->rchild;
}
}
free(q);
}
//
// 非递归前序遍历
void NoneRecursionPreOrder(BTree tree)
{ |