//4.4 二叉树的遍历方法
#define n0 100
struct node
{
int data;
int llink,rlink;
};
node tree[n0+1];
int root; //树的根节点位置
//递归方式实现前序，中序，后序遍历
void preorder(int p)
{
if(!p)
{//如果根节点不为空
cout<<tree[p].data;
preorder(tree[p].llink);
preorder(tree[p].rlink);
}
}
void inorder(int p)
{
if(!p)
{//如果根节点不为空
inorder(tree[p].llink);
cout<<tree[p].data;
inorder(tree[p].rlink);
}
}
void postorder(int p)
{
if(!p)
{//如果根节点不为空
postorder(tree[p].llink);
postorder(tree[p].rlink);
cout<<tree[p].data;
}
}
//非递归算法的前序，中序，后序遍历
//前序列的算法思想 ：从二叉树的根节点开始，令指针变量P指向根节点，访问当前节点p，并将p压入栈中。
//然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空
//从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。
void preorder()
{
int s[n0+1]; //栈
int t; //栈指针
int p = root;//树指针
while(p||t)
{//当p不为空或者栈不为空时
if(p)
{//当期指针不为空时候
cout<<tree[p].data; //访问当前节点
s[++t] = p; //当前地址入栈
p = tree[p].llink; //p指向p的左孩子
}
else
{//如果p指向的p的左孩子为空，就是没有左孩子
p = s[t--];//p返回到它的父亲节点
p = tree[p].rlink; //p指向它的父亲节点的右孩子
}
}
}
//中序算法：和前序算法基本上一致，但是数据访问在出栈的时候
//前序列的算法思想 ：从二叉树的根节点开始，令指针变量p指向根节点，访问当前节点p，并将p压入栈中。
//然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空
//从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。
void preorder()
{
int s[n0+1]; //栈
int t; //栈指针
int p = root;//树指针
while(p||t)
{//当p不为空或者栈不为空时
if(p)
{//当期指针不为空时候
s[++t] = p; //当前地址入栈
p = tree[p].llink; //p指向p的左孩子
}
else
{//如果p指向的p的左孩子为空，就是没有左孩子
p = s[t--];//p返回到它的父亲节点
cout<<tree[p].data; //访问当前节点
p = tree[p].rlink; //p指向它的父亲节点的右孩子
}
}
}
//后序遍历
//算法思路：当遇到非空的二叉树时候，首先将根节点地址和该节点的“右子树没有遍历”标记压入栈，然后沿
//左子数下降去遍历根节点的左子树，当遇到空二叉树时候，也就是这个节点没有左子树了，弹出栈顶元素，
//取得这个节点根节点的位置和，该根节点的右子树是否已经遍历的标记。
//1如果右子树已经遍历，就访问这个根节点。
//2如果右子树没有遍历，就把这个根节点的地址和这个根节点的“右子树已经遍历”的标记，压入栈中。然后沿
//右子树去遍历这个根节点的右子树。
//s[t] > 0 ：此节点右子树没有遍历
//s[t] < 0 : 此节点右子树已经遍历
void postorder()
{
int s[n0+1]; //栈
int t = 0; //栈指针
int p = root;//p指向当前节点
while(p||t)
{//当当前指针不为空 或者 栈不为空的时候
if(p)
{//如果当前指针不为空
s[++t] = p ;//同时p>0表示这个节点的右孩子还没有被遍历
p = tree[p].llink; //沿着左孩子向下遍历
}
else
{//如果当期指针为空了，表示栈顶节点的左孩子为空
if(s[t]<0)
{//如果这个栈顶节点的右孩子被访问过了
p = -s[t--]; //出栈，得到当前节点的父亲节点的地址
cout<<tree[p].data; //访问根节点
}
else
{//如果栈顶节点的右孩子没有被访问过
s[t] = -s[t]; //表示栈顶节点的右孩子已经被遍历过了
p = s[t]; //
p = tree[s[t]]->rlink;
}
}
}
}