您现在的位置是:首页 > 网站公告网站公告

Morris遍历--->为你的简历画龙点睛

2018-11-26【网站公告】人已围观

简介为什么学习Morris遍历

普通树的非递归遍历往往需要借助额外空间  比如:栈、队列

我们可以算出
            额外空间O(h)
而Morris遍历

            Morris空间O(1)

二者的时间复杂度都是O(n)

直觉上,认为它的复杂度是O(nlgn),因为找单个节点的前驱节点与树的高度有关。但事实上,寻找所有节点的前驱节点只需要O(n)时间。n个节点的二叉树中一共有n-1条边,整个过程中每条边最多只走2次,一次是为了定位到某个节点,另一次是为了寻找上面某个节点的前驱节点,如下图所示,其中红色是为了定位到某个节点,黑色线是为了找到前驱节点。所以复杂度为O(n)。


通过对比立见高下

Morris遍历流程
       来到的当前节点记为Cur
       <1>如果Cur无左孩子,Cur向右移动(Cur=Cur->right)
       <2>如果Cur有左孩子,找到Cur左子树上最右的节点,记为mostright
             (1)如果mostright的right指针指向空,让其指向Cur,Cur向左移动(Cur=Cur->left)
             (2)如果mostright的right指针指向Cur,让其指向空,Cur向右移动(Cur=Cur->right)

附递归、非递归、Morris遍历代码
#include <iostream>
#include <stack>
#include <malloc.h>
#include <cstdio>
#include <queue>
using namespace std;
typedef struct node {
    char data;
    struct node *lchild;
    struct node *rchild;
    int flag;
    node(int x) : data(x), lchild(NULL), rchild(NULL), flag(0) {}
}BiNode,*BiTree;

int k=0;
void createTree(BiTree &T)   //先序递归创建树,这里注意参数的类型,T的类型是 "*&" ,如果是 "**" 代码稍加改动就OK...
{
    char ch;
    cin.get(ch).get();
    if (ch==' ') T=NULL;
    else{
        T=(BiTree)malloc(sizeof(BiNode));
        T->data=ch;
        T->flag=k++;
        createTree(T->lchild);
        createTree(T->rchild);
    }
}

//递归

//先序遍历
void PreOrderTraversal(BiTree BT)
{
    if(BT){
        printf("%c  ",BT->data);
        PreOrderTraversal(BT->lchild);
        PreOrderTraversal(BT->rchild);
    }
}


//中序遍历
void InOrderTraversal(BiTree BT)
{
    if(BT){
        InOrderTraversal(BT->lchild);
        printf("%c  ",BT->data);
        InOrderTraversal(BT->rchild);
    }
}


//后序遍历
void PostOrderTraversal(BiTree BT)
{
    if(BT){
        PostOrderTraversal(BT->lchild);
        PostOrderTraversal(BT->rchild);
        printf("%c  ",BT->data);
    }
}


//层序遍历
void LeverOrderTraversal(BiTree BT)
{
    queue<BiTree> q;
    BiTree p;
    p=BT;
    q.push(p);
    while(!q.empty()){
        p=q.front();
        q.pop();
        cout<<p->data<<"  ";
        if(p->lchild)
            q.push(p->lchild);
        if(p->rchild)
            q.push(p->rchild);
    }
}

void preOrderNode(BiTree T)          // 前序遍历
{
    stack<BiTree> s;
    BiTree p;
    p=T;
    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;
        }
    }
}

void inOrderNode(BiTree T)       //中序遍历
{
    stack<BiTree> s;
    BiTree p;
    p=T;
    while(p!=NULL||!s.empty()){
        while(p!=NULL){
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty()){
            p=s.top();
            s.pop();
            cout<<p->data<<"  ";
            p=p->rchild;
        }
    }
}

void postOrderNode(BiTree T)          //后序遍历
{
    stack<BiTree> s;
    BiTree p;
    p=T;
    int *Tap=new int[256];
    while(p!=NULL||!s.empty()){
        while(p!=NULL){
            s.push(p);
            Tap[s.top()->flag]=0;
            p=p->lchild;
        }
        while(!s.empty()&&Tap[s.top()->flag]==1){
            cout<<s.top()->data<<"  ";
            s.pop();
        }
        if(!s.empty()){
            p=s.top();
            Tap[s.top()->flag]=1;
            p=p->rchild;
        }
    }
    delete []Tap;
}

void MorrisIn(BiTree T){
    if(T==NULL)
        return;
    BiTree cur,mostRight;
    cur = T;
    mostRight = NULL;
    while( cur != NULL ){
        mostRight = cur->lchild;
        if( mostRight != NULL){
            while( mostRight->rchild != NULL && mostRight->rchild != cur)
                mostRight = mostRight->rchild;
            if( mostRight->rchild == NULL){
                mostRight->rchild = cur;
                cur = cur->lchild;
                continue ;
            }else{
                mostRight->rchild = NULL;
            }
        }
        printf("%c  ",cur->data);
        cur = cur->rchild;
    }
    printf("\n");
}

void MorrisPre(BiTree T){
    if(T==NULL)
        return;
    BiTree cur,mostRight;
    cur = T;
    mostRight = NULL;
    while( cur != NULL ){
//        printf("%c  ",cur->data);
        mostRight = cur->lchild;
        if( mostRight != NULL){
            while( mostRight->rchild != NULL && mostRight->rchild != cur)
                mostRight = mostRight->rchild;
            if( mostRight->rchild == NULL){
                printf("%c  ",cur->data);
                mostRight->rchild = cur;
                cur = cur->lchild;
                continue ;
            }else{
                mostRight->rchild = NULL;
            }
        }else{
            printf("%c  ",cur->data);
        }
        cur = cur->rchild;
    }
    printf("\n");
}

void reverse(BiTree from, BiTree to){
    if (from == to)
        return;
    BiTree x = from, y = from->rchild, z;
    while (1){
        z = y->rchild;
        y->rchild = x;
        x = y;
        y = z;
        if (x == to)
            break;
    }
}

void printReverse(BiTree from, BiTree to){
    reverse(from, to);
    BiTree p = to;
    while (1){
        printf("%c  ",p->data);
        if (p == from)
            break;
        p = p->rchild;
    }
    reverse(to, from);
}

void MorrisPost(BiTree root){
    BiNode dump(0);
    dump.lchild = root;
    BiTree cur = &dump, prev = NULL;
    while (cur){
        if (cur->lchild == NULL)
            cur = cur->rchild;
        else{
            prev = cur->lchild;
            while (prev->rchild != NULL && prev->rchild != cur)
                prev = prev->rchild;
            if (prev->rchild == NULL){
                prev->rchild = cur;
                cur = cur->lchild;
            }else{
                printReverse(cur->lchild, prev);
                prev->rchild = NULL;
                cur = cur->rchild;
            }
        }
    }
    printf("\n");
}

int main()
{
    BiTree T;
    createTree(T);
    cout<<"前序遍历:  递归   非递归"<<endl;
    PreOrderTraversal(T);cout<<endl;//前序遍历
    preOrderNode(T);cout<<endl;//非递归
    cout<<endl;

    cout<<"中序遍历:  递归   非递归"<<endl;
    InOrderTraversal(T);cout<<endl;//中序遍历
    inOrderNode(T);cout<<endl;//非递归
    cout<<endl;

    cout<<"后序遍历:  递归   非递归"<<endl;
    PostOrderTraversal(T);cout<<endl;//后序遍历
    postOrderNode(T);cout<<endl;//非递归
    cout<<endl;

    cout<<"层序遍历:  非递归"<<endl;
    LeverOrderTraversal(T);cout<<endl;//层序遍历
    cout<<endl;

    cout<<"Morris遍历:  前序   中序   后序"<<endl;
    MorrisPre(T);
    MorrisIn(T);
    MorrisPost(T);
}
//A B D     F E       C G   H     I5

Tags:ACM   编程   算法

很赞哦! ()

上一篇:返回列表

下一篇:软件类证书|整理总结

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00