A. 二叉树的遍历

1.前序遍历二叉树：

(1)若二叉树为空，则为空操作，返回空。
(2)访问根结点。
(3)前序遍历左子树。
(4)前序遍历右子树。

a.二叉树前序遍历的递归算法：

[plain] view plain copy

print?

void PreOrderTraverse(BiTree BT)
{
if(BT)
{
printf("%c",BT->data); //访问根结点
PreOrderTraverse(BT->lchild); //前序遍历左子树
PreOrderTraverse(BT->rchild); //前序遍历右子树
}
}

b.使用栈存储每个结点右子树的二叉树前序遍历的非递归算法：

(1)当树为空时，将指针p指向根结点，p为当前结点指针。
(2)先访问当前结点p，并将p压入栈S中。
(3)令p指向其左孩子。
(4)重复执行步骤(2)、(3)，直到p为空为止。
(5)从栈S中弹出栈顶元素，将p指向此元素的右孩子。
(6)重复执行步骤(2)~(5)，直到p为空并且栈S也为空。
(7)遍历结束。
使用栈的前序遍历的非递归算法：

[plain] view plain copy
print?
void PreOrderNoRec(BiTree BT)
{
  stack S;
  BiTree p=BT->root;
  while((NULL!=p)||!StackEmpty(S))
  {
    if(NULL!=p)
    {
      printf("%c",p->data);
      Push(S,p);
      p=p->lchild;
    }
    else
    {
      p=Top(S);
      Pop(S);
      p=p->rchild;
    }
  }
}

c.使用二叉链表存储的二叉树前序遍历非递归算法：

[plain] view plain copy

print?

void PreOrder(pBinTreeNode pbnode)
{
pBinTreeNode stack[100];
pBinTreeNode p;
int top;
top=0;
p=pbnode;
do
{
while(p!=NULL)
{
printf("%d\n",p->data); //访问结点p
top=top+1;
stack[top]=p;
p=p->llink; //继续搜索结点p的左子树
}
if(top!=0)
{
p=stack[top];
top=top-1;
p=p->rlink; //继续搜索结点p的右子树
}
}while((top!=0)||(p!=NULL));
}

2.中序遍历二叉树：

(1)若二叉树为空，则为空操作，返回空。
(2)中序遍历左子树。
(3)访问根结点。
(4)中序遍历右子树。

a.二叉树中序遍历的递归算法：

[plain] view plain copy

print?

void InOrderTraverse(BiTree BT)
{
if(BT)
{
InOrderTraverse(BT->lchild); //中序遍历左子树
printf("%c",BT->data); //访问根结点
InOrderTraverse(BT->rchild); //中序遍历右子树
}
}

b.使用栈存储的二叉树中序遍历的非递归算法：

(1)当树为空时，将指针p指向根结点，p为当前结点指针。
(2)将p压入栈S中，并令p指向其左孩子。
(3)重复执行步骤(2)，直到p为空。
(4)从栈S中弹出栈顶元素，将p指向此元素。
(5)访问当前结点p，并将p指向其右孩子。
(6)重复执行步骤(2)~(5)，直到p为空并且栈S也为空。
(7)遍历结束。
使用栈的中序遍历的非递归算法：

[plain] view plain copy
print?
void IneOrderNoRec(BiTree BT)
{
  stack S;
  BiTree p=BT->root;
  while((NULL!=p)||!StackEmpty(S))
  {
    if(NULL!=p)
    {
      Push(S,p);
      p=p->lchild;
    }
    else
    {
      p=Top(S);
      Pop(S);
      printf("%c",p->data);
      p=p->rchild;
    }
  }
}

c.使用二叉链表存储的二叉树中序遍历非递归算法：

[plain] view plain copy

print?

void InOrder(pBinTreeNode pbnode)
{
pBinTreeNode stack[100];
pBinTreeNode p;
int top;
top=0;
p=pbnode;
do
{
while(p!=NULL)
{
top=top+1;
stack[top]=p; //结点p进栈
p=p->llink; //继续搜索结点p的左子树
}
if(top!=0)
{
p=stack[top]; //结点p出栈
top=top-1;
printf("%d\n",p->data); //访问结点p
p=p->rlink; //继续搜索结点p的右子树
}
}while((top!=0)||(p!=NULL));
}

3.后序遍历二叉树：

(1)若二叉树为空，则为空操作，返回空。
(2)后序遍历左子树。
(3)后序遍历右子树。
(4)访问根结点。

a.二叉树后序遍历的递归算法：

[plain] view plain copy

print?

void PostOrderTraverse(BiTree BT)
{
if(BT)
{
PostOrderTraverse(BT->lchild); //后序遍历左子树
PostOrderTraverse(BT->rchild); //后序遍历右子树
printf("%c",BT->data); //访问根结点
}
}

b.使用栈存储的二叉树后序遍历的非递归算法：

算法思想：首先扫描根结点的所有左结点并入栈，然后出栈一个结点，扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左、右子树均被访问后再访问该结点。因为在递归算法中，左子树和右子树都进行了返回，因此为了区分这两种情况，还需要设置一个标识栈tag，当tag的栈顶元素为0时表示从左子树返回，为1表示从右子树返回。
(1)当树为空时，将指针p指向根结点，p为当前结点指针。
(2)将p压入栈S中，0压入栈tag中，并令p指向其左孩子。
(3)重复执行步骤(2)，直到p为空。
(4)如果tag栈中的栈顶元素为1，跳至步骤(6)。
(5)如果tag栈中的栈顶元素为0，跳至步骤(7)。
(6)将栈S的栈顶元素弹出，并访问此结点，跳至步骤(8)。
(7)将p指向栈S的栈顶元素的右孩子。
(8)重复执行步骤(2)~(7)，直到p为空并且栈S也为空。
(9)遍历结束。
使用栈的后序遍历非递归算法：

[plain] view plain copy

print?