树的遍历算法

• 树的递归遍历

//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）

typedef  struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/递归方式前序遍历二叉树
void PreOrderTraverse(BiTree T, int level)
{
    if (T == NULL)
        return;

/*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
    //operation1(T->data);
    operation2(T->data, level); //输出了层数

    PreOrderTraverse(T->lchild, level + 1);
    PreOrderTraverse(T->rchild, level + 1);
}

//递归方式中序遍历二叉树

void InOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild,level+1);

//operation1(T->data);
operation2(T->data, level); //输出了层数

InOrderTraverse(T->rchild,level+1);
}

//递归方式后序遍历二叉树

void PostOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild,level+1);
PostOrderTraverse(T->rchild,level+1);

//operation1(T->data);
operation2(T->data, level); //输出了层数
}

• 树的层次遍历

/*二叉树层次遍历*/
void LevelTraverseTree(TreeNode * T)
{
    QueueHead * Q ;
    TreeNode * p ;
    Q = NULL ;    p = T ;
    Q = InitQueue(Q) ;
    if(NULL == p)
    {
        printf("树为空！\n") ;
        return ;
    }

    QueuePush(Q,p) ;
    while(!QueueEmpty(Q))
    {
        p = NULL ;
        QueuePop(Q,p) ;

        if(NULL != p->leftchild)
            QueuePush(Q,p->leftchild) ;

        if(NULL != p->rightchild)
            QueuePush(Q,p->rightchild) ;

        printf("%c  ", p->data) ;
    }
}

• 树的非递归前序遍历

// 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即
// 对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子
// 不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因
// 此其处理过程如下：
// 对于任一结点P：

// 1)访问结点P，并将结点P入栈;
// 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶
// 结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结
// 点P;
// 3)直到P为NULL并且栈为空，则遍历结束。

void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

• 树的非递归中序遍历

// 根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看
// 做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行
// 访问，然后按相同的规则访问其右子树。因此其处理过程如下：

// 对于任一结点P，
// 1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再
// 进行相同的处理；
// 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前
// 的P置为栈顶结点的右孩子；
// 3)直到P为NULL并且栈为空则遍历结束。

void inOrder2(BinTree *root)      //非递归中序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }    
}