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)
{
Stack s;
StackElemType *p = NULL, *q;

q = (StackElemType *)malloc(sizeof(StackElemType)); // 用于指向退栈元素的地址
InitStack(&s);
p = &tree;

while (p || !IsStackEmpty(s))
{
while (p)
{
printf("%c", p->data); // 访问根结点
Push(&s, *p); // 根结点指针入栈
p = p->lchild; // 一直向左走到底
}

Pop(&s, q);
p = q->rchild; // 向右走一步
}

free(q);
}

//
// 非递归后序遍历
void NoneRecursionPostOrder(BTree tree)
{
StackElemType *stack[STACK_INIT_SIZE], *p;
int tag[STACK_INIT_SIZE], // 值只有0和1，其中0表示该结点的左子树已经访问
// 值为1表示该结点的右子树已经访问
top = 0; // 栈顶指示器

p = &tree;

while (p || top != 0)// 树未遍历完毕或者栈不空
{
while (p)
{
top++;
stack[top] = p;
tag[top] = 0;
p = p->lchild; // 从根开始向左走到底
}

if (top > 0) // 栈不空
{
if (tag[top] == 1)// 表示已经访问该结点的右子树，并返回
{
p = stack[top--]; // 退栈
printf("%c", p->data);

p = NULL; // 下次进入循环时，就不会再遍历左子树
}
else // 表示刚从该结点的左子树返回，现在开始遍历右子树
{
p = stack[top]; // 取栈顶元素
if (top > 0) // 栈不空
{
p = p->rchild;
tag[top] = 1; // 标识该结点的右子树已经访问
}
}
}
}
}

int main()
{
BTree *tree = NULL;

printf("按先序输入二叉树结点元素的值，输入#表示空树：\n");

freopen("test.txt", "r", stdin);

if (CreateBinaryTree(&tree) == OK) // 创建二叉树
{
printf("二叉树创建成功！\n");
}

printf("先序遍历(#表示空子树)：\n");
PreOrderTraverse(tree);

printf("\n中序遍历(#表示空子树)：\n");
InOrderTraverse(tree);

printf("\n后序遍历(#表示空子树)：\n");
PostOrderTraverse(tree);

printf("\n树的深度为：%d\n", GetDepth(tree));

printf("\n层序遍历：\n");
LevelOrderTraverse(tree);

printf("\n遍历叶子结点:\n");
TraverseLeafNodes(tree);

printf("\n叶子结点的个数：%d\n", GetLeafCount(tree));
printf("度为1的结点的个数：%d\n", GetCountOfOneDegree(tree));
printf("度为2的结点的个数：%d\n", GetCountOfTwoDegree(tree));
printf("\n二叉树的结点总数为：%d\n", GetNodesCount(tree));

printf("\n该二叉树是否为平衡二叉树？\n");
if (IsBalanceBinaryTree(tree))
{
printf("Yes!\n");
}
else
{
printf("No!\n");
}

printf("\n结点值为A的结点在第%d层\n", GetLevelByValue(tree, 'A'));
printf("\n结点值为B的结点在第%d层\n", GetLevelByValue(tree, 'B'));
printf("\n结点值为C的结点在第%d层\n", GetLevelByValue(tree, 'C'));
printf("\n结点值为D的结点在第%d层\n", GetLevelByValue(tree, 'D'));
printf("\n结点值为E的结点在第%d层\n", GetLevelByValue(tree, 'E'));
printf("\n结点值为F的结点在第%d层\n", GetLevelByValue(tree, 'F'));
printf("\n结点值为G的结点在第%d层\n", GetLevelByValue(tree, 'G'));
printf("\n结点值为M的结点在第%d层\n", GetLevelByValue(tree, 'M'));