C前序遍历二叉树Morris Traversal算法

　　首先来递归算法，简单易懂：

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

typedef struct TreeNode{

    char data;

    struct TreeNode *lchild, *rchild;

}TreeNode;

void PreOrderTraverse(TreeNode *t){

    if( NULL == t ) return;

    printf("%c",t->data);

    PreOrderTraverse(t->lchild);

    PreOrderTraverse(t->rchild);

}

　　然后是栈模拟递归：

typedef struct StackNode{

    TreeNode *pdata;

    struct StackNode *next;

}StackNode;

typedef struct Stack{

    StackNode *top;

}Stack;

Stack *init_s(){

    Stack *pnew = (Stack *)malloc(sizeof(Stack));

    pnew->top = NULL;

    return pnew;

}

void push(Stack *s,TreeNode *p){

    StackNode *pnew = (StackNode *)malloc(sizeof(StackNode));

    pnew->pdata = p;

    pnew->next = s->top;

    s->top = pnew;

}

bool empty_stack(Stack *s){

    return NULL == s->top;

}

TreeNode *pop(Stack *s){

    TreeNode *p = NULL;

    StackNode *pn = NULL;

    if( ! empty_stack(s) ){

        pn = s->top;

        p = pn->pdata;

        s->top = pn->next;

        free(pn);

    }

    return p;

}

void PreOrderTraverse(TreeNode *t){

    if( NULL == t ) return;

    TreeNode *p = NULL;

    Stack *s = init_s();

    push(s,t);

    while( ! empty_stack(s) ){

        p = pop(s);

        if( NULL == p ){

            continue;

        }

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

        push(s,p->rchild);

        push(s,p->lchild);

    }

}

　　Morris Traversal算法：空间复杂度O(1)：

　　用线索二叉树（threaded binary tree）的概念，利用叶子的左右闲指针指向遍历的前驱或者后继节点。

　　算法如下：

　　1、初始化当前节点为root
　　2、若当前节点不为空
　　　　a) 若当前节点没有左孩子
　　　　　　访问当前节点，并将当前节点移向右孩子
　　　　b) 若当前节点有左孩子
　　　　　　找到左子树的最右边那个节点
　　　　　　若它的右指针为空，访问当前节点,把它的右指针指向cur,并移动到当前节点到左孩子
　　　　　　若它的右指针为当前节点，则把它的右指针重新设为空（恢复树），并移动到当前节点的右孩子
　　3、重复第2步

void PreOrderTraverse(TreeNode *t){

    if( NULL == t ) return;

    TreeNode *pcur = t, *pre = NULL;

    while( pcur ){

        if( pcur->lchild ){

            pre = pcur->lchild;

            while( pcur != pre->rchild && NULL != pre->rchild ){

                pre = pre->rchild;

            }

            if( pre->rchild == pcur ){

                pre->rchild = NULL;

                pcur = pcur->rchild;

            }

            else{

                printf("%c",pcur->data);

                pre->rchild = pcur;

                pcur = pcur->lchild;

            }

        }

        else{

            printf("%c",pcur->data);

            pcur = pcur->rchild;

        }

    }

}

　　main函数：

int main(){

    TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));

    TreeNode *pnew = (TreeNode *)malloc(sizeof(TreeNode));

    t->data = 'A';

    t->lchild = pnew;

    t->lchild->data = 'B';

    t->lchild->lchild = NULL;

    pnew = (TreeNode *)malloc(sizeof(TreeNode));

    t->lchild->rchild = pnew;

    t->lchild->rchild->data = 'D';

    t->lchild->rchild->lchild = NULL;

    t->lchild->rchild->rchild = NULL;

    pnew = (TreeNode *)malloc(sizeof(TreeNode));

    t->rchild = pnew;

    t->rchild->data = 'C';

    t->rchild->lchild = NULL;

    t->rchild->rchild = NULL;

    PreOrderTraverse(t);

    printf("\n");

}

巴特西

C前序遍历二叉树Morris Traversal算法

最新文章

热门文章