typedef char BTreeData;
// 二叉树的结点
typedef struct _btreeNode
{
BTreeData data;
struct _btreeNode *lchild; // 指向左孩子结点的指针
struct _btreeNode *rchild; // 指向右孩子结点的指针
}BTreeNode;
// 二叉树
typedef struct _btree
{
BTreeNode *root; // 指向二叉树的根节点
int count; // 记录二叉树结点的个数
}BTree;
BTree *Create_BTree()
{
BTree *btree = (BTree*)malloc(sizeof(BTree)/sizeof(char));
if (btree == NULL)
return NULL;
btree->count = 0;
btree->root = NULL;
return btree;
}
//非递归后序遍历
void last2_order (BTreeNode *node)
{
if (node == NULL)
{
errno = ERROR;
return;
}
LinkStack *Stack = Create_Stack ();
BTreeNode *tmp = node; //指向当前节点
BTreeNode *pre = NULL; //指向被输出的节点
Push (Stack,tmp);
while (StackEmpty (Stack) != TRUE)
{
GetTop (Stack,&tmp);
//若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出
if(tmp->lchild == NULL && tmp->rchild == NULL
|| pre != NULL &&(tmp->lchild == pre || tmp->rchild == pre))
{
Pop (Stack,&tmp);
printf("L",tmp->data);
pre = tmp;//指向被输出的节点
continue;
}
if(tmp->rchild)
{
Push (Stack,tmp->rchild);
}
if(tmp->lchild)
{
Push (Stack,tmp->lchild);
}
}
}
