二叉树:递归与非递归遍历

编辑于 2017-01-16

* 移动设备下, 可左滑手指以查看较宽代码

介绍二叉树的三种遍历,递归和非递归两种方法。

参考:www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

数据结构

typedef struct node {
    char data;
    struct node *lchild,*rchild;
} BinTree;

递归的遍历

//递归前序遍历
void preOrder1(BinTree *root)
{
    if(root!=NULL) {
        cout<<root->data<<" ";
        preOrder1(root->lchild);
        preOrder1(root->rchild);
    }
}

//递归中序遍历
void inOrder1(BinTree *root)
{
    if(root!=NULL) {
        inOrder1(root->lchild);
        cout<<root->data<<" ";
        inOrder1(root->rchild);
    }
}

//递归后序遍历
void postOrder1(BinTree *root)
{
    if(root!=NULL) {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->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;
        }
    }
}

非递归 - 后序遍历

在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点。对于任一结点 P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

void postOrder2(BinTree *root)
{
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL || !s.empty()) {
        //沿左子树一直往下搜索,直至出现没有左子树的结点
        while(p!=NULL) {
            BTNode *btn=new BTNode;
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty()) {
            temp=s.top();
            s.pop();
            //第一次出现在栈顶
            if(temp->isFirst==true) {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;
                //第二次出现在栈顶
            } else {
                cout<<temp->btnode->data<<" ";
                p=NULL;
            }
        }
    }
}