2013年07月27日

二叉树的遍历


二叉树的遍历,递归,非递归,Morris,线索

遍历

coolshell上看了看了二叉树迭代器算法的文章,想到先将二叉树的多种遍历算法一一总结一次,s顺便让自己更加熟练。 二叉树的遍历最为熟悉的也是最容易理解的便是递归方式,简单易懂,然而递归效率不高,需要一个函数递归调用的函数栈,简单的非递归方式使用stack来模拟递归的方式实现,这样每个节点需要进栈和出栈一次,并且需要使用到O(N)的空间,还有另外一种更加神奇的方式,使用Morris算法来遍历。

递归

递归的方式很简单,直接看代码。 假设二叉树的定义如下:

typedef struct tree{
    int value;
    struct tree* left;
    struct tree* right;
}BinaryTree;

递归的中序遍历如下:

void inorder(BinaryTree *tree){
    if(tree == NULL)
        return;
    if(tree->left != NULL)
        inorder(tree->left);
    cout << setw(4) << tree->value;
    if(tree->right != NULL)
        inorder(tree->right);
}

非递归

使用Stack来模拟函数递归调用的栈,下面的代码是先序遍历的Stack实现。

前序
void stackPreOrderV1(BinaryTree *tree){
    if(tree == NULL)
        return;
    std::stack<BinaryTree*> s;
    while(tree != NULL || !s.empty()){
        if(tree != NULL){
            cout << tree->value << " "; 
            s.push(tree);
            tree = tree->left;
        }else{
            tree = s.top();
            s.pop();
            tree = tree->right;
        }
    }
}

void stackPreOrderV2(BinaryTree *tree){
    if(tree == NULL)
        return;
    std::stack<BinaryTree *> s;
    s.push(tree);
    while(!s.empty()){
        while((tree = s.top()) != NULL){
            cout << tree->value << " ";
            s.push(tree->left);
        }
        s.pop();
        if(!s.empty()){
            tree = s.top();
            s.pop();
            tree = tree->right;
        }
    }
}

上面给出了前序遍历的两个非递归版本,本质上是一样的,两个之间的区别在于是否把空指针压入栈,所以第二个版本中间多了一次将空指针pop出栈的操作。基本的思路是将节点压入栈,然后将其左节点压入栈,依次往复直到叶子节点,然后弹出栈,可以访问其右节点。

由于前序和中序只是打印的语句放在不同的地方,故中序在此省略。

后序

后序遍历是其中最复杂的,因为在访问跟节点前,不仅需要左子树全都访问完,还必须保证右子树也要全都访问完成,所以判断情况要复杂于前序遍历和中序遍历。很显然的思路是增加对节点的访问标记,标记节点是否被访问完了。还有一种更加巧妙的方法,因为我们首先访问的是左子树,然后是右子树,最后才是根节点,若节点是叶子则可以访问,若节点的左右子树都被访问完,则节点可以访问,对于前面一种情况我们很好判断,对于后一种情况,我们可以引入一个指针,标记上一个被访问的节点,如果上一个被访问的节点是当前节点的子节点,则表明左右子树都被访问完了。

void stackPostOrder(BinaryTree *tree){
    if(tree == NULL)
        return;
    BinaryTree *pre = NULL;
    std::stack<BinaryTree *> s;
    s.push(tree);
    while(!s.empty()){
        tree = s.top();
        if((tree->left == NULL && tree->right == NULL) || 
            (pre != NULL && (pre == tree->left || pre == tree->right))){
            cout << tree->value << " ";
            s.pop();
            pre = tree;
        }else{
            if(tree->right != NULL)
                s.push(tree->right);
            if(tree->left != NULL)
                s.push(tree->left);
        }
    }
}

注意其中将左右子树添加到栈中的顺序,因为我们要先访问左子树,故需要将左子树放在栈顶,所以后入栈。

Morris遍历

前面提到的非递归遍历使用了O(N)的栈空间,空间效率不高,还有一种更加神奇的遍历方式,利用叶子节点空着的两个指针,因为我们在遍历到叶子节点之后需要再找到下一个节点访问,那么就可以利用叶子节点空着的指针指到下一个要访问的节点,这么遇到另一个问题,如何将叶子节点的两个指针还原了。我们脑中模拟这个过程,假定为中序遍历,三个节点的二叉树,根节点A,字节点B,C。首先从A出发,查找到B节点,B的右子树为空,可以将其指到下一个要访问的节点A,下次从A出发的时候,又找到B了,B的右子树已经连接到A,就可以发现,B是一个叶子节点,就消除右子树。我们可以从下面的代码中感受这段话。

中序
void morrisInOrder(BinaryTree *tree){
    if(tree == NULL)
        return;
    BinaryTree *tmp = NULL;
    while(tree != NULL){
        if(tree->left == NULL){
            cout << tree->value << " ";
            tree = tree->right;
        }else{
            tmp = tree->left;
            while(tmp->right != NULL && tmp->right != tree){
                tmp = tmp->right;
            } 
            if(tmp->right == NULL){
                tmp->right = tree;
                tree = tree->left;
            }else{
                cout << tree->value << " ";
                tmp->right = NULL; 
                tree = tree->right;
            }
        }
    }
    cout << endl;
}

观察这个Morris中序遍历,对每一个节点,如果其左子树为空,那么就访问这个节点,如果左子树不为空,就寻找左儿子的最右节点,将他们连接起来,下一次再回到此节点时,查找其左儿子的最右节点就会回到它本身,故知道这有个叶节点需要将其右子树置空。

前序
void morrisPreOrder(BinaryTree *tree){
    if(tree == NULL)
        return;
    BinaryTree *tmp = NULL;
    while(tree != NULL){
        if(tree->left == NULL){
            cout << tree->value << " ";
            tree = tree->right;
        }else{
            tmp = tree->left;
            while(tmp->right != NULL && tmp->right != tree){
                tmp = tmp->right;
            }
            if(tmp->right == NULL){
                tmp->right = tree;
                cout << tree->value << " ";
                tree = tree->left;
            }else{
                tmp->right = NULL;
                tree = tree->right;
            }
        }
    }
    cout << endl;
}

Morris前序遍历和中序遍历代码几乎一模一样,除了打印语句至于不同的地方。

后序

Morris后序遍历同样比较复杂,总是需要将左右子树均访问完成之后才能在访问根节点,我们发现前面使用morris遍历时,在第一次出现tmp->right == tree时,此时tree节点的左儿子节点是没有左子树的,可能存在右子树,并且可以看到一个单向链表,那么我们可以将tree的左子树遍历一遍,由于是后续遍历,所以需要从tree节点左儿子的最右节点往上遍历,所以可以使用一个stack来辅助当然这就违背了Morris只使用O(1)空间的原则,那么可以将左子树看成单向链表反转,然后遍历,再反转回来,使用stack则方便很多了。现在问题来了,我们无法访问tree节点了,因为tree节点还能有右子树,最棒的方式是构造一个伪根节点pesudo node,其左子树为根节点,右子树为空。那么现在所有的节点都成为了一个节点的左儿子,我们就可以通过刚才的方法统一遍历了。

void morrisPostOrder(BinaryTree *tree){
    if(tree == NULL)
        return;
    BinaryTree *tmp = NULL;
    BinaryTree *pesudo = new BinaryTree(0,tree,NULL);
    tree = pesudo;
    std::stack<BinaryTree *> s;
    while(tree != NULL){
        if(tree->left == NULL)
            tree = tree->right;
        else{
            tmp = tree->left;
            while(tmp->right != NULL && tmp->right != tree)
                tmp = tmp->right;
            if(tmp->right == NULL){
                tmp->right = tree;
                tree = tree->left;
            }else{
                if(tree->left == tmp){
                    cout << tmp->value <<" ";
                }else{
                    BinaryTree *node = tree->left;
                    while(node != tree){
                        s.push(node);
                        node = node->right;
                    }
                    while(!s.empty()){
                        cout << s.top()->value<< " ";
                        s.pop();
                    }
                }
                tmp->right = NULL; 
                tree = tree->right;
            }
        }
    }
    cout << endl;
    delete pesudo;
}

总结

二叉树存在三种不同的遍历方式,每种都各有其特点:

查看这三种方式的实现代码,发现不管哪种方式,前序和中序都是差不多的,唯有后续复杂很多,需要仔细观察,建立更多的判断条件。 CoolShell上提到了如何使用迭代器来遍历二叉树,思想和非递归遍历一样,使用stack来存储节点,方便调用next()来获取下一个需要访问的节点,对树的遍历方式没有改变,只是提供了统一的接口来对多种不同的数据结构进行同样的操作。

前一篇: Openstack Restful Api 后一篇: 随机数的简单生成