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'));
printf("\n非递归中序遍历：\n");
NoneRecursionInOrder(*tree);
printf("\n非递归前序遍历：\n");
NoneRecursionPreOrder(*tree);
printf("\n非递归后序遍历：\n");
NoneRecursionPostOrder(*tree);
printf("\n=======================================================\n");
printf("下面执行交换左右子树操作：\n");
SwapLeftRightSubtree(&tree);
printf("先序遍历(#表示空子树)：\n"); |